Interior-point method: Difference between revisions

Revision as of 10:50, 30 November 2023

Revision as of 10:58, 30 November 2023

Line 73:

</math>, and <math>\bar{x}</math> is some point in the interior of ''G''.

Overall, the overall Newton complexity of finding an ''ε''-approximate solution is at most<blockquote><math>O(1) \cdot \sqrt{M} \cdot \ln\left(\frac{V}{\varepsilon} + 1\right) </math>, where V is some problem-dependent constant: <math>V = \frac{\text{Var}_G(c)}{1-\pi_{x^*_f(\bar{x})}}

</math>.</blockquote>Each Newton step takes O(''n''³) arithmetic operations.

=== Practical considerations ===

<math>O(1) \cdot \sqrt{M} \cdot \ln\left(\frac{V}{\varepsilon} + 1\right) </math>, where V is some problem-dependent constant: <math>V = \frac{\text{Var}_G(c)}{1-\pi_{x^*_f(\bar{x})}}

The theoretic guarantees assume that the penalty parameter is increased at the rate <math>\left(1+r/\sqrt{M}\right)</math>, so the number of required Newton steps is <math>O(\sqrt{M})</math>. In practice, it is possible to increase the penalty parameter much faster; these are called ''long step'' techniques.<ref name=":0" />{{Rp|___location=Sec.4.6}}

</math>.

{{Under construction|placedby=Erel Segal}}

==Primal-dual methods==