8
$\begingroup$

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.

$\endgroup$
  • 8
    $\begingroup$ 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. $\endgroup$ – Sasho Nikolov Jul 25 at 22:17
  • 1
    $\begingroup$ 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? $\endgroup$ – Sergey Dovgal Jul 26 at 12:30
  • $\begingroup$ by "barrier methods" I mean interior-point type methods which have been developed after ellipsoid method by Nesterov, Nemirovskii et. al. $\endgroup$ – Sergey Dovgal Jul 26 at 13:38
  • $\begingroup$ 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. $\endgroup$ – Sasho Nikolov Jul 31 at 13:21
5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I think that my question needs to be reformulated. SDP is clearly a convex optimisation problem (optimising a convex function over a convex set), but my question specifically points to the standard form of convex optimisation, where the convex set is defined by the set of inequalities "convex function is negative". Do you believe that the answer to that particular form (convex optimisation in standard form is in P) is unknown? $\endgroup$ – Sergey Dovgal Jul 29 at 9:57
  • $\begingroup$ @SergeyDovgal As far as I know, one can only claim the linear programming is solvable in polynomial time. For other convex optimization problems, if they depend on the square-root-sum, one can not claim they are truly polynomial-time solvable. $\endgroup$ – Rupei Xu Jul 30 at 16:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.