Sequential quadratic programming

From DDWiki

This article has been marked as incomplete and requiring attention. You can help DDWiki by expanding it.

Sequential quadratic programming, or called SQP, is an efficient and powerful algorithm to solve the nonlinear programming (NLP) problems. It is developed based on the concepts of:

To directly solve the first-order necessary condition (FOC) for the 2nd-order approximation of the Lagrangian function
Finding the solutions of FOC equations using Newton's method

The process can be seen as finding search direction toward optimum sequentially through minimizing the quadratic approximation of the Lagrangian function with the linear approximation of the constraints, as known as quadratic programming. This is the reason why the approach called sequential quadratic programming. The method is also known as projected Lagrangian method.

1 Derivation with equality constraint
2 Derivation with inequality constraint considered
3 Hessian matrix update
4 Iteration process
5 External links
6 References

Derivation with equality constraint

The original nonlinear programming problem with equality constraints to be solved is (inequality constraints will be considered later):

Minimize $f(\mathbf{x})$ (with respect to x)

Subject to

$\mathbf{h(x)=0}$

The Lagrangian function for this problem is:

$L=f(\mathbf{x})+\mathbf{\lambda}^T\mathbf{h(x)}$

where λ is the Lagrangian multiplier vector for the equality constraint h. The KKT first-order necessary conditions for a local optimum is:

$\nabla L=\mathbf{0} \Rightarrow \nabla f+\lambda^T \nabla \mathbf{h}=\mathbf{0}$

$\mathbf{h}=\mathbf{0}$

The set of these nonlinear equations is presented as:

$\mathbf{F(Y)=0}$

where

$\mathbf{F=[\nabla L, h]}^T$

$\mathbf{Y=[x, \lambda]}^T$

The problem can be solved using iteration function of Newton's method (root finding):

$\mathbf{Y}_{k+1}= \mathbf{Y}_k - \alpha_k(\nabla \mathbf{F}_{k}^{-1})^T \mathbf{F}_k$

Replace Y and F with the symbols in the original problem:

$\begin{bmatrix} \mathbf{x} \\ \mathbf{\lambda} \\ \end{bmatrix}_{k+1} = \begin{bmatrix} \mathbf{x} \\ \mathbf{\lambda} \\ \end{bmatrix}_k - \alpha_k \begin{bmatrix} \nabla^2 L & \nabla \mathbf{h}^T \\ \nabla \mathbf{h}^T & \mathbf{0} \\ \end{bmatrix}^{-1}_{k} \begin{bmatrix} \nabla L \\ \mathbf{h} \\ \end{bmatrix}_k$

The iteration process is to find the solutions satisfying the first-order condition of Lagrangian formulation. The derivation of the following section is to consider the NLP problem with both equality and inequality constraints included.

Derivation with inequality constraint considered

When inequality constraints are also considered, the formulation of the NLP problem is given by:

Minimize $f(\mathbf{x})$ (with respect to x)

Subject to

$\mathbf{h(x)=0}$

$\mathbf{g(x)\leq0}$

The NLP formulation can be converted into a Lagrangian augment function form:

$L=f(\mathbf{x})+\mathbf{\lambda}^T\mathbf{h(x)}+ \mathbf{\mu}^T\mathbf{g(x)}$

where λ and μ are the Lagrangian multiplier vectors for the equality constraints h and the inequality constraints g. The correspondent QP problem from is expressed as:

Minimize

$Q(s)= \nabla f^T \mathbf{s}+\frac{1}{2}\mathbf{s}^T (\nabla^2L) \mathbf{s}$

subject to

$\nabla \mathbf{g}^T \mathbf{s}+ \mathbf{g} \le \mathbf{0}$

$\nabla \mathbf{h}^T \mathbf{s}+ \mathbf{h} = \mathbf{0}$

To be noticed, the active inequality constraint strategy, e.g. applying specific scaling parameters to h and g terms in the QP linear constraints, is usually used to insure that linearized constraints do not cut off the feasible region completely. The details can be found in the reference.

Through solving the above quadratic programming problem, the search direction s is determined. Then the problem becomes a one-dimensional search problem, which can be solved using exterior penalty function method, as:

Minimize

$\phi = f(\mathbf{x})+\sum^{m}_{j=1}\lambda_{j} \max(0,g_j(\mathbf{x})) + \sum^{p}_{k=1}\mu_{k} |h_k(\mathbf{x})|$

where

$\mathbf{x}^{q+1}=\mathbf{x}^{q}+ \alpha \mathbf{s}$ where s is obtained by QP process above

$\qquad \lambda_j^{1}=|\lambda_j^{0}|$ for first iteration (q=1)

$\qquad \lambda_j^{q+1}= \max(|\lambda_j^q|,\frac{1}{2}(\lambda_j^q,|\lambda_j^q|)$ for subsequent iterations (q>1)

$\qquad j=1,2,...,m+p$

It can be seen that the final formulation results an one-dimensional search problem.

Hessian matrix update

During the iteration process, the Hessian matrix of the Lagrangian function ( $\nabla^2L$ ) needs to be updated for finding search direction through quadratic programming. The most popular and useful method to generate an approximate Hessian matrix is BFGS method.

Iteration process

The iteration procedure is described in follows:

Starting point with x=x⁰
Set Hessian matrix H⁰ = identity matrix I
Solve the QP subprogram to find search direction s
Solve the unconstrained exterior penalty function of finding α as one dimensional minimization problem
Update x^new = x + α s
Convergence check

If yes, go exit

If no, update Hessian matrix H and go back to step 3

External links

DONLP2 is an open-sourced code of implementing SQP algorithm. The code is available (Fortran 77, F90 and ANSI-C versions) through the request to the author.
Matlab Optimization Toolbox is a commercial software package which includes SQP algorithm to solve the NLP problems.
SNOPT is a software package for solving large-scale optimization problems using SQP with updated features.

References

G.N. Vanderplaats, Numerical Optimization techniques for Engineering Design with Applications, 1984, McGraw-Hill Inc.
P.Y. Papalambros and D.J. Wilde, Principles of Optimal Design: Modeling and Computation, 1988, Cambridge University Press.
S.S. Rao, Engineering Optimization: Theory and Practice, 1996, 3rd Ed., John Wiley & Sons, Inc.

Retrieved from "http://ddl.me.cmu.edu/ddwiki/index.php/Sequential_quadratic_programming"

Categories: Incomplete | Optimization