optiml.opti.constrained package

Submodules

Module contents

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

Bases: Optimizer, ABC

Abstract base class for the optimizers that solve the convex Box-Constrained Quadratic program

\[(P) \quad \min \left\{ \tfrac{1}{2} x^\top Q x + q^\top x : 0 \le x \le ub \right\}\]
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, i.e., \(0 \le x \le ub\).

  • 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 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.

Return status:

(string): the status of the algorithm at termination, one of: optimal (x is a(n approximately) optimal solution), unbounded (f() was driven below m_inf, i.e., the problem looks unbounded below), stopped (the maximum number of iterations or evaluations was reached) or error (a numerical error occurred, e.g., the step size fell below min_a).

f_star()[source]
x_star()[source]
callback(args=())
check_lagrangian_dual_conditions()
check_lagrangian_dual_optimality()
is_augmented_lagrangian_dual()
is_lagrangian_dual()
is_verbose()
minimize()
class optiml.opti.constrained.LagrangianQuadratic(primal, A=None, b=None, G=None, h=None, lb=None, ub=None)[source]

Bases: Quadratic

Construct the lagrangian relaxation of a constrained quadratic function defined as

\[\tfrac{1}{2} x^\top Q x + q^\top x : A x = b, \; G x \le h, \; lb \le x \le ub\]

i.e.,

\[\tfrac{1}{2} x^\top Q x + q^\top x : A x = b, \; \hat{G} x \le \hat{h}\]

where \(\hat{G}^\top = [\, G \;\; -I \;\; I \,]\) and \(\hat{h} = [\, h \;\; -lb \;\; ub \,]\).

Construct a quadratic function from its linear and quadratic part defined as

\[\tfrac{1}{2} x^\top Q x + q^\top x\]
Parameters:

  • Q – ([n x n] real symmetric matrix, not necessarily positive semidefinite): the Hessian (i.e., the quadratic part) of f. If it is not positive semidefinite, f(x) will be unbounded below.

  • q – ([n x 1] real column vector): the linear part of f.

f_star()[source]
x_star()[source]
constraints(x_mu_lmbda)[source]
function(x_mu_lmbda)[source]

Compute the value of the augmented lagrangian relaxation defined as

\[L(x, \mu, \lambda) = \tfrac{1}{2} x^\top Q x + q^\top x + \mu^\top (A x - b) + \lambda^\top (G x - h)\]
Parameters:

x_mu_lmbda – the primal-dual variable wrt evaluate the function

Returns:

the function value wrt primal-dual variable

jacobian(x_mu_lmbda)[source]

Compute the jacobian of the lagrangian relaxation defined as

\[J L(x, \mu, \lambda) = Q x + q + \mu^\top A + \lambda^\top G\]
Parameters:

x_mu_lmbda – the primal-dual variable wrt evaluate the jacobian

Returns:

the jacobian wrt primal-dual variable

hessian(x)[source]

The Hessian matrix of a general quadratic function \(H f(x) = Q\).

Parameters:

x – 1D array of points at which the Hessian is to be computed.

Returns:

the Hessian matrix (i.e., the quadratic part) of a general quadratic function at x.

args()
function_jacobian(*args, **kwargs)
class optiml.opti.constrained.AugmentedLagrangianQuadratic(primal, A=None, b=None, G=None, h=None, lb=None, ub=None, rho=1)[source]

Bases: Quadratic

Construct the augmented lagrangian relaxation of a constrained quadratic function defined as

\[\tfrac{1}{2} x^\top Q x + q^\top x : A x = b, \; G x \le h, \; lb \le x \le ub\]

i.e.,

\[\tfrac{1}{2} x^\top Q x + q^\top x : A x = b, \; \hat{G} x \le \hat{h}\]

where \(\hat{G}^\top = [\, G \;\; -I \;\; I \,]\) and \(\hat{h} = [\, h \;\; -lb \;\; ub \,]\).

Construct a quadratic function from its linear and quadratic part defined as

\[\tfrac{1}{2} x^\top Q x + q^\top x\]
Parameters:

  • Q – ([n x n] real symmetric matrix, not necessarily positive semidefinite): the Hessian (i.e., the quadratic part) of f. If it is not positive semidefinite, f(x) will be unbounded below.

  • q – ([n x 1] real column vector): the linear part of f.

args()
f_star()[source]
x_star()[source]
constraints(x)[source]
function(x)[source]

Compute the value of the augmented lagrangian relaxation defined as

\[L(x, \mu, \lambda) = \tfrac{1}{2} x^\top Q x + q^\top x + \mu^\top (A x - b) + \lambda^\top (G x - h) + \tfrac{\rho}{2} \| (A x - b) + (G x - h) \|^2\]
Parameters:

x – the primal variable wrt evaluate the function

Returns:

the function value wrt primal-dual variable

jacobian(x)[source]

Compute the jacobian of the augmented lagrangian relaxation defined as

\[J L(x, \mu, \lambda) = Q x + q + \mu^\top A + \lambda^\top G + \rho ((A x - b) + (G x - h))\]
Parameters:

x – the primal variable wrt evaluate the jacobian

Returns:

the jacobian wrt primal-dual variable

function_jacobian(x)[source]
hessian(x)[source]

The Hessian matrix of a general quadratic function \(H f(x) = Q\).

Parameters:

x – 1D array of points at which the Hessian is to be computed.

Returns:

the Hessian matrix (i.e., the quadratic part) of a general quadratic function at x.

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

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()[source]
callback(args=())
check_lagrangian_dual_conditions()
check_lagrangian_dual_optimality()
f_star()
is_augmented_lagrangian_dual()
is_lagrangian_dual()
is_verbose()
x_star()
class optiml.opti.constrained.ActiveSet(quad, ub, lb=None, x=None, eps=1e-06, tol=1e-08, max_iter=1000, callback=None, callback_args=(), verbose=False)[source]

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()[source]
callback(args=())
check_lagrangian_dual_conditions()
check_lagrangian_dual_optimality()
f_star()
is_augmented_lagrangian_dual()
is_lagrangian_dual()
is_verbose()
x_star()
class optiml.opti.constrained.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)[source]

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()[source]
callback(args=())
check_lagrangian_dual_conditions()
check_lagrangian_dual_optimality()
f_star()
is_augmented_lagrangian_dual()
is_lagrangian_dual()
is_verbose()
x_star()
class optiml.opti.constrained.InteriorPoint(quad, ub, lb=None, x=None, eps=1e-10, tol=1e-08, max_iter=1000, callback=None, callback_args=(), verbose=False)[source]

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()[source]
callback(args=())
check_lagrangian_dual_conditions()
check_lagrangian_dual_optimality()
f_star()
is_augmented_lagrangian_dual()
is_lagrangian_dual()
is_verbose()
x_star()