Just a new guy in optimization. Is it true that all convex optimization problems can be solved in polynomial time using interior-point algorithms?
Convex Optimization – Solving in Polynomial Time with Interior-Point Algorithms
computational complexityconvex optimizationoc.optimization-and-control
Related Solutions
This phenomenon extends beyond the traveling salesman problem, and even beyond NP, for there are even some undecidable problems with the feature that most instances can be solved very quickly.
There is an emerging subfield of complexity theory called generic-case complexity, which is concerned with decision problems in the generic case, the problem of solving most or nearly all instances of a given problem. This contrasts with the situtation in the classical complexity theory, where it is in effect the worst-case complexity that drives many complexity classifications. (And even for approximate solutions in NP-hard problems, the worst-case phenomenon is still present.)
Particularly interesting is the black-hole phenomenon, the phenomenon by which the difficulty of an infeasible or even undecidable problem is concentrated in a very tiny region, outside of which it is easy. (Here, tiny means tiny with respect to some natural measure, such as asymptotic density.) For example, many of the classical decision problems from combinatorial group theory, such as the word problem and the conjugacy problem are linear time solvable in the generic case. This phenomenon provides a negative answer to analogue of your question 1 for these problems. The fact that the problems are easily solved outside the black hole provides a negative answer to the analogue of question 2. And I think that the fact that these problems are actually undecidable as total problems suggests that this manner of solving almost all cases of a problem will not help us with P vs. NP, in your question 3.
For question 4, let me mention that an extreme version of the black-hole phenomenon is provided even by the classical halting problem. Of course, this is the most famous of undecidable problems. Nevertheless, Alexei Miasnikov and I proved that for one of the standard Turing machine models with a one-way infinite tape, there is an algorithm that solves the halting problem on a set of asymptotic measure one. That is, there is a set A of Turing machine programs, such that (1) almost every program is in A, in the sense of asymptotic density, (2) A is linear time decidable, and (3) the halting problem is linear time decidable for programs in A. This result appears in (J. D. Hamkins and A. Miasnikov, The halting problem is decidable on a set of asymptotic probability one, Notre Dame J. Formal Logic 47, 2006. http://arxiv.org/abs/math/0504351). Inside the black hole, the complement of A, of course, the problem is intractible. The proof, unfortunately, does not fully generalize to all the other implementations of Turing machines, since for other models one finds a black hole of some measure intermediate between 0 and 1, rather than measure 0.
[Edit: A bug in the original proof has been fixed, thanks to a comment by Francois Dorais.]
The answer is no. This kind of thing can be proved by what I call a "gas tank" argument. First enumerate all Turing machines in some manner $N_1, N_2, N_3, \ldots$ Then construct a sequence of Turing machines $M_1, M_2, M_3, \ldots$ as follows. On an input of length $n$, $M_i$ simulates $N_i$ (on empty input) for up to $n$ steps. If $N_i$ does not halt within that time, then $M_i$ halts immediately after the $n$th step. However, if $N_i$ halts within the first $n$ steps, then $M_i$ "runs out of gas" and starts behaving erratically, which in this context means (say) that it continues running for $n^e$ steps before halting where $e$ is the number of steps that $N_i$ took to halt.
Now if we had a program $P$ that could compute a polynomial upper bound on any polytime machine, then we could determine whether $N_i$ halts by calling $P$ on $M_i$, reading off the exponent $e$, and simulating $N_i$ for (at most) $e$ steps. If $N_i$ doesn't halt by then, then we know it will never halt.
Of course this proof technique is very general; for example, $M_i$ can be made to simulate any fixed $M$ as long as it has gas but then do something else when it runs out of gas, proving that it will be undecidable whether an arbitrary given machine behaves like $M$.
Best Answer
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).