Sequential linear-quadratic programming

Sequential linear-quadratic programming (SLQP) is an iterative method for nonlinear optimization problems where objective function and constraints are twice continuously differentiable. Similarly to sequential quadratic programming (SQP), SLQP proceeds by solving a sequence of optimization subproblems. The difference between the two approaches is that:

• in SQP, each subproblem is a quadratic program, with a quadratic model of the objective subject to a linearization of the constraints
• in SLQP, two subproblems are solved at each step: a linear program (LP) used to determine an active set, followed by an equality-constrained quadratic program (EQP) used to compute the total step

This decomposition makes SLQP suitable to large-scale optimization problems, for which efficient LP and EQP solvers are available, these problems being easier to scale than full-fledged quadratic programs.

It may be considered related to, but distinct from, quasi-Newton methods.

Algorithm basics

Consider a nonlinear programming problem of the form:

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

The Lagrangian for this problem is

${ℒ}(x,\lambda ,\sigma )=f(x)-{\lambda }^{T}b(x)-{\sigma }^{T}c(x),$

where $\lambda \ge 0$ and $\sigma$ are Lagrange multipliers.

LP phase

In the LP phase of SLQP, the following linear program is solved:

$\begin{array}{rl}\min {}_d& f(x_k)+\mathrm{\nabla }f(x_k{)}^{T}d\\ \mathrm{s}\mathrm{.}\mathrm{t}\mathrm{.}& b(x_k)+\mathrm{\nabla }b(x_k{)}^{T}d\ge 0\\ & c(x_k)+\mathrm{\nabla }c(x_k{)}^{T}d=0.\end{array}$

Let ${{𝒜}}_k$ denote the active set at the optimum $d_{\text{LP}}^{*}$ of this problem, that is to say, the set of constraints that are equal to zero at $d_{\text{LP}}^{*}$. Denote by $b_{{{𝒜}}_k}$ and $c_{{{𝒜}}_k}$ the sub-vectors of $b$ and $c$ corresponding to elements of ${{𝒜}}_k$.

EQP phase

In the EQP phase of SLQP, the search direction $d_k$ of the step is obtained by solving the following equality-constrained quadratic program:

$\begin{array}{rl}\min {}_d& f(x_k)+\mathrm{\nabla }f(x_k{)}^{T}d+\frac{1}{2}{d}^T\underset{xx}{\overset{2}{\mathrm{\nabla }}}{ℒ}(x_k,{\lambda }_k,{\sigma }_k)d\\ \mathrm{s}\mathrm{.}\mathrm{t}\mathrm{.}& b_{{{𝒜}}_k}(x_k)+\mathrm{\nabla }{b}_{{{𝒜}}_k}(x_k{)}^{T}d=0\\ & c_{{{𝒜}}_k}(x_k)+\mathrm{\nabla }{c}_{{{𝒜}}_k}(x_k{)}^{T}d=0.\end{array}$

Note that the term $f(x_k)$ in the objective functions above may be left out for the minimization problems, since it is constant.

See also

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

References

• 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.