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:

$\min \limits _{x}\;f(x),\;\;{\mbox{s.t.}}\;b(x)\geq 0,\;c(x)=0.$

The Lagrangian for this problem is

$L(x,\lambda ,\sigma )=f(x)-\lambda ^{T}b(x)-\sigma ^{T}c(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

<math>\min\limits_{d}\; f

See also

• Secant method
• Newton's method

External links

• Introduction to sequential quadratic programming
• Sequential Quadratic Programming