Interior-point method: Difference between revisions

Revision as of 11:52, 30 November 2023

Revision as of 11:55, 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-folliwingfollowing 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 Newtoמ 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-folliwingfollowing 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''²).

*''Approximation in L_p norm'': we are given a problem of the form '''minimize sum_''j'' |''v_j''-''u_j''^T''x''|^''p''''', where 1<''p''<∞, ''u_j'' are vectors and ''v_j'' are scalars. After converting to the standard form, we can apply path-following methods with a self-concordant barrier with parameter ''M''=4''m''. The Newton complexity is O(''(m+n)n''²), and the total runtime complexity is O(''m''^1/2 (m+n) ''n''²).

*

==See also==