Interior-point method: Difference between revisions

Revision as of 10:45, 30 November 2023

Revision as of 10:47, 30 November 2023

Line 70:

+

O(1) \cdot \sqrt{M} \cdot \ln\left(\frac{M \text{Var}_G(c)}{\epsilon} + 1\right)

</math></blockquote>where the constant factor O(1) depends only on ''r'' and ''L'', and <math>O\text{Var}_G(1c) \cdot:= \sqrtmax_{Mx\in G} \cdotc^T x \ln\left(\frac{M}{1- \pi_min_{x^*_f}(\bar{x})in G} +c^T 1\right)x

</math>.

+

\text{Var}_G(c) := \max_{x\in G} c^T x - \min_{x\in G} c^T x

Overall, the overall Newton complexity of finding an ''ε''-approximate solution is at most

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

{{Under construction|placedby=Erel Segal}}