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:

${\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 Lagrange multipliers.

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.

• v
• t
• e

Optimization: Algorithms, methods, and heuristics

Unconstrained nonlinear

Functions Golden-section search Powell's method Line search Nelder–Mead method Successive parabolic interpolation Gradients Convergence Trust region Wolfe conditions Quasi–Newton Berndt–Hall–Hall–Hausman Broyden–Fletcher–Goldfarb–Shanno and L-BFGS Davidon–Fletcher–Powell Symmetric rank-one (SR1) Other methods Conjugate gradient Gauss–Newton Gradient Mirror Levenberg–Marquardt Powell's dog leg method Truncated Newton Hessians Newton's method

Constrained nonlinear
General Barrier methods Penalty methods Differentiable Augmented Lagrangian methods Sequential quadratic programming Successive linear programming

Convex optimization
Convex minimization Cutting-plane method Reduced gradient (Frank–Wolfe) Subgradient method Linear and quadratic Interior point Affine scaling Ellipsoid algorithm of Khachiyan Projective algorithm of Karmarkar Basis-exchange Simplex algorithm of Dantzig Revised simplex algorithm Criss-cross algorithm Principal pivoting algorithm of Lemke

Combinatorial
Paradigms Approximation algorithm Dynamic programming Greedy algorithm Integer programming Branch and bound/cut Graph algorithms Minimum spanning tree Borůvka Prim Kruskal Shortest path Bellman–Ford SPFA Dijkstra Floyd–Warshall Network flows Dinic Edmonds–Karp Ford–Fulkerson Push–relabel maximum flow

Metaheuristics
Evolutionary algorithm Hill climbing Local search Parallel metaheuristics Simulated annealing Spiral optimization algorithm Tabu search

• Software

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

• v
• t
• e