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.

## Contents

* 1 Algorithm basics
* 1.1 LP phase
* 1.2 EQP phase
* 2 See also
* 3 Notes
* 4 References

## Algorithm basics

Consider a nonlinear programming problem of the form:

min⁡xf(x)s.t.b(x)≥0c(x)=0.

The Lagrangian for this problem is[1]

ℒ(x,λ,σ)=f(x)−λTb(x)−σTc(x),

where λ≥0 and σ are Lagrange multipliers.

### LP phase

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

min⁡df(xk)+∇f(xk)Tds.t.b(xk)+∇b(xk)Td≥0c(xk)+∇c(xk)Td=0.

Let 𝒜k denote the active set at the optimum dLP* of this problem, that is to say, the set of constraints that are equal to zero at dLP*. 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 dk of the step is obtained by solving the following equality-constrained quadratic program:

min⁡df(xk)+∇f(xk)Td+12dT∇xx2ℒ(xk,λk,σk)ds.t.b𝒜k(xk)+∇b𝒜k(xk)Td=0c𝒜k(xk)+∇c𝒜k(xk)Td=0.

Note that the term f(xk) 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

1. ↑ 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.

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

* v
* t
* e

Optimization: Algorithms, methods, and heuristics

Unconstrained nonlinear

| … functions|

* Golden-section search
* Interpolation methods
* Line search
* Nelder–Mead method
* Successive parabolic interpolation

|

… and 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|

* Gauss–Newton
* Gradient
* Levenberg–Marquardt
* Conjugate gradient
* Truncated Newton

… and Hessians|

* Newton's method

Optimization computes maxima and minima.

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

|

* Bellman–Ford
* Dijkstra
* Floyd–Warshall

Network flows|

* Dinic
* Edmonds–Karp
* Ford–Fulkerson
* Push–relabel maximum flow

Metaheuristics

* Evolutionary algorithm
* Hill climbing
* Local search
* Simulated annealing
* Tabu search

* Software

0.00

(0 votes)

Original source: https://en.wikipedia.org/wiki/Sequential linear-quadratic programming. Read more

|

Retrieved from "https://handwiki.org/wiki/index.php?title=Sequential_linear-quadratic_programming&oldid=248227"
*[v]: View this template
*[t]: Discuss this template
*[e]: Edit this template