Just a new guy in optimization. Is it true that all convex optimization problems can be solved in polynomial time using interior-point algorithms?
$\begingroup$
$\endgroup$
asked Apr 2, 2012 at 23:31
Add a comment
|
5 Answers
$\begingroup$
$\endgroup$
14
No, this is not true (unless P=NP). There are examples of convex optimization problems which are NP-hard. Several NP-hard combinatorial optimization problems can be encoded as convex optimization problems over cones of co-positive (or completely positive) matrices. See e.g. "Approximation of the stability number of a graph via copositive programming", SIAM J. Opt. 12(2002) 875-892 (which I wrote jointly with Etienne de Klerk).
Moreover, even for semidefinite programming problems (SDP) in its general setting (without extra assumptions like strict complementarity) no polynomial-time algorithms are known, and there are examples of SDPs for which every solution needs exponential space. See Leonid Khachiyan, Lorant Porkolab. "Computing Integral Points in Convex Semi-algebraic Sets". FOCS 1997: 162-171 and Leonid Khachiyan, Lorant Porkolab "Integer Optimization on Convex Semialgebraic Sets". Discrete & Computational Geometry 23(2): 207-224 (2000).
M.Ramana in "An Exact duality Theory for Semidefinite Programming and its Complexity Implications" Mathematical Programming, 77(1995) shows that SDP lies either in the intersection of NP and co-NP, or outside the union of NP and coNP, and nothing better than this is known.
In "Semidefinite programming and arithmetic circuit evaluation" Discrete Applied Mathematics, 156(2008) Sergey P. Tarasov and Mikhail N. Vyalyi show that SDP can be used to compare numbers represented by arithmetic circuits. (The latter is regarded as one of hard problems).
answered Apr 3, 2012 at 3:54
-
4$\begingroup$ Just to add a note: the copositive cone causes problems because of the lack of a "polynomial time" separation oracle. Even the complexity membership in the copositive cone is a difficult problem if i recall correctly. $\endgroup$– SuvritCommented Apr 5, 2012 at 20:13
-
3$\begingroup$ @Suvrit: right. There is a theorem about "equivalence of separation and optimization" for convex problems, i.e. you can solve convex problems in polynomially many (in the dimension, and diameter of the feasible set) calls to the separation oracle. $\endgroup$ Commented Apr 6, 2012 at 5:40
-
1$\begingroup$ +1. Thanks for your answer! (1) I was wondering what is "semidefinite programming problems (SDP) in its general setting"? I have seen several different formulations of SDP, and am confused if they are equivalent, or just some is more general than the other. More specifically, here is the post for my question: scicomp.stackexchange.com/questions/5566/…. (2) What special kinds of SDP have polynomial-time exact (as opposed to approximate) algorithm? Thanks for your help! $\endgroup$– TimCommented Mar 15, 2013 at 22:03
-
2$\begingroup$ Tim: (2) in short, the ellipsoid method seems to me the only one for which the complexity is known to be polynomial-time in the classical model of computation, assuming that the diameter of a Euclidean ball containing the feasible set is a part of the input. And the latter might be doubly exponential in the rest of the problem size, as examples of Khachiyan and Porkolab show. In some cases this diameter is small, and so it's not an issue, e.g. this is so for the MAXCUT SDP relaxation by Goemans and Williamson. $\endgroup$ Commented Mar 17, 2013 at 13:18
-
1$\begingroup$ (2) - but note that it will remain an approximation, with arbitrary precision, just by nature of the ellipsoid method, and the fact that, unlike in LP, there are no rational vertex solutions, in general. If you want an exact (algebraic numbers!) solution, then the only known algorithms would be exponential-time w.r.t. the dimension or w.r.t. the number of constraints. $\endgroup$ Commented Mar 17, 2013 at 13:22
$\begingroup$
$\endgroup$
2
As mentioned by another poster, the work of Nesterov and Nemirovski summarized in Interior-Point Polynomial Algorithms in Convex Programming showed that many convex optimization problems (including linear programming (LP), second order cone programming (SOCP) and semidefinite programming (SDP) problems) can be solved in polynomial time by interior point methods. These methods are hugely important both in theory and in practice.
An earlier approach that is equally important in its theoretical consequences was the work in the 1980's on the ellipsoid algorithm. Khachian showed that the ellipsoid algorithm can solve linear programming problems in polynomial time. Later, Groetschel, Lovasz, and Schrijver showed that the ellipsoid algorithm could also be applied to certain combinatorial optimization problems and proved the polynomial equivalence of separation and optimization. This work appears in their book, Geometric Algorithms and Combinatorial Optimization. Although the ellipsoid method was very important from a theoretical point of view it isn't useful in practice.
The phrase "convex optimization" is often used by authors to refer to the class of convex optimization problems that can be formulated as conic form LP, SOCP, or SDP problems. It isn't strictly true that all optimization problems involving the minimization of a convex objective function over a convex feasible set can be formulated as LP, SOCP, or SDP problems. You can even imagine mathematical instances of convex optimization problems for which there is no reasonably structured problem representation that you could use in saying "I have a polynomial time algorithm for this problem."
Thus it's not really correct to say that "all convex optimization problems can be solved in polynomial time." However, as Nesterov and Nemirovski show, many convex optimization problems can be formulated as LP, SOCP, or SDP and this technique is enormously important in both theory and practice.
answered Apr 3, 2012 at 1:33
-
6$\begingroup$ even SDPs, however, cannot be solved in polynomial time, or at least no algorithms like this are known. See my answer below. $\endgroup$ Commented Apr 3, 2012 at 3:58
-
1$\begingroup$ Yes, although in most practical situations where you're formulating some problem as an SDP, you can ensure that Slater's condition holds. $\endgroup$ Commented Apr 3, 2012 at 5:03
$\begingroup$
$\endgroup$
2
You should check out Boyd-Vanderberghe's convex optimization, available for free on Boyd's web page at Stanford. This has a discussion of the "easy" classes of convex optimization problems (google "self concordant", for slightly quicker satisfaction). Even for linear problems interior point methods are slow if the condition number is very bad (which sometimes occurs in practice; what occurs even more frequently is that the condition number cannot be PROVED to be small, so your program runs fast in practice, but cannot be proved to be polynomial time).
answered Apr 3, 2012 at 1:57
-
1$\begingroup$ One question about your last sentence. Do you mean the condition number might be exponential? $\endgroup$ Commented Apr 5, 2012 at 19:47
-
$\begingroup$
$\endgroup$
3
For many cases, Yes (but see Dima's and Brian's answers), by work of Yu. Nesterov, A. Nemirovski, as summarized in their book Interior-Point Polynomial Algorithms in Convex Programming, SIAM Studies in Applied Mathematics, 1994. (SIAM link). Here are more recent (2004) lecture notes for a course given by Arkadi Nemirovski, entitled "Interior Point Polynomial Time Methods in Convex Programming": PDF link.
Convex optimization specialists will hopefully provide a more nuanced answer.
answered Apr 3, 2012 at 0:15
-
3$\begingroup$ However, there are NP-hard convex optimization problems. (see my answer below) $\endgroup$ Commented Apr 3, 2012 at 3:56
-
1$\begingroup$ @Dima: Thank you for correcting me; I have revised accordingly. $\endgroup$ Commented Apr 3, 2012 at 10:28
-
2$\begingroup$ The reference to Nesterov and Nemirovskii is very useful, and the authors articulate quite clearly in the Introduction that when they say "Polynomial Algorithms", they refer to a relaxed notion of polynomial bounds, subject to a bound on the accuracy of the solution, provided as an input. This relaxed notion of polynomial bounds is called "weakly polynomial" in Papadimitriou and Stieglitz, "Combinatorial Algorithms", 2nd Edition. Richard Kipp-Martin in his "Large Scale Integer and Linear Optimization" uses the same terminology in the Appendices. $\endgroup$ Commented Aug 10, 2020 at 7:46
$\begingroup$
$\endgroup$
0
If I understand correctly, interior-point algorithms require the objective and constraint functions to have a certain amount of smoothness.
