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:
The Lagrangian for this problem is[1]
where and are Lagrange multipliers.
LP phase
In the LP phase of SLQP, the following linear program is solved:
Let denote the active set at the optimum of this problem, that is to say, the set of constraints that are equal to zero at . Denote by and the sub-vectors of and corresponding to elements of .
EQP phase
In the EQP phase of SLQP, the search direction of the step is obtained by solving the following equality-constrained quadratic program:
Note that the term 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
- ^ 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.
- v
- t
- e
Unconstrained nonlinear | |||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|
|
![Graph of a strictly concave quadratic function with unique maximum.](http://upload.wikimedia.org/wikipedia/commons/thumb/7/72/Max_paraboloid.svg/150px-Max_paraboloid.svg.png)
|
|
|
![]() | This applied mathematics-related article is a stub. You can help Wikipedia by expanding it. |
- v
- t
- e