optiml.opti.constrained.active_set module

class optiml.opti.constrained.active_set.ActiveSet(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 Active Set Method 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\}\]

Since all the constraints are box ones, the active set is logically partitioned into the variables fixed to the lower bound (L) and those fixed to the upper bound (U); at each iteration the equality-constrained subproblem restricted to the remaining free variables (A), with the others held at their bounds, is solved in closed form as

\[x_A^\star = -Q_{AA}^{-1} \left( q_A + Q_{A,U}\, ub_U + Q_{A,L}\, lb_L \right)\]

(via a Cholesky factorization of \(Q_{AA}\), falling back to a minimum-norm solution when \(Q_{AA}\) is singular). If \(x_A^\star\) is feasible, a constraint whose multiplier has the wrong sign is released from the active set; otherwise the largest feasible step toward \(x_A^\star\) is taken and the newly hit bounds are added to the active set (Bland’s rule prevents cycling).

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 gradient at x 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()