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

Notes

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

References


This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.