Sequential linear-quadratic programming

This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed. Find sources: "Sequential linear-quadratic programming" – news · newspapers · books · scholar · JSTOR (November 2017) (Learn how and when to remove this message)

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.

Consider a nonlinear programming problem of the form:

min x f ( x ) s.t. b ( x ) ≥ 0 c ( x ) = 0. {\displaystyle {\begin{array}{rl}\min \limits _{x}&f(x)\\{\mbox{s.t.}}&b(x)\geq 0\\&c(x)=0.\end{array}}}

The Lagrangian for this problem is^[1]

L ( x , λ , σ ) = f ( x ) − λ T b ( x ) − σ T c ( x ) , {\displaystyle {\mathcal {L}}(x,\lambda ,\sigma )=f(x)-\lambda ^{T}b(x)-\sigma ^{T}c(x),}

where λ ≥ 0 {\displaystyle \lambda \geq 0} and σ {\displaystyle \sigma } are Lagrange multipliers.

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

min d f ( x k ) + ∇ f ( x k ) T d s . t . b ( x k ) + ∇ b ( x k ) T d ≥ 0 c ( x k ) + ∇ c ( x k ) T d = 0. {\displaystyle {\begin{array}{rl}\min \limits _{d}&f(x_{k})+\nabla f(x_{k})^{T}d\\\mathrm {s.t.} &b(x_{k})+\nabla b(x_{k})^{T}d\geq 0\\&c(x_{k})+\nabla c(x_{k})^{T}d=0.\end{array}}}

Let A k {\displaystyle {\cal {A}}_{k}} denote the active set at the optimum d LP ∗ {\displaystyle d_{\text{LP}}^{*}} of this problem, that is to say, the set of constraints that are equal to zero at d LP ∗ {\displaystyle d_{\text{LP}}^{*}} . Denote by b A k {\displaystyle b_{{\cal {A}}_{k}}} and c A k {\displaystyle c_{{\cal {A}}_{k}}} the sub-vectors of b {\displaystyle b} and c {\displaystyle c} corresponding to elements of A k {\displaystyle {\cal {A}}_{k}} .

In the EQP phase of SLQP, the search direction d k {\displaystyle d_{k}} of the step is obtained by solving the following equality-constrained quadratic program:

min d f ( x k ) + ∇ f ( x k ) T d + 1 2 d T ∇ x x 2 L ( x k , λ k , σ k ) d s . t . b A k ( x k ) + ∇ b A k ( x k ) T d = 0 c A k ( x k ) + ∇ c A k ( x k ) T d = 0. {\displaystyle {\begin{array}{rl}\min \limits _{d}&f(x_{k})+\nabla f(x_{k})^{T}d+{\tfrac {1}{2}}d^{T}\nabla _{xx}^{2}{\mathcal {L}}(x_{k},\lambda _{k},\sigma _{k})d\\\mathrm {s.t.} &b_{{\cal {A}}_{k}}(x_{k})+\nabla b_{{\cal {A}}_{k}}(x_{k})^{T}d=0\\&c_{{\cal {A}}_{k}}(x_{k})+\nabla c_{{\cal {A}}_{k}}(x_{k})^{T}d=0.\end{array}}}

Note that the term f ( x k ) {\displaystyle f(x_{k})} in the objective functions above may be left out for the minimization problems, since it is constant.

• Newton's method
• Secant method
• Sequential linear programming
• Sequential quadratic programming

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