Sequential linear-quadratic programming

This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed. Find sources: "Sequential linear-quadratic programming" – news · newspapers · books · scholar · JSTOR (November 2017) (Learn how and when to remove this message)

Sequential linear-quadratic programming (SLQP) is an

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

Algorithm basics

Consider a nonlinear programming problem of the form:

${\displaystyle {\begin{array}{rl}\min \limits _{x}&f(x)\\{\mbox{s.t.}}&b(x)\geq 0\\&c(x)=0.\end{array}}}$

The Lagrangian for this problem is^[1]

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

where ${\displaystyle \lambda \geq 0}$ and ${\displaystyle \sigma }$ are

LP phase

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

${\displaystyle {\begin{array}{rl}\min \limits _{d}&f(x_{k})+\nabla f(x_{k})^{T}d\\\mathrm {s.t.} &b(x_{k})+\nabla b(x_{k})^{T}d\geq 0\\&c(x_{k})+\nabla c(x_{k})^{T}d=0.\end{array}}}$

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

EQP phase

In the EQP phase of SLQP, the search direction ${\displaystyle d_{k}}$ of the step is obtained by solving the following equality-constrained quadratic program:

${\displaystyle {\begin{array}{rl}\min \limits _{d}&f(x_{k})+\nabla f(x_{k})^{T}d+{\tfrac {1}{2}}d^{T}\nabla _{xx}^{2}{\mathcal {L}}(x_{k},\lambda _{k},\sigma _{k})d\\\mathrm {s.t.} &b_{{\cal {A}}_{k}}(x_{k})+\nabla b_{{\cal {A}}_{k}}(x_{k})^{T}d=0\\&c_{{\cal {A}}_{k}}(x_{k})+\nabla c_{{\cal {A}}_{k}}(x_{k})^{T}d=0.\end{array}}}$

Note that the term ${\displaystyle 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

Notes

References

• Jorge Nocedal and Stephen J. Wright (2006). Numerical Optimization. Springer.
  ISBN 0-387-30303-0
  .

This applied mathematics-related article is a stub. You can help Wikipedia by expanding it.

• v
• t
• e