Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Sequential linear-quadratic programming
open-in-new
<h2 id="algorithm-basics">Algorithm basics</h2> <p>Consider a <a href="/facts/Nonlinear_programming/cSXGuX2m">nonlinear programming</a> problem of the form: </p> 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}}} <p>The Lagrangian for this problem is<a class="footnote-ref" id="fnref:1" href="#fn:1"><sup>1</sup></a> </p> 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),} <p>where λ ≥ 0 {\displaystyle \lambda \geq 0} and σ {\displaystyle \sigma } are <a href="/facts/Lagrange_multipliers/U5mSI5YP">Lagrange multipliers</a>. </p> <h3>LP phase</h3> <p>In the LP phase of SLQP, the following linear program is solved: </p> 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}}} <p>Let A k {\displaystyle {\cal {A}}_{k}} denote the <i>active set</i> 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}} . </p> <h3>EQP phase</h3> <p>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: </p> 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}}} <p>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. </p> <h2 id="see-also">See also</h2> <ul><li><a href="/facts/Newton%2527s_method/VlRhI2FL">Newton's method</a></li> <li><a href="/facts/Secant_method/tkNV8Rzk">Secant method</a></li> <li><a href="/facts/Sequential_linear_programming/UtYaIG4R">Sequential linear programming</a></li> <li><a href="/facts/Sequential_quadratic_programming/3QUzYBps">Sequential quadratic programming</a></li></ul> <h2 id="notes">Notes</h2> <ul><li>Jorge Nocedal and Stephen J. Wright (2006). <a href="http://www.ece.northwestern.edu/~nocedal/book/num-opt.html"><i>Numerical Optimization</i></a>. Springer. <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 0-387-30303-0.</li></ul> <h2 id="references">References</h2> <ol> <li id="fn:1"><p>Jorge Nocedal and Stephen J. Wright (2006). Numerical Optimization. Springer. ISBN 0-387-30303-0. <a href="0-387-30303-0" target="_blank">0-387-30303-0</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li> </ol>