Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Just a new guy in optimization. Is that true all the convex optimization problems can be solved in polynomial time using interior-point algorithms?

share|improve this question

5 Answers 5

up vote 19 down vote accepted

No, this is not true (unless P=NP). There 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 of number represented by arithmetic circuits. (The latter is regarded as one of hard problems).

share|improve this answer
3  
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. –  Suvrit Apr 5 '12 at 20:13
1  
@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. –  Dima Pasechnik Apr 6 '12 at 5:40
1  
+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! –  Tim Mar 15 '13 at 22:03
1  
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. –  Dima Pasechnik Mar 17 '13 at 13:18
1  
(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. –  Dima Pasechnik Mar 17 '13 at 13:22

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.

share|improve this answer
1  
even SDPs, however, cannot be solved in polynomial time, or at least no algorithms like this are known. See my answer below. –  Dima Pasechnik Apr 3 '12 at 3:58
    
Yes, although in most practical situations where you're formulating some problem as an SDP, you can ensure that Slater's condition holds. –  Brian Borchers Apr 3 '12 at 5:03
    
very helpful! Thank you guys –  Optimizationguy Apr 5 '12 at 19:45

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

share|improve this answer
    
One question about your last sentence. Do you mean the condition number might be exponential? –  Optimizationguy Apr 5 '12 at 19:47
    
Unfortunately, yes... –  Igor Rivin Apr 5 '12 at 20:46
    
I see. Thank you –  Optimizationguy Apr 5 '12 at 21:21

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.

share|improve this answer
    
However, there are NP-hard convex optimization problems. (see my answer below) –  Dima Pasechnik Apr 3 '12 at 3:56
    
@Dima: Thank you for correcting me; I have revised accordingly. –  Joseph O'Rourke Apr 3 '12 at 10:28
    
Thank you, Joseph! The pdf file is quite useful:) –  Optimizationguy Apr 5 '12 at 19:49

If I understand correctly, interior-point algorithms require the objective and constraint functions to have a certain amount of smoothness.

share|improve this answer
    
Thank you very much:) –  Optimizationguy Apr 5 '12 at 19:46

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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