Interior-point method: Difference between revisions

Revision as of 11:13, 10 December 2023

Revision as of 13:53, 12 December 2023

Line 159:

:<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.]]

== Types of Convex Programs Solvable via Interior-Point Methods ==

== 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 program]]s ===

* [[Linear programming]]: given a program of the form: '''minimize ''c''^T''x'' s.t. ''Ax'' ≤ ''b''''', we can apply path-following 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}}

Given a program of the form: '''minimize ''c''^T''x'' s.t. ''Ax'' ≤ ''b''''', we can apply path-following methods with the barrier

* [[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-following 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''²).

<math display="block">b(x) := -\sum_{j=1}^m \ln(b_j - a_j^T x).</math>

*''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''²).

*The [[Linear programming]]: given a program of the form: '''minimize ''c''^T''x'' s.t. ''Ax'' ≤ ''b''''', we can apply path-following methods with the barrierfunction <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מNewton 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}}

*[[Geometric programming]]: we are given a problem with objective function '''''f''₀(x)=sum''_i c_i0'' exp(''a_i''^T''x'')''', and constraints '''''f_j''(''x'')=sum''_i c_ij'' exp(''a_i''^T''x'') ≤ ''d_j'' for ''j'' in 1,...,''m''''' '''and ''i'' in 1,...,''k'''''. There is a self-concordant barrier with parameter 2''k''+''m''. The path-following method has Newton complexity O(''mk''²+''k''³+''n''³) and total complexity O((''k+m'')^1/2[''mk''²+''k''³+''n''³]).

===[[Quadratically constrained quadratic program]]s===

*[[Semidefinite programming]].<ref name=":0" />{{Rp|___location=Sec.11}}

* [[Quadratically constrained quadratic program]]<nowiki/>ing: givenGiven 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 program]], we can apply path-following 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''²).

===L_p norm approximation===

*''Approximation in L_p norm'': we are givenConsider 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''²).

===[[Geometric program]]s===

*[[Geometric programming]]: we are givenConsider a problem with objective function '''''f''₀(x)=sum''_i c_i0'' exp(''a_i''^T''x'')''', and constraints '''''f_j''(''x'')=sum''_i c_ij'' exp(''a_i''^T''x'') ≤ ''d_j'' for ''j'' in 1,...,''m''''' '''and ''i'' in 1,...,''k'''''. There is a self-concordant barrier with parameter 2''k''+''m''. The path-following method has Newton complexity O(''mk''²+''k''³+''n''³) and total complexity O((''k+m'')^1/2[''mk''²+''k''³+''n''³]).

=== [[Semidefinite program]]s ===

Interior point methods can be used to solve semidefinite programs.<ref name=":0" />{{Rp|___location=Sec.11}}

==See also==