Sequential quadratic programming (SQP) is an

iterative method In computational mathematics, an iterative method is a mathematical procedure that uses an initial value to generate a sequence of improving approximate solutions for a class of problems, in which the ''n''-th approximation is derived from the pre ...

for constrained nonlinear optimization. SQP methods are used on

mathematical Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...

problems for which the

objective function In mathematical optimization and decision theory, a loss function or cost function (sometimes also called an error function) is a function that maps an event or values of one or more variables onto a real number intuitively representing some "cos ...

and the constraints are twice

continuously differentiable In mathematics, a differentiable function of one real variable is a function whose derivative exists at each point in its domain. In other words, the graph of a differentiable function has a non- vertical tangent line at each interior point in ...

. 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 In numerical analysis, Newton's method, also known as the Newton–Raphson method, named after Isaac Newton and Joseph Raphson, is a root-finding algorithm which produces successively better approximations to the roots (or zeroes) of a real ...

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

to the first-order optimality conditions, or

Karush–Kuhn–Tucker conditions In mathematical optimization, the Karush–Kuhn–Tucker (KKT) conditions, also known as the Kuhn–Tucker conditions, are first derivative tests (sometimes called first-order necessary conditions) for a solution in nonlinear programming to be ...

, of the problem.

Algorithm basics

Consider a nonlinear programming problem of the form: :

\begin
\min\limits_ & f(x) \\
\mbox & b(x) \ge 0 \\
  & c(x) = 0.
\end

The

Lagrangian Lagrangian may refer to: Mathematics * Lagrangian function, used to solve constrained minimization problems in optimization theory; see Lagrange multiplier ** Lagrangian relaxation, the method of approximating a difficult constrained problem with ...

for this problem is :

\mathcal(x,\lambda,\sigma) = f(x) - \lambda b(x) - \sigma c(x),

where

\lambda

and

\sigma

are

Lagrange multipliers In mathematical optimization, the method of Lagrange multipliers is a strategy for finding the local maxima and minima of a function subject to equality constraints (i.e., subject to the condition that one or more equations have to be satisfied ...

. At an iterate

x_k

, a basic sequential quadratic programming algorithm defines an appropriate search direction

d_k

as a solution to the

quadratic programming Quadratic programming (QP) is the process of solving certain mathematical optimization problems involving quadratic functions. Specifically, one seeks to optimize (minimize or maximize) a multivariate quadratic function subject to linear constr ...

subproblem :

\begin \min\limits_ & f(x_k) + \nabla f(x_k)^Td + \tfrac d^T \nabla^2_ \mathcal(x_k, \lambda_k, \sigma_k) d \\
\mathrm & b(x_k) + \nabla b(x_k)^Td \ge 0 \\
  & c(x_k) + \nabla c(x_k)^T d = 0. \end

Note that the term

f(x_k)

in the expression above may be left out for the minimization problem, since it is constant under the

\min\limits_

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 MATLAB (an abbreviation of "MATrix LABoratory") is a proprietary multi-paradigm programming language and numeric computing environment developed by MathWorks. MATLAB allows matrix manipulations, plotting of functions and data, implementa ...

and

GNU Octave GNU Octave is a high-level programming language primarily intended for scientific computing and numerical computation. Octave helps in solving linear and nonlinear problems numerically, and for performing other numerical experiments using a lang ...

. 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 Laboratory Virtual Instrument Engineering Workbench (LabVIEW) is a system-design platform and development environment for a visual programming language from National Instruments. The graphical language is named "G"; not to be confused with G- ...

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

SuanShu
(Java)

Notes

References

* *

External links