Is convex optimisation in P?

Question

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

Answer 1

In 1998, Michel X. Goemans gave an ICM talk, in which, he addressed this issue:"Semidefinite programs can be solved(or more precisely, approximated) in polynomial-time within any specific accuracy either by the ellipsoid algorithm or more efficiently through interior-point algorithms...The above algorithms produce a strictly feasible solution(or slightly infeasible for some versions of the ellipsoid algorithm) and, in fact, the problem of deciding whether a semidefinite program is feasible(exactly) is still open. A special case of semidefinite programming feasibility is the square-root-sum problem. The complexity of this problem is still open." http://garden.irmacs.sfu.ca/op/complexity_of_square_root_sum

In 1976, Ron Graham, Michael Garey, and David Johnson could not show some geometric optimization problems such as whether Euclidean Traveling Salesman Problem is NP-complete(they can only show the problem is NP-hard), the reason is that they could not show whether the square-root-sum problem is polynomial time solvable or not. https://rjlipton.wordpress.com/2009/03/04/ron-graham-gives-a-talk/

The square-root-sum problem is a long open problem which puzzles scholars from computational geometry, optimization, computational complexity, game theory and some other areas a lot as they all at some point, figure out the main obstacle for their problems is to handle the square-root-sum problem.

The most remarkable progress towards this problem is by Eric Allender and his co-authors, in 2003, they showed this problem lies in the 4th level of the Counting Hierarchy. http://ftp.cs.rutgers.edu/pub/allender/slp.pdf

So based on above facts, one can't solve convex optimization problem in (true) polynomial time with the Ellipsoid method and Interior Point method.

The big O notation is to measure the running time of the algorithm in worst case. However, in practice, the worst case may be a very rare event, that's why you can not use it to measure the practical performance.