Solver class hierarchy

Solver object interface

class pyunlocbox.solvers.solver(step=1, post_step=None, post_sol=None)

Bases: object

Defines the solver object interface.

This class defines the interface of a solver object intended to be passed to the pyunlocbox.solvers.solve() solving function. It is intended to be a base class for standard solvers which will implement the required methods. It can also be instantiated by user code and dynamically modified for rapid testing. This class also defines the generic attributes of all solver objects.

Parameters:

step : float

The gradient-descent step-size. This parameter is bounded by 0 and \(\frac{2}{\beta}\) where \(\beta\) is the Lipschitz constant of the gradient of the smooth function (or a sum of smooth functions). Default is 1.

post_step : function

User defined function to post-process the step size. This function is called every iteration and permits the user to alter the solver algorithm. The user may start with a high step size and progressively lower it while the algorithm runs to accelerate the convergence. The function parameters are the following : step (current step size), sol (current problem solution), objective (list of successive evaluations of the objective function), niter (current iteration number). The function should return a new value for step. Default is to return an unchanged value.

post_sol : function

User defined function to post-process the problem solution. This function is called every iteration and permits the user to alter the solver algorithm. Same parameter as post_step(). Default is to return an unchanged value.

algo(objective, niter)

Call the solver iterative algorithm while allowing the user to alter it. This makes it possible to dynamically change the step step size while the algorithm is running. See parameters documentation in pyunlocbox.solvers.solve() documentation.

post()

Solver specific post-processing. Mainly used to delete references added during initialization so that the garbage collector can free the memory. See parameters documentation in pyunlocbox.solvers.solve() documentation.

pre(functions, x0)

Solver specific initialization. See parameters documentation in pyunlocbox.solvers.solve() documentation.

Forward-backward proximal splitting algorithm

class pyunlocbox.solvers.forward_backward(method='FISTA', lambda_=1, *args, **kwargs)

Bases: pyunlocbox.solvers.solver

Forward-backward proximal splitting algorithm.

This algorithm solves convex optimization problems composed of the sum of a smooth and a non-smooth function.

See generic attributes descriptions of the pyunlocbox.solvers.solver base class.

Parameters:

method : {‘FISTA’, ‘ISTA’}, optional

The method used to solve the problem. It can be ‘FISTA’ or ‘ISTA’. Note that while FISTA is much more time efficient, it is less memory efficient. Default is ‘FISTA’.

lambda_ : float, optional

The update term weight for ISTA. It should be between 0 and 1. Default is 1.

Notes

This algorithm requires one function to implement the pyunlocbox.functions.func.prox() method and the other one to implement the pyunlocbox.functions.func.grad() method.

See [BT09a] for details about the algorithm.

Examples

>>> from pyunlocbox import functions, solvers
>>> import numpy as np
>>> y = [4, 5, 6, 7]
>>> x0 = np.zeros(len(y))
>>> f1 = functions.norm_l2(y=y)
>>> f2 = functions.dummy()
>>> solver = solvers.forward_backward(method='FISTA', lambda_=1, step=0.5)
>>> ret = solvers.solve([f1, f2], x0, solver, atol=1e-5)
Solution found after 12 iterations:
    objective function f(sol) = 4.135992e-06
    stopping criterion: ATOL
>>> ret['sol']
array([ 3.99927529,  4.99909411,  5.99891293,  6.99873176])

Douglas-Rachford proximal splitting algorithm

class pyunlocbox.solvers.douglas_rachford(lambda_=1, *args, **kwargs)

Bases: pyunlocbox.solvers.solver

Douglas-Rachford proximal splitting algorithm.

This algorithm solves convex optimization problems composed of the sum of two non-smooth (or smooth) functions.

See generic attributes descriptions of the pyunlocbox.solvers.solver base class.

Parameters:

lambda_ : float, optional

The update term weight. It should be between 0 and 1. Default is 1.

Notes

This algorithm requires the two functions to implement the pyunlocbox.functions.func.prox() method.

See [CP07] for details about the algorithm.

Examples

>>> from pyunlocbox import functions, solvers
>>> import numpy as np
>>> y = [4, 5, 6, 7]
>>> x0 = np.zeros(len(y))
>>> f1 = functions.norm_l2(y=y)
>>> f2 = functions.dummy()
>>> solver = solvers.douglas_rachford(lambda_=1, step=1)
>>> ret = solvers.solve([f1, f2], x0, solver, atol=1e-5)
Solution found after 8 iterations:
    objective function f(sol) = 2.927052e-06
    stopping criterion: ATOL
>>> ret['sol']
array([ 3.99939034,  4.99923792,  5.99908551,  6.99893309])

Generalized forward-backward proximal splitting algorithm

class pyunlocbox.solvers.generalized_forward_backward(lambda_=1, *args, **kwargs)

Bases: pyunlocbox.solvers.solver

Generalized forward-backward proximal splitting algorithm.

This algorithm solves convex optimization problems composed of the sum of any number of non-smooth (or smooth) functions.

See generic attributes descriptions of the pyunlocbox.solvers.solver base class.

Parameters:

lambda_ : float, optional

A relaxation parameter bounded by 0 and 1. Default is 1.

Notes

This algorithm requires each function to either implement the pyunlocbox.functions.func.prox() method or the pyunlocbox.functions.func.grad() method.

See [RFP13] for details about the algorithm.

Examples

>>> from pyunlocbox import functions, solvers
>>> import numpy as np
>>> y = [0.01, 0.2, 8, 0.3, 0 , 0.03, 7]
>>> x0 = np.zeros(len(y))
>>> f1 = functions.norm_l2(y=y)
>>> f2 = functions.norm_l1()
>>> solver = solvers.generalized_forward_backward(lambda_=1, step=0.5)
>>> ret = solvers.solve([f1, f2], x0, solver)
Solution found after 2 iterations:
    objective function f(sol) = 1.463100e+01
    stopping criterion: RTOL
>>> ret['sol']
array([ 0. ,  0. ,  7.5,  0. ,  0. ,  0. ,  6.5])

Primal-dual algorithms

class pyunlocbox.solvers.primal_dual(L=None, Lt=None, d0=None, *args, **kwargs)

Bases: pyunlocbox.solvers.solver

Parent class of all primal-dual algorithms.

See generic attributes descriptions of the pyunlocbox.solvers.solver base class.

Parameters:

L : function or ndarray, optional

The transformation L that maps from the primal variable space to the dual variable space. Default is the identity, \(L(x)=x\). If L is an ndarray, it will be converted to the operator form.

Lt : function or ndarray, optional

The adjoint operator. If Lt is an ndarray, it will be converted to the operator form. If L is an ndarray, default is the transpose of L. If L is a function, default is L, \(Lt(x)=L(x)\).

d0: ndarray, optional

Initialization of the dual variable.

Monotone+Lipschitz forward-backward-forward algorithm

class pyunlocbox.solvers.mlfbf(L=None, Lt=None, d0=None, *args, **kwargs)

Bases: pyunlocbox.solvers.primal_dual

Monotone + Lipschitz Forward-Backward-Forward primal-dual algorithm.

This algorithm solves convex optimization problems with objective of the form \(f(x) + g(Lx) + h(x)\), where \(f\) and \(g\) are proper, convex, lower-semicontinuous functions with easy-to-compute proximity operators, and \(h\) has Lipschitz-continuous gradient with constant \(\beta\).

See generic attributes descriptions of the pyunlocbox.solvers.primal_dual base class.

Notes

The order of the functions matters: set \(f\) first on the list, \(g\) second, and \(h\) third.

This algorithm requires the first two functions to implement the pyunlocbox.functions.func.prox() method, and the third function to implement the pyunlocbox.functions.func.grad() method.

The step-size should be in the interval \(\left] 0, \frac{1}{\beta + \|L\|_{2}}\right[\).

See [KP15], Algorithm 6, for details.

Examples

>>> from pyunlocbox import functions, solvers
>>> import numpy as np
>>> y = np.array([294, 390, 361])
>>> L = np.array([[5, 9, 3], [7, 8, 5], [4, 4, 9], [0, 1, 7]])
>>> x0 = np.zeros(len(y))
>>> f = functions.dummy()
>>> f._prox = lambda x, T: np.maximum(np.zeros(len(x)), x)
>>> g = functions.norm_l2(lambda_=0.5)
>>> h = functions.norm_l2(y=y, lambda_=0.5)
>>> max_step = 1/(1 + np.linalg.norm(L, 2))
>>> solver = solvers.mlfbf(L=L, step=max_step/2.)
>>> ret = solvers.solve([f, g, h], x0, solver, maxit=1000, rtol=0)
Solution found after 1000 iterations:
    objective function f(sol) = 1.833865e+05
    stopping criterion: MAXIT
>>> ret['sol']
array([ 1.,  1.,  1.])

Projection-based primal-dual algorithm

class pyunlocbox.solvers.projection_based(lambda_=1, *args, **kwargs)

Bases: pyunlocbox.solvers.primal_dual

Projection-based primal-dual algorithm.

This algorithm solves convex optimization problems with objective of the form \(f(x) + g(Lx)\), where \(f\) and \(g\) are proper, convex, lower-semicontinuous functions with easy-to-compute proximity operators.

See generic attributes descriptions of the pyunlocbox.solvers.primal_dual base class.

Parameters:

lambda_ : float, optional

The update term weight. It should be between 0 and 2. Default is 1.

Notes

The order of the functions matters: set \(f\) first on the list, and \(g\) second.

This algorithm requires the two functions to implement the pyunlocbox.functions.func.prox() method.

The step-size should be in the interval \(\left] 0, \infty \right[\).

See [KP15], Algorithm 7, for details.

Examples

>>> from pyunlocbox import functions, solvers
>>> import numpy as np
>>> y = np.array([294, 390, 361])
>>> L = np.array([[5, 9, 3], [7, 8, 5], [4, 4, 9], [0, 1, 7]])
>>> x0 = np.array([500, 1000, -400])
>>> f = functions.norm_l1(y=y)
>>> g = functions.norm_l1()
>>> solver = solvers.projection_based(L=L, step=1.)
>>> ret = solvers.solve([f, g], x0, solver, maxit=1000, rtol=None, xtol=.1)
Solution found after 996 iterations:
    objective function f(sol) = 1.045000e+03
    stopping criterion: XTOL
>>> ret['sol']
array([0, 0, 0])