Content deleted Content added
Erel Segal (talk | contribs) |
Erel Segal (talk | contribs) |
||
Line 144:
* [[Quadratically constrained quadratic program]]<nowiki/>ing: given a program of the form: '''minimize d<sup>T</sup>x s.t. ''f<sub>j</sub>''(''x'') := ''x''<sup>T</sup> ''A<sub>j</sub> x'' + ''b<sub>j</sub>''<sup>T</sup>''x'' + ''c<sub>j</sub>'' ≤ 0 for all j in 1,...,''m''''', where all matrices ''A<sub>j</sub>'' 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''<sup>2</sup>), and the total runtime complexity is O(''m''<sup>1/2</sup> (m+n) ''n''<sup>2</sup>).
*''Approximation in L<sub>p</sub> norm'': we are given a problem of the form '''minimize sum<sub>''j''</sub> |''v<sub>j</sub>''-''u<sub>j</sub>''<sup>T</sup>''x''|<sup>''p''</sup>''', where 1<''p''<∞, ''u<sub>j</sub>'' are vectors and ''v<sub>j</sub>'' 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''<sup>2</sup>), and the total runtime complexity is O(''m''<sup>1/2</sup> (m+n) ''n''<sup>2</sup>).
*[[Geometric programming]]: we are given a problem with objective function '''''f''<sub>0</sub>(x)=sum''<sub>i</sub> c<sub>i0</sub>'' exp(''a<sub>i</sub>''<sup>T</sup>''x'')''', and constraints '''''f<sub>j</sub>''(''x'')=sum''<sub>i</sub> c<sub>ij</sub>'' exp(''a<sub>i</sub>''<sup>T</sup>''x'') ≤ ''d<sub>j</sub>'' 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''<sup>2</sup>+''k''<sup>3</sup>+''n''<sup>3</sup>) and total complexity O((''k+m'')<sup>1/2</sup>[''mk''<sup>2</sup>+''k''<sup>3</sup>+''n''<sup>3</sup>]).
==See also==
| |||