mushi.optimization.AccProxGrad

class AccProxGrad(g, grad, h, prox, verbose=False, **line_search_kwargs)[source]

Bases: mushi.optimization.LineSearcher

Nesterov accelerated proximal gradient method with backtracking line search 1.

The optimization problem solved is:

\[\arg\min_x g(x) + h(x)\]

where \(g\) is differentiable, and the proximal operator for \(h\) is available.

Parameters

References

1

https://people.eecs.berkeley.edu/~elghaoui/Teaching/EE227A/lecture18.pdf

Examples

>>> import mushi.optimization as opt
>>> import numpy as np

We’ll use a squared loss term and a Lasso term for this example, since we can specify the solution analytically (indeed, it is directly the prox of the Lasso term).

Define \(g(x)\) and \(\boldsymbol\nabla g(x)\):

>>> def g(x):
...     return 0.5 * np.sum(x ** 2)
>>> def grad(x):
...     return x

Define \(h(x)\) and \(\mathrm{prox}_h(u)\) (we will use a Lasso term and the corresponding soft thresholding operator):

>>> def h(x):
...     return np.linalg.norm(x, 1)
>>> def prox(u, s):
...     return np.sign(u) * np.clip(np.abs(u) - s, 0, None)

Initialize optimizer and define initial point

>>> fista = opt.AccProxGrad(g, grad, h, prox)
>>> x = np.zeros(2)

Run optimization

>>> fista.run(x)
array([0., 0.])

Evaluate cost at the solution point

>>> fista.f()
0.0

Methods

f

Evaluate cost function at current solution point.

run

Optimize until convergence criteria are met.

f()[source]

Evaluate cost function at current solution point.

run(x, tol=1e-06, max_iter=100)

Optimize until convergence criteria are met.

Parameters
  • x (ndarray) – initial point

  • tol (float64) – relative tolerance in objective function

  • max_iter (int) – maximum number of iterations

Returns

solution point

Return type

x