GeezerVison

GeezerVison is showing en.wikipedia.org — Sequential linear-quadratic programming - Wikipedia

This article needs more citations. 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 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{matrix} min_{x} & f (x) \\ s.t. & b (x) \geq 0 \\ c (x) = 0. \end{matrix}

The Lagrangian for this problem is^[1]

ℒ (x, λ, σ) = f (x) - λ^{T} b (x) - σ^{T} c (x),

where $λ \geq 0$ and $σ$ are Lagrange multipliers.

LP phase

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

\begin{matrix} min_{d} & f (x_{k}) + \nabla f (x_{k})^{T} d \\ s . t . & b (x_{k}) + \nabla b (x_{k})^{T} d \geq 0 \\ c (x_{k}) + \nabla c (x_{k})^{T} d = 0. \end{matrix}

Let $𝒜_{k}$ denote the active set at the optimum $d_{LP}^{*}$ of this problem, that is to say, the set of constraints that are equal to zero at $d_{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{matrix} min_{d} & f (x_{k}) + \nabla f (x_{k})^{T} d + \frac{1}{2} d^{T} \nabla_{x x}^{2} ℒ (x_{k}, λ_{k}, σ_{k}) d \\ s . t . & b_{𝒜_{k}} (x_{k}) + \nabla b_{𝒜_{k}} (x_{k})^{T} d = 0 \\ c_{𝒜_{k}} (x_{k}) + \nabla c_{𝒜_{k}} (x_{k})^{T} d = 0. \end{matrix}

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

Notes

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

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 adding missing information.

Retrieved from "https://en.wikipedia.org/w/index.php?title=Sequential_linear-quadratic_programming&oldid=1158740143"

Categories:

Hidden categories: