Sequential linear-quadratic programming (SLQP) is an

iterative method In computational mathematics, an iterative method is a Algorithm, mathematical procedure that uses an initial value to generate a sequence of improving approximate solutions for a class of problems, in which the ''i''-th approximation (called an " ...

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 "cost ...

and constraints are twice

continuously differentiable In mathematics, a differentiable function of one Real number, real variable is a Function (mathematics), function whose derivative exists at each point in its Domain of a function, domain. In other words, the Graph of a function, graph of a differ ...

. Similarly to

sequential quadratic programming Sequential quadratic programming (SQP) is an iterative method for constrained nonlinear optimization, also known as Lagrange-Newton method. SQP methods are used on mathematical problems for which the objective function and the constraints are twi ...

(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 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 and objective are represented by linear relationships. Linear ...

(LP) used to determine an

active set In mathematical optimization, the active-set method is an algorithm used to identify the active constraints in a set of inequality constraints. The active constraints are then expressed as equality constraints, thereby transforming an inequalit ...

, 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: :

\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 equation constraints (i.e., subject to the condition that one or more equations have to be satisfie ...

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