Sequential linear-quadratic programming (SLQP) is an

iterative method In computational mathematics, an iterative method is a mathematical procedure that uses an initial value to generate a sequence of improving approximate solutions for a class of problems, in which the ''n''-th approximation is derived from the pre ...

for nonlinear optimization problems where

objective function In mathematical optimization and decision theory, a loss function or cost function (sometimes also called an error function) is a function that maps an event or values of one or more variables onto a real number intuitively representing some "cos ...

and constraints are twice

continuously differentiable In mathematics, a differentiable function of one real variable is a function whose derivative exists at each point in its domain. In other words, the graph of a differentiable function has a non- vertical tangent line at each interior point in ...

. Similarly to

sequential quadratic programming Sequential quadratic programming (SQP) is an iterative method for constrained nonlinear optimization. SQP methods are used on mathematical problems for which the objective function and the constraints are twice continuously differentiable. SQP me ...

(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 Quadratic programming (QP) is the process of solving certain mathematical optimization problems involving quadratic functions. Specifically, one seeks to optimize (minimize or maximize) a multivariate quadratic function subject to linear constr ...

, 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 Linear programming (LP), also called linear optimization, is a method to achieve the best outcome (such as maximum profit or lowest cost) in a mathematical model whose requirements are represented by linear relationships. Linear programming is ...

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

Algorithm basics

Consider a nonlinear programming problem of the form: :

\begin
\min\limits_ & f(x) \\
\mbox & b(x) \ge 0 \\
  & c(x) = 0.
\end

The Lagrangian for this problem is :

\mathcal(x,\lambda,\sigma) = f(x) - \lambda^T b(x) - \sigma^T c(x),

where

\lambda \ge 0

and

\sigma

are

Lagrange multipliers In mathematical optimization, the method of Lagrange multipliers is a strategy for finding the local maxima and minima of a function subject to equality constraints (i.e., subject to the condition that one or more equations have to be satisfied ...

LP phase

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

\begin 
\min\limits_ & f(x_k) + \nabla f(x_k)^Td\\
\mathrm & b(x_k) + \nabla b(x_k)^Td \ge 0 \\
  & c(x_k) + \nabla c(x_k)^T d = 0. \end

Let

_k

denote the ''active set'' at the optimum

d^*_

of this problem, that is to say, the set of constraints that are equal to zero at

d^*_

. Denote by

b_

and

c_

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 
\min\limits_ & f(x_k) + \nabla f(x_k)^Td + \tfrac d^T \nabla_^2 \mathcal(x_k,\lambda_k,\sigma_k) d\\
\mathrm & b_(x_k) + \nabla b_(x_k)^Td = 0 \\
  & c_(x_k) + \nabla c_(x_k)^T d = 0. \end

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

References

* Optimization algorithms and methods {{Mathapplied-stub

Algorithm basics

LP phase

EQP phase

See also

Notes

References