Solving function

pyunlocbox.solvers.solve(functions, x0, solver=None, atol=None, dtol=None, rtol=0.001, xtol=None, maxit=200, verbosity='LOW')[source]

Solve an optimization problem whose objective function is the sum of some convex functions.

This function minimizes the objective function \(f(x) = \sum\limits_{k=0}^{k=K} f_k(x)\), i.e. solves \(\operatorname{arg\,min}\limits_x f(x)\) for \(x \in \mathbb{R}^{n \times N}\) where \(n\) is the dimensionality of the data and \(N\) the number of independent problems. It returns a dictionary with the found solution and some informations about the algorithm execution.

Parameters:

functions : list of objects

A list of convex functions to minimize. These are objects who must implement the pyunlocbox.functions.func.eval() method. The pyunlocbox.functions.func.grad() and / or pyunlocbox.functions.func.prox() methods are required by some solvers. Note also that some solvers can only handle two convex functions while others may handle more. Please refer to the documentation of the considered solver.

x0 : array_like

Starting point of the algorithm, \(x_0 \in \mathbb{R}^{n \times N}\). Note that if you pass a numpy array it will be modified in place during execution to save memory. It will then contain the solution. Be careful to pass data of the type (int, float32, float64) you want your computations to use.

solver : solver class instance, optional

The solver algorithm. It is an object who must inherit from pyunlocbox.solvers.solver and implement the _pre(), _algo() and _post() methods. If no solver object are provided, a standard one will be chosen given the number of convex function objects and their implemented methods.

atol : float, optional

The absolute tolerance stopping criterion. The algorithm stops when \(f(x^t) < atol\) where \(f(x^t)\) is the objective function at iteration \(t\). Default is None.

dtol : float, optional

Stop when the objective function is stable enough, i.e. when \(\left|f(x^t) - f(x^{t-1})\right| < dtol\). Default is None.

rtol : float, optional

The relative tolerance stopping criterion. The algorithm stops when \(\left|\frac{ f(x^t) - f(x^{t-1}) }{ f(x^t) }\right| < rtol\). Default is \(10^{-3}\).

xtol : float, optional

Stop when the variable is stable enough, i.e. when \(\frac{\|x^t - x^{t-1}\|_2}{\sqrt{n N}} < xtol\). Note that additional memory will be used to store \(x^{t-1}\). Default is None.

maxit : int, optional

The maximum number of iterations. Default is 200.

verbosity : {‘NONE’, ‘LOW’, ‘HIGH’, ‘ALL’}, optional

The log level : 'NONE' for no log, 'LOW' for resume at convergence, 'HIGH' for info at all solving steps, 'ALL' for all possible outputs, including at each steps of the proximal operators computation. Default is 'LOW'.

Returns:

sol : ndarray

The problem solution.

solver : str

The used solver.

crit : {‘ATOL’, ‘DTOL’, ‘RTOL’, ‘XTOL’, ‘MAXIT’}

The used stopping criterion. See above for definitions.

niter : int

The number of iterations.

time : float

The execution time in seconds.

objective : ndarray

The successive evaluations of the objective function at each iteration.

Examples

>>> import pyunlocbox
>>> import numpy as np

Define a problem:

>>> y = [4, 5, 6, 7]
>>> f = pyunlocbox.functions.norm_l2(y=y)

Solve it:

>>> x0 = np.zeros(len(y))
>>> ret = pyunlocbox.solvers.solve([f], x0, atol=1e-2, verbosity='ALL')
INFO: Dummy objective function added.
INFO: Selected solver : forward_backward
    norm_l2 evaluation : 1.260000e+02
    dummy evaluation : 0.000000e+00
INFO: Forward-backward method : FISTA
Iteration 1 of forward_backward :
    norm_l2 evaluation : 1.400000e+01
    dummy evaluation : 0.000000e+00
    objective = 1.40e+01
Iteration 2 of forward_backward :
    norm_l2 evaluation : 1.555556e+00
    dummy evaluation : 0.000000e+00
    objective = 1.56e+00
Iteration 3 of forward_backward :
    norm_l2 evaluation : 3.293044e-02
    dummy evaluation : 0.000000e+00
    objective = 3.29e-02
Iteration 4 of forward_backward :
    norm_l2 evaluation : 8.780588e-03
    dummy evaluation : 0.000000e+00
    objective = 8.78e-03
Solution found after 4 iterations :
    objective function f(sol) = 8.780588e-03
    stopping criterion : ATOL

Verify the stopping criterion (should be smaller than atol=1e-2):

>>> np.linalg.norm(ret['sol'] - y)**2
0.008780587752251795

Show the solution (should be close to y w.r.t. the L2-norm measure):

>>> ret['sol']
array([ 4.03339154,  5.04173943,  6.05008732,  7.0584352 ])

Show the used solver:

>>> ret['solver']
'forward_backward'

Show some information about the convergence:

>>> ret['crit']
'ATOL'
>>> ret['niter']
4
>>> ret['time']  
0.0012578964233398438
>>> ret['objective']  
[[126.0, 0], [13.999999999999998, 0], [1.5555555555555558, 0],
[0.032930436204105726, 0], [0.0087805877522517933, 0]]