optiml.opti.constrained.interior_point module

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

Bases: BoxConstrainedQuadraticOptimizer

Apply the Primal-Dual (feasible) Interior (barrier) 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\}\]

At each iteration a feasible interior primal-dual solution is updated by taking a Newton step on the slackened KKT system, in which the complementarity equations are linearized; the step size is then chosen so that the new iterate remains strictly interior.

Introducing the multipliers \(\lambda^+, \lambda^- \ge 0\) for the upper and lower bounds, the perturbed (slackened) KKT system of (P) reads

\[Q x + q + \lambda^+ - \lambda^- = 0, \quad \lambda^+ (ub - x) = \mu e, \quad \lambda^- x = \mu e, \quad 0 \le x \le ub\]

where \(e\) is the all-ones vector and \(\mu > 0\) is the barrier parameter driven to 0. Linearizing the complementarity equations (dropping the bilinear terms) reduces the Newton step to the single symmetric positive definite system

\[\underbrace{\left( Q + \tfrac{\lambda^+}{ub - x} + \tfrac{\lambda^-}{x} \right)}_{H} dx = \mu \left( \tfrac{e}{ub - x} - \tfrac{e}{x} \right) + \lambda^+ - \lambda^-\]

solved by a Cholesky factorization of \(H\); the primal/dual increments are recovered from \(dx\) and a fraction (0.9995) of the maximum feasible step is taken to stay interior. The duality gap \(v - p = 2 n \mu\) certifies optimality.

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-10): the accuracy in the stopping criterion: the algorithm is stopped when the relative gap between the value of the current primal and dual feasible solutions 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()