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.

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

The Lagrangian for this problem is

$\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:

$\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^2_{xx} \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^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)^Td + \tfrac{1}{2} d^T \nabla^2_{xx} \mathcal{L}(x_k, \lambda_k, \sigma_k) d \\ \mathrm{s.t.} & h(x_k) + \nabla h(x_k)^Td \ge 0 \\ & g(x_k) + \nabla g(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.

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.

## 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.
• LabVIEW
• KNITRO (C, C++, C#, Java, Python, Julia, Fortran)
• NPSOL (Fortran)
• SNOPT (Fortran)
• NLPQL (Fortran)
• MATLAB
• SuanShu (Java)