Sequential quadratic programming

Sequential quadratic programming (SQP) is an iterative method for constrained nonlinear optimization which may be considered a quasi-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:

${\displaystyle {\begin{array}{rl}\min \limits _{x}&f(x)\\{\mbox{subject to}}&h(x)\geq 0\\&g(x)=0.\end{array}}}$

The Lagrangian for this problem is^[1]

${\displaystyle {\mathcal {L}}(x,\lambda ,\sigma )=f(x)+\lambda h(x)+\sigma g(x),}$

where ${\displaystyle \lambda }$ and ${\displaystyle \sigma }$ are Lagrange multipliers.

The standard Newton's Method searches for the solution ${\displaystyle \nabla {\mathcal {L}}(x,\lambda ,\sigma )=0}$ by iterating the following equation, where ${\displaystyle \nabla _{xx}^{2}}$ denotes the Hessian matrix:

${\displaystyle {\begin{bmatrix}x_{k+1}\\\lambda _{k+1}\\\sigma _{k+1}\end{bmatrix}}={\begin{bmatrix}x_{k}\\\lambda _{k}\\\sigma _{k}\end{bmatrix}}-\underbrace {{\begin{bmatrix}\nabla _{xx}^{2}{\mathcal {L}}&\nabla h&\nabla g\\\nabla h^{T}&0&0\\\nabla g^{T}&0&0\end{bmatrix}}^{-1}} _{\nabla ^{2}{\mathcal {L}}}\underbrace {\begin{bmatrix}\nabla f+\lambda _{k}\nabla h+\sigma _{k}\nabla g\\h\\g\end{bmatrix}} _{\nabla {\mathcal {L}}}}$.

However, because the matrix ${\displaystyle \nabla ^{2}{\mathcal {L}}}$ is generally singular (and therefore non-invertible), the Newton step ${\displaystyle d_{k}=\left(\nabla _{xx}^{2}{\mathcal {L}}\right)^{-1}\nabla {\mathcal {L}}}$ cannot be calculated directly. Instead the basic sequential quadratic programming algorithm defines an appropriate search direction ${\displaystyle d_{k}}$ at an iterate ${\displaystyle (x_{k},\lambda _{k},\sigma _{k})}$, as a solution to the quadratic programming subproblem

${\displaystyle {\begin{array}{rl}\min \limits _{d}&f(x_{k})+\nabla f(x_{k})^{T}d+{\tfrac {1}{2}}d^{T}\nabla _{xx}^{2}{\mathcal {L}}(x_{k},\lambda _{k},\sigma _{k})d\\\mathrm {s.t.} &h(x_{k})+\nabla h(x_{k})^{T}d\geq 0\\&g(x_{k})+\nabla g(x_{k})^{T}d=0.\end{array}}}$

where the quadratic form is formed with the Hessian of the Lagrangian. Note that the term ${\displaystyle f(x_{k})}$ in the expression above may be left out for the minimization problem, since it is constant under the ${\displaystyle \min \limits _{d}}$ operator.

Together, the SQP algorithm starts by first choosing the initial iterate ${\displaystyle (x_{0},\lambda _{0},\sigma _{0})}$, then calculating ${\displaystyle \nabla ^{2}{\mathcal {L}}(x_{0},\lambda _{0},\sigma _{0})}$ and ${\displaystyle \nabla {\mathcal {L}}(x_{0},\lambda _{0},\sigma _{0})}$. Then the QP subproblem is built and solved to find the Newton step direction ${\displaystyle d_{0}}$ which is used to update the parent problem iterate using ${\displaystyle \left[x_{k+1},\lambda _{k+1},\sigma _{k+1}\right]^{T}=\left[x_{k},\lambda _{k},\sigma _{k}\right]^{T}+d_{k}}$. This process is repeated for ${\displaystyle k=0,1,2,\ldots }$ until the parent problem satisfies a convergence test.

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 an 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, 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.^[2][3]
• ALGLIB SQP solver (C++, C#, Java, Python API)

and commercial

• LabVIEW
• KNITRO^[4] (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

• Bonnans, J. Frédéric; Gilbert, J. Charles; Lemaréchal, Claude; Sagastizábal, Claudia A. (2006). Numerical optimization: Theoretical and practical aspects. Universitext (Second revised ed. of translation of 1997 French ed.). Berlin: Springer-Verlag. pp. xiv+490. doi:10.1007/978-3-540-35447-5. ISBN 978-3-540-35445-1. MR 2265882.
• Jorge Nocedal and Stephen J. Wright (2006). Numerical Optimization. Springer. ISBN 978-0-387-30303-1.

External links

• Sequential Quadratic Programming at NEOS guide

• v
• t
• e

Optimization: Algorithms, methods, and heuristics

Unconstrained nonlinear

Functions Golden-section search Interpolation methods Line search Nelder–Mead method Successive parabolic interpolation Gradients Convergence Trust region Wolfe conditions Quasi–Newton Berndt–Hall–Hall–Hausman Broyden–Fletcher–Goldfarb–Shanno and L-BFGS Davidon–Fletcher–Powell Symmetric rank-one (SR1) Other methods Conjugate gradient Gauss–Newton Gradient Mirror Levenberg–Marquardt Powell's dog leg method Truncated Newton Hessians Newton's method

Constrained nonlinear
General Barrier methods Penalty methods Differentiable Augmented Lagrangian methods Sequential quadratic programming Successive linear programming

Convex optimization
Convex minimization Cutting-plane method Reduced gradient (Frank–Wolfe) Subgradient method Linear and quadratic Interior point Affine scaling Ellipsoid algorithm of Khachiyan Projective algorithm of Karmarkar Basis-exchange Simplex algorithm of Dantzig Revised simplex algorithm Criss-cross algorithm Principal pivoting algorithm of Lemke

Combinatorial
Paradigms Approximation algorithm Dynamic programming Greedy algorithm Integer programming Branch and bound/cut Graph algorithms Minimum spanning tree Borůvka Prim Kruskal Shortest path Bellman–Ford SPFA Dijkstra Floyd–Warshall Network flows Dinic Edmonds–Karp Ford–Fulkerson Push–relabel maximum flow

Metaheuristics
Evolutionary algorithm Hill climbing Local search Parallel metaheuristics Simulated annealing Spiral optimization algorithm Tabu search

• Software