Metadata-Version: 2.4
Name: mizoGrad
Version: 1.0.0
Summary: Very Fast Gradient-Based Optimization Algorithms
Author-email: Mazen Alamir <mazen.alamir@grenoble-inp.fr>
Project-URL: Homepage, https://www.mazenalamir.fr/mizoGrad/
Project-URL: Documentation, https://www.mazenalamir.fr/mizoGrad/
Project-URL: Repository, https://github.com/mazenalamir/mizoGrad
Requires-Python: >=3.11
Description-Content-Type: text/markdown
Requires-Dist: numpy>=2.4.6

# mizoGrad: Search & Accelerate Gradient-Based Algorithm

This package encompasses two modules that enable  to address deterministic and stochastic formulation of 
optimization problem. Namely, the two modules are: 

- `GradOptimizer`: solves deterministic box-consrtained optimization problems 

- `StochasticGradOptimizer`: Solves stochastic box constrained in which the cost function 
 is defined to be one of the following three versions:

  - The `Expectation` of the cost function 
  - The value at risk `VaR` of the cost function for a given quantile value $\alpha$. 
  - The Complementary Value at Risk `CVaR` which is the expectation of values beyond `VaR`.

The cost function used in the stochastic version is determined through the value of the parameter `criterion` that 
is used when calling the `solve` method of the `StochasticGradOptimizer` class.
## Description 

This module is dedicated to the implementation of the Gradient-based box constrained optimization
proposed in the following two papers: 

- [paper for the determinisitic version](https://arxiv.org/abs/2607.14600).
- [paper for the stochastic version](https://arxiv.org/abs/2607.146000).

Both algorithms are based on the so-called Search & Acceleration (`SaA`) algorithm. 
The stochastic algorithm is based on a repetitive call for the basic `SaA` that is described hereafter.

The `SaA` algorithm combines the following features: 

- Line search along the gradient line 
- Line search along the acceleration path 
- Provable asymptotic convergence to a solution meeting the KKT-optimality conditions.

The above mentioned [paper](https://arxiv.org/abs/2607.14600) regarding the deterministic version shows that the algorithm outperfoms 
almost all existing gradient-based methods on a set of benchmark problems proposed in the
 [kaggle repository](https://www.kaggle.com/datasets/mazenalamir/gradient-based-optimization-collection-of-problems). The stochastic version leverages on this efficiency in order provide an efficient algorithm
fro the solution of the far more challenging problem of stochastic optimization. 

## Installation 

The package can be installed using one of the following commands:

```terminal 
uv add mizoGrad 
pip install mizoGrad
```

## The deterministic version `GradOptimizer`

### Input arguments for the instantiation method  

IN order to instantiate the `GradOptimizer` class, the user needs to provide the following **mandatory input arguments**:

- The first, say `cost`, represents the cost functiont to be minimized 
- The second, say `cost_gradient`,  is the gradient of the same cost funciton
- The number of decision variables `nx`

> **Note:** The names `cost` and `cost_gradient` are just examples, any names can be used; only their key fields 
> are detremined which are `f` and `g` respectively (see the example below).

The complete list of **input parameters** (including all those with defaults values) is given on the following table:

| Parameter   | Type     |    Default    | Description                          |
|-------------|----------|:-------------:|--------------------------------------|
| `f`         | callable |       —       | Cost function to minimize            |
| `g`         | callable |       —       | Gradient of the cost function        |
| `nx`        | int      |       —       | Number of decision variables         |
| `xmin`      | ndarray  | `[-inf] * nx` | Lower bound on the decision variable |
| `xmax`      | ndarray  | `[+inf] * nx` | Upper bound on the decision variable |
| `ng`        | int      |      `5`      | Number of exploration points         |
| `alpha_min` | float    |     `-8`      | lower initial exponent on the step   |
| `alpha_max` | float    |      `0`      | Higher initial exponent on the step  |
| `ng`        | int      |      `5`      | Number of exploration points         |
| `fast_min`  | float    |    `-0.2`     | Maximum number of iterations         |
| `fast_max`  | float    |      `1`      | Maximum number of iterations         |
| `rho_adapt` | float    |    `0.05`     | Adaptation ratio                     |
| `eta`       | float    |  `10^{-16}`   | Small step (<1/L)                    |


### The `solve` method of the `GradOptimizer` class

The problem is solved by invoking the `solve` method of the `GradOptimizer` class. 
This call needs the following arguments: 

| parameter | Type of value | Description                                                             |
|-----------|---------------|-------------------------------------------------------------------------|
| `x0`      | ndarray       | The initial guess                                                       |
| `kwargs`  | dictionary    | The dictionary of arguments used in the cost and the gradient functions |
| `maxIter` | int           | The maximum number of iterations allowed                                |
| `epsG`    | float         | Stopping threshold on the norm of the gradient                          |
| `display` | boolean       | Whether to print intermiediate results or not                           |


### Returned solution 

The returned solution is a **dictionary** with the following format:

| Dictionary key | Type of value | Description                                              |
|----------------|---------------|----------------------------------------------------------|
| `xopt`         | ndarray       | The best solution found                                  |
| `fopt`         | float         | The corresponding best cost function value               |
| `normG`        | float         | The norm of the gradient at solution                     |
| `lesalpha_min` | ndarray       | The sequence of values taken by `alpha_min`              |
| `lesalpha_max` | ndarray       | The sequence of values taken by `alpha_max`              |
| `traj`         | ndarray       | The sequence of values of the cost                       |
| `traj_c`       | ndarray       | The sequence of step sizes on the acceleration direction |


### Example of use

```python
import numpy as np
from mizoGrad import GradOptimizer
from time import time

np.set_printoptions(formatter={'float': lambda x: "{0:0.4f}".format(x)})

# Define the cost function and the gradient

def cost(x, a=10, b=2, m=1):

    f = np.power((x[0]-a)*x[1] + b * x[2] ** 3, 2*m)
    return f

def cost_gradient(x, a=10, b=2, m=1):
    term = 4 * np.power((x[0]-a)*x[1] + b * x[2] ** 3, 2*m-1)
    g = np.array([
        term * x[1],
        term * (x[0]-a),
        term * (3 * b * x[2] ** 2)
    ])
    return g


x0 = 2*np.array([1,1,1])

xmin = np.array([-5] * len(x0))
xmax = np.array([+5] * len(x0))

s2a = GradOptimizer(
    f=cost,
    g=cost_gradient,
    nx = 3,
    xmin=xmin,
    xmax=xmax,
    ng=5,
    alpha_min=-8,
    alpha_max=0,
    fast_min=-0.2,
    fast_max=1.0,
    rho_adapt=0.05,
    eta=1e-16,
)

# set the dictionary argument used the cost function and gradient 

kwargs = dict(
    a=3,
    b=1,
    m=1,
)

# solve the problem

t1 = time()
R = s2a.solve(x0=x0, kwargs=kwargs, maxIter=20, epsG=1e-8, display=True)
cpu = time()-t1

print('solution: ', np.array(R['xopt'], dtype=float))
print('best cost : ', cost(s2a.y, **kwargs))
print('cpu = ', cpu)

```

which gives the following results:

```
value 9.374756801 normg=292.957 | alpha_min=-8.0 | alpha_max=-0.4
value 3.931283917 normg=31.930 | alpha_min=-8.0 | alpha_max=-0.78
value 1.109572100 normg=17.759 | alpha_min=-7.962 | alpha_max=-0.419
value 0.000013588 normg=6.499 | alpha_min=-7.922 | alpha_max=-0.04185
value 0.000000666 normg=0.066 | alpha_min=-7.922 | alpha_max=-0.4359
value 0.000000029 normg=0.015 | alpha_min=-7.922 | alpha_max=-0.8102
value 0.000000000 normg=0.003 | alpha_min=-7.922 | alpha_max=-1.166
value 0.000000000 normg=0.000 | alpha_min=-7.922 | alpha_max=-1.504
value 0.000000000 normg=0.000 | alpha_min=-7.922 | alpha_max=-1.825
value 0.000000000 normg=0.000 | alpha_min=-7.89 | alpha_max=-1.52
value 0.000000000 normg=0.000 | alpha_min=-7.89 | alpha_max=-1.838
value 0.000000000 normg=0.000 | alpha_min=-7.859 | alpha_max=-1.536
value 0.000000000 normg=0.000 | alpha_min=-7.859 | alpha_max=-1.852
solution:  [1.7020 -1.2326 -1.1696]
best cost :  8.860672896017431e-21
cpu =  0.0008881092071533203
```

### Citing `mizoGrad.GradOptimizer` (Deterministic version)

```
@misc{alamir2026nonlinearmodelpredictivecontrol,
      title={A Nonlinear Model Predictive Control Perspective on Gradient-Based Optimization: A New Efficient, Parameter-Free and Provably Stable Algorithm}, 
      author={Mazen Alamir},
      year={2026},
      eprint={2607.14600},
      archivePrefix={arXiv},
      primaryClass={cs.CE},
      url={https://arxiv.org/abs/2607.14600}, 
}
```

## The stochastic version StochasticGradOptimizer`

The basic class `StochasticGradOptimizer` is a child class of the previous one. As such, all the input argument described above are 
also needed for this class in addition to some more arguments that controls the 
way the stochastic aspect of the problem is handled. This is the reason why for the sake of convenience, the dictionary 
containing the default values that might be used in the call can be obtained through the command: 

```python
from mizoGrad import dicGradDefault

# Load the default dictionary for the deterministic solver
dicGrad = dicGradDefault

# Update the dictionary with the mandatory values 
dicGrad.update(
    dict(
        f= ...,
        g= ...,
        nx= ...,
        xmin= ...,
        xmax= ...,
        )
)

```

The full list of arguments for the instantiation of the `StochasticGradOptimizer` class 
are described in the following section.

### Input arguments 


| Parameter          | Type        | Default | Description                                                                                            |
|--------------------|-------------|:-------:|--------------------------------------------------------------------------------------------------------|
| `dicGradOptimizer` | dictionary  |    —    | Dictionary representing the input arguments of the deterministic version                               |
| `key`              | str         |    —    | The key in the `kwargs` dictionary that corresponds to the stochastic variable                         |
| `realizations`     | numpy array |    -    | The matrix of realizations of the uncertain parameters used to approximate the cost.                   |
| `nDesign`          | int         |  `25`   | The number of realizations used as pivots in the algorithm.     <br/>                                  |
| `alpha_criterion`  | float       |  `95`   | The quantile used in the definition of the cost functions.     <br/>                                   |
| `nCV`              | int         |   `0`   | The number of extra candidate to be sampled from the convex hull    <br/>                              |
| `maxIterCV`        | int         |   `0`   | The number of convex-hull associated trials to improve the solution     <br/>                          |
| `m`                | int         |   `5`   | The number of best solution to be retained before a convex-hull operation is attempted.     <br/>      |
| `maxIter`          | int         |  `20`   | Number of iterations of the determinisitc solver for the first instance of uncertainty.     <br/>      |
| `maxIter_low`      | int         |   `5`   | Number of iterations of the determinisitc solver for the remaining instances of uncertainty.     <br/> |



### The solve method of `StochasticGradOptimizer`

Here again, the stochastic optimization problem is solved by calling the 
`solve` method of the `StochasticGradOptimizer` class.


| parameter   | Type of value | Description                                                             |
|-------------|---------------|-------------------------------------------------------------------------|
| `x0`        | ndarray       | The initial guess                                                       |
| `kwargs`    | dictionary    | The dictionary of arguments used in the cost and the gradient functions |
| `epsG`      | float         | Stopping threshold on the norm of the gradient                          |
| `display`   | boolean       | Whether to print intermiediate results or not                           |
| `criterion` | str           | one of {expectation, var, cvar} defining the criterion to be minimized  |

### Returned solution 

The `solve` method of the `StochasticGradOptimizer` class returns a dictionary with the following keys and values:


| Dictionary key | Type of value | Description                                                   |
|----------------|---------------|---------------------------------------------------------------|
| `xopt`         | ndarray       | The best solution found                                       |
| `fopt`         | float         | The corresponding best cost function value                    |
| `cpu`          | float         | The computation time of the stochastic algorithm.             |

### Example of use 

```python
import numpy as np
from mizoGrad import StochasticGradOptimizer, dicGradDefault
from time import time

# Define the problem, cost, grandient and uncertainty generator.
xc = np.array([0.0, 0.25, 0.5, 0.75, 1.25, 1.5])

phix = lambda x: np.sum((x - xc) ** 2)
phip = lambda p: np.sum((p-1)**2)
gradPhix = lambda x: 2*(x - xc)

# The cost function
def cost(x, p, lam, rho):
    x = np.array(x)
    p = np.array(p)
    v = phix(x) + rho * phip(p) * np.exp(-lam * phix(x))
    return v

# The gradient of the cost function
def grad(x, p, lam, rho):
    x = np.array(x)
    p = np.array(p)
    return (1-lam * rho * phip(p)* np.exp(-lam * phix(x))) * gradPhix(x)


# Function that generates a list of random realizations
def generate_p_samples(nSamples=1, pnom=(1, 1), sig=0):
    P = np.array([pnom + sig * np.random.randn(2) for _ in range(nSamples)])
    return P

# Define the algorithm parameters

nx = 6
x_upper = 5
sigma0 = 0.35
kwargs = dict(lam=0.5, rho=50)
N = 1000 # used in the design
nTest = 100000
nDesign = 50
# Choice of the criterion
# possible values are ['expectation', 'var', 'cvar']
criterion = 'cvar'

xmin = np.array([-x_upper] * nx)
xmax = np.array([x_upper] * nx)

Ptest = generate_p_samples(nSamples=nTest, sig=sigma0)

for sigma_train in [0, 0.35]:

    x0 = xmin + np.random.rand(nx) * (xmax - xmin)
    realizations = generate_p_samples(nSamples=N, sig=sigma_train)


    # Define the dictionary for GradOptimizer
    # Download the dafault arguments then update with mandatory ones
    dicGrad = dicGradDefault
    dicGrad.update(
        dict(
            f=cost,
            g=grad,
            nx=nx,
            xmin=xmin,
            xmax=xmax,
            )
    )

    sgo = StochasticGradOptimizer(dicGradOptimizer=dicGrad,
                                  realizations=realizations,
                                  key='p',
                                  nDesign=nDesign,
                                  )

    t0 = time()
    dR = sgo.solve(x0,
                   kwargs,
                   display=False,
                   epsG=1e-10,
                   criterion=criterion)

    cpu = time() - t0
    print(f'Results when learning using sigma = {sigma_train}')
    print(f'achieved {criterion} cost on working data = {dR["fopt"]:2.3f}  | cpu = {cpu:2.2f}')
    perf = sgo.global_cost(dR['xopt'], kwargs, Ptest, criterion=criterion)
    print(f'achieved cost on test data = {perf}')
    print('-----')
```

This results in the following output 

```terminal
Results when learning using sigma = 0
achieved cvar cost on working data = 0.000  | cpu = 0.49
achieved cost on test data = 48.49123245004931
-----
Results when learning using sigma = 0.35
achieved cvar cost on working data = 8.348  | cpu = 0.51
achieved cost on test data = 8.377288795786622
```

### Citing `mizoGrad.GradOptimizer` (Stochastic version)

```
@misc{alamir2026nonlinearmodelpredictivecontrol,
      title={A Unified Efficient Gradient-Based Heuristic For Box-Constrained Expectation-Related 
      and Risk-Averse Stochastic Optimization Problems}, 
      author={Mazen Alamir},
      year={2026},
      eprint={2609.07427},
      archivePrefix={arXiv},
      primaryClass={cs.CE},
      url={https://arxiv.org/abs/2609.07427}, 
}
```
