optiml.opti.constrained.frank_wolfe module

class optiml.opti.constrained.frank_wolfe.FrankWolfe(quad, ub, lb=None, x=None, t=0.0, eps=1e-06, tol=1e-08, max_iter=1000, callback=None, callback_args=(), verbose=False)

Bases: BoxConstrainedQuadraticOptimizer

Apply the (possibly, stabilized) Frank-Wolfe algorithm with exact line search to the convex Box-Constrained Quadratic program

\[(P) \quad \min \left\{ \tfrac{1}{2} x^\top Q x + q^\top x : lb \le x \le ub \right\}\]

At each iteration the linearized problem \(\min \{ \nabla f(x)^\top y : lb \le y \le ub \}\) is solved over the box, whose vertex picks, per coordinate, \(ub_i\) where the gradient is negative and \(lb_i\) otherwise; this yields the descent direction \(d = y - x\), the lower bound \(f(x) + \nabla f(x)^\top (y - x)\) (whose gap to f(x) drives the stopping criterion), and the exact step size

\[\alpha = \min \left( -\frac{\nabla f(x)^\top d}{d^\top Q d},\; 1 \right)\]

Optionally the search is stabilized by restricting y to a box of relative size t around the current point.

Parameters:

• quad – the quadratic function \(\tfrac{1}{2} x^\top Q x + q^\top x\) to be minimized.

• ub – ([n x 1] real column vector): the upper bound of the box, i.e., the variables are constrained to lie in \(lb \le x \le ub\).

• lb – ([n x 1] real column vector, optional): the lower bound of the box; if not provided it defaults to the all-zeros vector.

• x – ([n x 1] real column vector, optional): the point where to start the algorithm from; if not provided, it starts from the middle of the box.

• t – (real scalar, optional, default value 0): if the stabilized version of the approach is used, then the new point is chosen in the box of relative size around the current point, i.e., the component x[i] is allowed to change by not more than plus or minus t * ub[i]. If t = 0, then the non-stabilized version of the algorithm is used. It has to lie in [0, 1).

• eps – (real scalar, optional, default value 1e-6): the accuracy in the stopping criterion: the algorithm is stopped when the relative gap between the value of the best primal solution (the current one) and the value of the best lower bound obtained so far is less than or equal to eps.

• tol – (real scalar, optional, default value 1e-8): the tolerance used to check the optimality conditions when f is a Lagrangian dual relaxation.

• max_iter – (integer scalar, optional, default value 1000): the maximum number of iterations.

• callback – (callable, optional, default value None): a function called at each iteration with the optimizer instance as first argument.

• callback_args – (tuple, optional, default value ()): additional arguments passed to callback.

• verbose – (boolean, optional, default value False): print details about each iteration if True, nothing otherwise.

Return x:

([n x 1] real column vector): the best solution found so far (possibly the optimal one).

Return status:

(string): the status of the algorithm at termination, one of: optimal (x is a(n approximately) optimal solution) or stopped (the maximum number of iterations or evaluations was reached).

minimize()

callback(args=())

check_lagrangian_dual_conditions()

check_lagrangian_dual_optimality()

f_star()

is_augmented_lagrangian_dual()

is_lagrangian_dual()

is_verbose()

x_star()