<p>Consider a convex optimisation problem in the form</p>

<p><span class="math-container">$$\begin{align}
f_0(x_1, \ldots, x_n) &amp;\to \min \\
f_i(x_1, \ldots, x_n) &amp; \leq 0, \quad i = 1, \ldots, m
\end{align}$$</span></p>

<p>where <span class="math-container">$f_0, f_1, \dots, f_m$</span> are convex functions. Without loss of generality, we can assume that <span class="math-container">$f_0$</span> is linear.</p>

<p>Nesterov and Nemirovskii mention in their book "Interior point polynomial algorithms in convex programming" that there is an algorithm which is able to solve any convex program in polynomial time in the following sense. We want to have a solution within a relative accuracy <span class="math-container">$\varepsilon$</span> at the cost of <span class="math-container">$O(p(n,m) \ln (n/\varepsilon))$</span> computations of the values and <span class="math-container">$O(q(n,m) \ln(n/\varepsilon))$</span> computations of the subgradients. Then, for the ellipsoid method, it is claimed that </p>

<p><span class="math-container">$$p(n,m) = n^3 (m+ n), \qquad q(n,m) = n^2$$</span></p>

<p>At first glance, this seems to imply that a convex optimisation problem can be solved in polynomial time using the ellipsoid method (let us assume for simplicity that the oracles for computing the values and the subgradients require <span class="math-container">$O(1)$</span> time for the considered class of convex optimisation problems).</p>

<p>However, I totally don't understand, whether the <span class="math-container">$O(\cdot)$</span> expressions are somehow dependent on the functions <span class="math-container">$f_i$</span>, e.g., on their Hessians, or not. In this case, the complexity may have an exponential blowup due to curvature properties of the functions. Moreover, it is mysteriously claimed that "ellipsoid method doesn't work well in practice". There seems to be no consensus in the internet whether the answer to my question is affirmative or negative, see e.g. <a href="https://mathoverflow.net/q/92939/91764">this discussion</a> on MathOverflow.</p>

<p>I have searched on every book on convex optimisation I could find, and I have gotten an impression that this <span class="math-container">$O(\cdot)$</span> indeed depends on the problem, but could not find any clear confirmation of this guess. So my only hope is to directly ask people who are doing research in this field.</p>

<p>Interior point methods that have been developed later seem to explicitly account for the curvature using the notion of self-concordant barriers. But when people say that these methods are efficient in practice, they usually don't specify this on the level of complexity.</p>

CC BY-SA 4.0
2019-07-25T22:17:25.690Z
These issues (which can be subtle) are explained in detail in the book Geometric Algorithms and Combinatorial Optimization by Groetschel, Lovasz and Schrijver. The rough answer is that with the ellipsoid method 1) you only get an approximately feasible and approximately optimal solution, and 2) you need to know a ball of radius $R$ that contains the feasible region, and the running time also depends on  $\log R$. Ignoring the complexity of getting a gradient, there should be no other hidden dependencies.
Sasho Nikolov
CC BY-SA 4.0
2019-07-26T12:30:49.540Z
In my case, $R = \infty$, so my intuition is that barrier methods can work in some cases even when $R = \infty$. But this means there is no general theorem that regardless of $R$, there is a polynomial algorithm?
Sergey Dovgal
CC BY-SA 4.0
2019-07-26T13:38:08.613Z
by "barrier methods" I mean interior-point type methods which have been developed after ellipsoid method by Nesterov, Nemirovskii et. al.
Sergey Dovgal
CC BY-SA 4.0
2019-07-31T13:21:40.120Z
I think that's true, without some bound on $R$ there is no generic polynomial time guarantee. In many cases when the feasible region is unbounded you can still show apriori that if there exists a feasible solution, then there exists one of Euclidean norm at most $R$, where $R$ may depend on the bit complexity of the input. In that case you can just intersect the feasible region with the ball of radius $R$ centered at the origin.
Sasho Nikolov
<convex-optimization><complexity>
Is convex optimisation in P?
Sergey Dovgal
# Is convex optimisation in P?

(Asked by: username_0 on 2019-07-25)

Consider a convex optimisation problem in the form

$$\begin{align}
f\_0(x\_1, \ldots, x\_n) &\to \min \\
f\_i(x\_1, \ldots, x\_n) & \leq 0, \quad i = 1, \ldots, m
\end{align}$$

where $f\_0, f\_1, \dots, f\_m$ are convex functions. Without loss of generality, we can assume that $f\_0$ is linear.

Nesterov and Nemirovskii mention in their book "Interior point polynomial algorithms in convex programming" that there is an algorithm which is able to solve any convex program in polynomial time in the following sense. We want to have a solution within a relative accuracy $\varepsilon$ at the cost of $O(p(n,m) \ln (n/\varepsilon))$ computations of the values and $O(q(n,m) \ln(n/\varepsilon))$ computations of the subgradients. Then, for the ellipsoid method, it is claimed that

$$p(n,m) = n^3 (m+ n), \qquad q(n,m) = n^2$$

At first glance, this seems to imply that a convex optimisation problem can be solved in polynomial time using the ellipsoid method (let us assume for simplicity that the oracles for computing the values and the subgradients require $O(1)$ time for the considered class of convex optimisation problems).

However, I totally don't understand, whether the $O(\cdot)$ expressions are somehow dependent on the functions $f\_i$, e.g., on their Hessians, or not. In this case, the complexity may have an exponential blowup due to curvature properties of the functions. Moreover, it is mysteriously claimed that "ellipsoid method doesn't work well in practice". There seems to be no consensus in the internet whether the answer to my question is affirmative or negative, see e.g. [this discussion](https://mathoverflow.net/q/92939/91764) on MathOverflow.

I have searched on every book on convex optimisation I could find, and I have gotten an impression that this $O(\cdot)$ indeed depends on the problem, but could not find any clear confirmation of this guess. So my only hope is to directly ask people who are doing research in this field.

Interior point methods that have been developed later seem to explicitly account for the curvature using the notion of self-concordant barriers. But when people say that these methods are efficient in practice, they usually don't specify this on the level of complexity.

**Tags:** convex-optimization, complexity

> **Comments:**
> **username_1**: These issues (which can be subtle) are explained in detail in the book Geometric Algorithms and Combinatorial Optimization by Groetschel, Lovasz and Schrijver. The rough answer is that with the ellipsoid method 1) you only get an approximately feasible and approximately optimal solution, and 2) you need to know a ball of radius $R$ that contains the feasible region, and the running time also depends on  $\log R$. Ignoring the complexity of getting a gradient, there should be no other hidden dependencies.  
> **username_0**: In my case, $R = \infty$, so my intuition is that barrier methods can work in some cases even when $R = \infty$. But this means there is no general theorem that regardless of $R$, there is a polynomial algorithm?  
> **username_0**: by "barrier methods" I mean interior-point type methods which have been developed after ellipsoid method by Nesterov, Nemirovskii et. al.  
> **username_1**: I think that's true, without some bound on $R$ there is no generic polynomial time guarantee. In many cases when the feasible region is unbounded you can still show apriori that if there exists a feasible solution, then there exists one of Euclidean norm at most $R$, where $R$ may depend on the bit complexity of the input. In that case you can just intersect the feasible region with the ball of radius $R$ centered at the origin.  

---

## 0 answers

