HOME

TheInfoList



OR:

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
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- ...
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 o ...
, of the problem.


Algorithm basics

Consider a
nonlinear programming In mathematics, nonlinear programming (NLP) is the process of solving an optimization problem where some of the constraints or the objective function are nonlinear. An optimization problem is one of calculation of the extrema (maxima, minima or sta ...
problem of the form: :\begin \min\limits_ & f(x) \\ \mbox & b(x) \ge 0 \\ & c(x) = 0. \end The Lagrangian 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 constra ...
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, implementatio ...
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 langu ...
. There also exist numerous software libraries, including open source: *
SciPy SciPy (pronounced "sigh pie") is a free and open-source Python library used for scientific computing and technical computing. SciPy contains modules for optimization, linear algebra, integration, interpolation, special functions, FFT, signa ...
(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-cod ...
*
KNITRO Artelys Knitro is a commercial software package for solving large scale nonlinear mathematical optimization problems. KNITRO – (the original solver name) short for "Nonlinear Interior point Trust Region Optimization" (the "K" is silent) – wa ...
KNITRO User Guide: Algorithms
/ref> (C, C++, C#, Java, Python, Julia, Fortran) * NPSOL (Fortran) * SNOPT (Fortran) * NLPQL (Fortran) *
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, implementatio ...

SuanShu
(Java)


See also

*
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- ...
*
Secant method In numerical analysis, the secant method is a root-finding algorithm that uses a succession of roots of secant lines to better approximate a root of a function ''f''. The secant method can be thought of as a finite-difference approximation o ...


Notes


References

* *


External links


Sequential Quadratic Programming at NEOS guide
Optimization algorithms and methods {{Mathapplied-stub