Sequential quadratic programming

Sequential quadratic programming (SQP) is an iterative method for nonlinear optimization. SQP methods are used on problems for which the objective function and the constraints are twice continuously differentiable.

SQP methods solve a sequence of optimization subproblems, each 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. SQP methods have been implemented in a many packages, including NPSOL, NLPQL, OPSYC, OPTIMA, MATLAB, and SQP.

Algorithm basics

Consider a nonlinear programming problem of the form:

$\begin{array}{rl} \min\limits_{x} & f(x) \\ \mbox{s.t.} & b(x) \ge 0 \\ & c(x) = 0. \end{array}$

The Lagrangian for this problem is

$\mathcal{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

$\begin{array}{rl} \min\limits_{d} & \mathcal{L}(x_k,\lambda_k,\sigma_k) + \nabla \mathcal{L}(x_k,\lambda_k,\sigma_k)^Td + \tfrac{1}{2} d^T \nabla_{xx}^2 \mathcal{L}(x_k,\lambda_k,\sigma_k) d \\ \mathrm{s.t.} & b(x_k) + \nabla b(x_k)^Td \ge 0 \\ & c(x_k) + \nabla c(x_k)^T d = 0. \end{array}$

See also

• Sequential linear programming
• Secant method
• Newton's method

References

• Bonnans, J. Frédéric; Gilbert, J. Charles; Lemaréchal, Claude; Sagastizábal, Claudia A. (2006). Numerical optimization: Theoretical and practical aspects. Universitext (Second revised ed. of translation of 1997 French ed.). Berlin: Springer-Verlag. pp. xiv+490. doi:10.1007/978-3-540-35447-5. ISBN 3-540-35445-X. MR2265882. http://www.springer.com/mathematics/applications/book/978-3-540-35445-1. 
• Cottle, Richard W.; Pang, Jong-Shi; Stone, Richard E. (1992). The linear complementarity problem. Computer Science and Scientific Computing. Boston, MA: Academic Press, Inc.. pp. xxiv+762 pp.. ISBN 0-12-192350-9. MR1150683. 
• Jorge Nocedal and Stephen J. Wright (2006). Numerical Optimization. Springer.. ISBN 0-387-30303-0. http://www.ece.northwestern.edu/~nocedal/book/num-opt.html. 

External links

• Sequential Quadratic Programming