Sequential quadratic programming

Sequential quadratic programming (SQP) is one of the most popular and robust algorithms for nonlinear continuous optimization. The method is based on solving a series of subproblems designed to minimize 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. A number of packages (including NPSOL, NLPQL, OPSYC, OPTIMA, MATLAB, and SQP) are founded on this approach.

Algorithm basics

Consider a nonlinear programming problem of the form:

:$minlimits\_\{x\};\; f(x),;;\; mbox\{s.t.\};\; b(x)\; ge\; 0,;\; c(x)\; =\; 0.$

The Lagrangian for this problem is

:$L(x,lambda,sigma)\; =\; f(x)\; -\; lambda^Tb(x)\; -\; sigma^Tc(x),$

where $lambda$ and $sigma$ are Lagrange multipliers. 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 subproblem

:$minlimits\_\{d\};\; f(x\_k)\; +\; abla\; f(x\_k)^Td\; +\; frac\{1\}\{2\}\; d^T\; abla\_\{xx\}^2\; L(x\_k,lambda\_k,sigma\_k)\; d,;;\; mbox\{s.t.\};\; b(x\_k)\; +\; abla\; b(x\_k)^Td\; ge\; 0,;\; c(x\_k)\; +\; abla\; c(x\_k)^Td\; =\; 0.$

ee also

* Secant method
* Newton's method

External links

* [http://www.math.mtu.edu/~msgocken/ma5630spring2003/lectures/sqp1/sqp1.pdf Introduction to sequential quadratic programming]
* [http://www-fp.mcs.anl.gov/otc/Guide/OptWeb/continuous/constrained/nonlinearcon/section2_1_1.html Sequential Quadratic Programming]