Sequential quadratic programming

Sequential quadratic programming (SQP) is an iterative method for constrained nonlinear optimization, also known as Lagrange-Newton method. SQP methods are used on mathematical problems for which the objective function and the constraints are twice continuously differentiable, but not necessarily convex.

SQP methods solve a sequence of optimization subproblems, each of which optimizes a quadratic model of the objective subject to a linearization of the constraints. If the problem is unconstrained, then the method reduces to Newton's method for finding a point where the gradient of the objective vanishes. If the problem has only equality constraints, then the method is equivalent to applying Newton's method to the first-order optimality conditions, or Karush–Kuhn–Tucker conditions, of the problem.

Algorithm basics

Consider a nonlinear programming problem of the form:

:$\begin \min\limits_ & f(x) \\ \mbox & h(x) \ge 0 \\ & g(x) = 0. \end$
where $x \in \mathbb^n$, $f: \mathbb^n \rightarrow \mathbb$, $h: \mathbb^n \rightarrow \mathbb^$ and $g: \mathbb^n \rightarrow \mathbb^$.

The Lagrangian for this problem is
:$\mathcal(x,\lambda,\sigma) = f(x) + \lambda h(x) + \sigma g(x),$

where $\lambda$ and $\sigma$ are Lagrange multipliers.

The equality constrained case

If the problem does not have inequality constrained (that is, $m_I = 0$), the first-order optimality conditions (aka KKT conditions) $\nabla \mathcal(x, \sigma) = 0$ are a set of nonlinear equations that may be iteratively solved with Newton's Method. Newton's method linearizes the KKT conditions at the current iterate \left _k, \sigma_k \rightT,
which provides the following expression for the Newton step \left _x, d_\sigma \rightT:

\begin
d_x \\
d_\sigma
\end
= - nabla_^2 \mathcal(x_k, \sigma_k) \nabla_x \mathcal(x_k, \sigma_k)
= -
\begin
\nabla^2_ \mathcal(x_k, \sigma_k) & \nabla g(x_k, \sigma_k) \\
\nabla g^(x_k, \sigma_k) & 0
\end^
\begin
\nabla f(x_k) + \sigma_k \nabla g(x_k) \\
g(x_k)
\end
,

where $\nabla^2_ \mathcal(x_k, \sigma_k)$ denotes the Hessian matrix of the Lagrangian, and $d_x$ and $d_\sigma$ are the primal and dual displacements, respectively. Note that the Lagrangian Hessian is not explicitly inverted and a linear system is solved instead.

When the Lagrangian Hessian $\nabla^2 \mathcal(x_k, \sigma_k)$ is not positive definite, the Newton step may not exist or it may characterize a stationary point that is not a local minimum (but rather, a local maximum or a saddle point). In this case, the Lagrangian Hessian must be regularized, for example one can add a multiple of the identity to it such that the resulting matrix is positive definite.

An alternative view for obtaining the primal-dual displacements is to construct and solve a local quadratic model of the original problem at the current iterate:

$\begin \min\limits_ & f(x_k) + \nabla f(x_k)^T d_x + \frac d_x^T \nabla^2_ \mathcal(x_k, \sigma_k) d_x \\ \mathrm & g(x_k) + \nabla g(x_k)^T d_x = 0. \end$

The optimality conditions of this quadratic problem correspond to the linearized KKT conditions of the original problem.
Note that the term $f(x_k)$ in the expression above may be left out, since it is constant under the $\min\limits_$ operator.

The inequality constrained case

In the presence of inequality constraints ($m_I > 0$), we can naturally extend the definition of the local quadratic model introduced in the previous section:

$\begin \min\limits_ & f(x_k) + \nabla f(x_k)^Td + \frac d^T \nabla^2_ \mathcal(x_k, \lambda_k, \sigma_k) d \\ \mathrm & h(x_k) + \nabla h(x_k)^T d \ge 0 \\ & g(x_k) + \nabla g(x_k)^T d = 0. \end$

The SQP algorithm

The SQP algorithm starts from the initial iterate $(x_0, \lambda_0, \sigma_0)$. At each iteration, the QP subproblem is built and solved; the resulting Newton step direction _x, d_\lambda, d_\sigmaT is used to update current iterate:

\left x_, \lambda_, \sigma_ \rightT =
\left x_, \lambda_, \sigma_ \rightT + _x, d_\lambda, d_\sigmaT.

This process is repeated for $k = 0, 1, 2, \ldots$ until some convergence criterion is satisfied.

Practical implementations

Practical implementations of the SQP algorithm are significantly more complex than its basic version above. To adapt SQP for real-world applications, the following challenges must be addressed:
* The possibility of an infeasible QP subproblem.
* QP subproblem yielding a bad step: one that either fails to reduce the target or increases constraints violation.
* Breakdown of iterations due to significant deviation of the target/constraints from their quadratic/linear models.

To overcome these challenges, various strategies are typically employed:
* Use of merit functions, which assess progress towards a constrained solution, non-monotonic steps or filter methods.
* Trust region or line search methods to manage deviations between the quadratic model and the actual target.
* Special feasibility restoration phases to handle infeasible subproblems, or the use of L1-penalized subproblems to gradually decrease infeasibility

These strategies can be combined in numerous ways, resulting in a diverse range of SQP methods.

Alternative approaches

* Sequential linear programming
* Sequential linear-quadratic programming
* Augmented Lagrangian method

Implementations

SQP methods have been implemented in well known numerical environments such as MATLAB and GNU Octave. There also exist numerous software libraries, including open source:

* SciPy (de facto standard for scientific Python) has scipy.optimize.minimize(method='SLSQP') solver.

NLopt
(C/C++ implementation, with numerous interfaces including Julia, Python, R, MATLAB/Octave), implemented by Dieter Kraft as part of a package for optimal control, and modified by S. G. Johnson.
* ALGLIB SQP solver (C++, C#, Java, Python API)

acados
(C with interfaces to Python, MATLAB, Simulink, Octave) implements a SQP method tailored to the problem structure arising in optimal control, but tackles also general nonlinear programs.

and commercial

* LabVIEW
* KNITROKNITRO User Guide: Algorithms
/ref> (C, C++, C#, Java, Python, Julia, Fortran)
* NPSOL (Fortran)
* SNOPT (Fortran)
* NLPQL (Fortran)
* MATLAB
* SuanShu (Java)

See also

* Newton's method
* Secant method
* Model Predictive Control

Notes

References

*
*

External links

Sequential Quadratic Programming at NEOS guide

{{optimization algorithms, constrained

Optimization algorithms and methods