Skip to content

qp⚓︎

A small dense solver for the strictly convex quadratic programs of an SQP method.

solve_qp(B, g, A_eq=None, b_eq=None, A_iq=None, b_iq=None, lb=None, ub=None, rho=None, rho_max=None, tol=1e-09, maxiter=None) ⚓︎

Solve the quadratic program of an SQP step,

\[ \min_d \; g^T d + \tfrac{1}{2} d^T B d \quad \text{s.t.} \quad A_{eq} d + b_{eq} = 0, \quad A_{iq} d + b_{iq} \geq 0, \quad lb \leq d \leq ub. \]

The linear constraints are relaxed with non-negative slacks that cost rho each (an exact penalty), which does two things. A feasible starting point always exists (d = 0 with the slacks taking up the violation), so a primal active-set method needs no first phase; and constraints that cannot all hold, which happens for the linearisation of a nonlinear problem far from the solution, still give a step that reduces their violation. rho is raised until the slacks vanish or stop shrinking.

Parameters:

Name Type Description Default
B (ndarray, shape(n, n))

Symmetric positive definite Hessian.

required
g (ndarray, shape(n))

Gradient.

required
A_eq (ndarray, shape(m_eq, n) and (m_eq,))

Equality constraints.

None
b_eq (ndarray, shape(m_eq, n) and (m_eq,))

Equality constraints.

None
A_iq (ndarray, shape(m_iq, n) and (m_iq,))

Inequality constraints.

None
b_iq (ndarray, shape(m_iq, n) and (m_iq,))

Inequality constraints.

None
lb (ndarray, shape(n))

Bounds on d; infinite entries are free. lb <= 0 <= ub is expected.

None
ub (ndarray, shape(n))

Bounds on d; infinite entries are free. lb <= 0 <= ub is expected.

None
rho float

First penalty on the slacks. Default: ten times the largest gradient element, at least 1.

None
rho_max float

Largest penalty tried. Default: 1e8 * rho.

None
tol float

Tolerance on steps, multipliers and slacks.

1e-09
maxiter int

Active-set iterations per solve. Default: 50 times the number of variables and constraints.

None

Returns:

Name Type Description
d (ndarray, shape(n))

The step.

multipliers dict

'c_eq', 'c_iq', 'lb' and 'ub': multipliers of the equalities (either sign) and of the inequalities and bounds (non-negative), in the convention g + B d = A_eq^T lam_eq + A_iq^T lam_iq + lam_lb - lam_ub.

info dict

'slack': what is left of the linear constraints' violation (zero when they can hold), 'rho': the penalty used, 'iterations', and 'converged'.