Content deleted Content added
Erel Segal (talk | contribs) |
Erel Segal (talk | contribs) |
||
Line 145:
*''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>]).
*[[Semidefinite programming]].<ref name=":0" />{{Rp|___location=Sec.11}}
==See also==
| |||