Sequential quadratic programming

This article provides insufficient context for those unfamiliar with the subject. Please help by providing more context for the reader. (October 2009) (Learn how and when to remove this template message)

Sequential quadratic programming (SQP) is an iterative method for constrained nonlinear optimization. SQP methods are used on mathematical problems for which the objective function and the constraints are twice continuously differentiable.

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}}&b(x)\geq 0\\&c(x)=0.\end{array}}}$

The Lagrangian for this problem is^[1]

${\displaystyle {\mathcal {L}}(x,\lambda ,\sigma )=f(x)-\lambda b(x)-\sigma c(x),}$

where ${\displaystyle \lambda }$ and ${\displaystyle \sigma }$ are Lagrange multipliers. At an iterate ${\displaystyle x_{k}}$, a basic sequential quadratic programming algorithm defines an appropriate search direction ${\displaystyle d_{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.} &b(x_{k})+\nabla b(x_{k})^{T}d\geq 0\\&c(x_{k})+\nabla c(x_{k})^{T}d=0.\end{array}}}$

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.

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

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

This applied mathematics-related article is a stub. You can help Wikipedia by .

• v
• t