Interior-point method: Difference between revisions

Revision as of 11:13, 30 November 2023

Revision as of 11:24, 30 November 2023

Line 137:

should be enforced at each step. This can be done by choosing appropriate <math>\alpha</math>:

:<math>(x,\lambda) \to (x + \alpha p_x, \lambda + \alpha p_\lambda).</math>[[File:Interior_Point_Trajectory.webm|center|thumb|400x400px|Trajectory of the iterates of ''x'' by using the interior point method.]]

== Special cases ==

Here are some special cases of convex programs, that can be solved efficiently by interior-point methods.<ref name=":0" />{{Rp|___location=Sec.10}}

* [[Linear programming]]: given a program of the form: minimize ''c''^T''x'' s.t. ''Ax'' ≤ ''b'', we can apply path-folliwing methods with the barrier <math>b(x) := -\sum_{j=1}^m \ln(b_j - a_j^T x)</math>. It is a self-concordant barrier with parameter ''M''=''m'' (the number of constraints). Therefore, the number of required Newtom steps is O(''mn''²), and the total runtime complexity is O(''m''^3/2 ''n''²).

==See also==

Line 147 ⟶ 152:

==References==

{{Reflist}}

== Bibliography ==

* {{cite book |last1=Bonnans |first1=J.&nbsp;Frédéric |last2=Gilbert |first2=J.&nbsp;Charles |last3=Lemaréchal |first3=Claude |authorlink3=Claude Lemaréchal |last4=Sagastizábal |first4=Claudia&nbsp;A. |author4-link=Claudia Sagastizábal |title=Numerical optimization: Theoretical and practical aspects |url=https://www.springer.com/mathematics/applications/book/978-3-540-35445-1 |edition=Second revised ed. of translation of 1997 <!-- ''Optimisation numérique: Aspects théoriques et pratiques'' --> French |series=Universitext |publisher=Springer-Verlag |___location=Berlin |year=2006 |pages=xiv+490 |isbn=978-3-540-35445-1 |doi=10.1007/978-3-540-35447-5 |mr=2265882}}

* {{cite book |title=Numerical Optimization |first=Jorge |last=Nocedal |author2=Stephen Wright |year=1999 |publisher=Springer |___location=New York, NY |isbn=978-0-387-98793-4}}

*{{Cite book | last1=Press | first1=WH | last2=Teukolsky | first2=SA | last3=Vetterling | first3=WT | last4=Flannery | first4=BP | year=2007 | title=Numerical Recipes: The Art of Scientific Computing | edition=3rd | publisher=Cambridge University Press | ___location=New York | isbn=978-0-521-88068-8 | chapter=Section 10.11. Linear Programming: Interior-Point Methods | chapter-url=http://apps.nrbook.com/empanel/index.html#pg=537}}

*{{cite book |title=Convex Optimization |last1=Boyd |first1=Stephen |last2=Vandenberghe |first2=Lieven |year=2004 |publisher=Cambridge University Press |url=https://web.stanford.edu/~boyd/cvxbook/bv_cvxbook.pdf}}

{{Optimization algorithms|convex}}