Interior-point method: Difference between revisions

Revision as of 11:24, 30 November 2023

Revision as of 11:49, 30 November 2023

Line 141:

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 NewtomNewtoמ steps for the path-following method is O(''mn''²), and the total runtime complexity is O(''m''^3/2 ''n''²).{{Clarify|reason=This is the cost for an approximate solution - not an exact solution. The text does not elaborate on this.|date=November 2023}}

* [[Quadratically constrained quadratic program]]<nowiki/>ing: given a program of the form: '''minimize d^Tx s.t. ''f_j''(''x'') := ''x''^T ''A_j x'' + ''b_j''^T''x'' + ''c_j'' ≤ 0 for all j in 1,...,''m''''', where all matrices ''A_j'' are [[Positive semidefinite matrices|positive-semidefinite]], we can apply path-folliwing methods with the barrier <math>b(x) := -\sum_{j=1}^m \ln(-f_j(x))</math>. It is a self-concordant barrier with parameter ''M''=''m''. The Newton complexity is O(''(m+n)n''²), and the total runtime complexity is O(''m''^1/2 (m+n) ''n''²).

*

==See also==