optiml.opti.constrained.projected_gradient module

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

Bases: BoxConstrainedQuadraticOptimizer

Apply the Projected Gradient 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 steepest descent direction \(d = -\nabla f(x)\) is projected over the active constraints (its components pushing against an active bound are zeroed), and the exact step size minimizing the quadratic along d,

\[\alpha = -\frac{d^\top (Q x + q)}{d^\top Q d}\]

is taken, clipped to the largest step \(\alpha_{\max}\) that keeps the iterate inside the box \(lb \le x \le ub\).

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.

• eps – (real scalar, optional, default value 1e-6): the accuracy in the stopping criterion: the algorithm is stopped when the norm of the (projected) gradient 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()