If a convex optimization problem can be NP-Hard, in what sense are convex problems easier than non-convex problems?

Question

Being new to the OR and Optimization world, I've always assumed that a problem being convex meant that it can be solved in polynomial time.

Now I am learning that a convex optimization problem can be NP-Hard, but that convex problems are still somehow considered easier than non-convex problems.

Can someone explain this apparent contradiction to me:

• Is it true that a convex optimization can be NP-Hard? On one hand, based on this post and the accepted answer, yes, There are examples of convex optimization problems which are NP-hard. On the other hand, This lecture from a Stanford Professor, around 28:00 states that convexity means tractability and polynomial time algorithms.

• If it is indeed true that convex optimization problems can be NP-Hard, then in what sense are they "easier" than non-convex problems? As far as I know, there are no levels of NP-Hardness, anything between NP-Complete and P-Space is NP-Hard. I frequently hear Operations Research people say that we have all sorts of tools for convex problems, while non-convex problems are still very hard to deal with?

Answer 1

A first order approximation is that convex programs are tractable, .i.e., most problems you can think of as a layman in the field that are convex, are (probably) tractable to solve. That's why you would be told that in an introductory course on convex optimization. It is not true though.

Tractability of convex problems essentially boils down to being able to decide if a solution $x$ is feasible, in a computationally tractable way (having a so called oracle available). There are convex sets for which this isn't the case. One such example if the set of co-positive matrices. If you are trying to find a matrix $M(x)$ such that $z^TM(x)z \geq 0$ for all $z\geq 0$, you have problems, as it is very hard to decide if a candidate $M(x)$ satisfies that property. Compare to the simple case of positive-semidefinite where all $z$ should lead to non-negativity, this is simply an eigenvalue test and thus semidefinite programming is tractable. Alas, also this statement is up for debate, as it depends on what you mean with solving a problem. A semidefinite programming problem with size $n$ (what ever we mean with that) can have a solution which whose representation grows at an exponential rate $2^n$.

Answer 2

There are special cases of convex problems that can be solved in polynomial time, e.g. a convex QP defined over a simplex. In general, however, convex programming is NP-hard. However, NP-hard by no means means unsolvable.

Although theorists would probably cringe at the term, there are NP-hard and what I coin as "NP-harder" problems. What I call an NP-harder problem is one that requires the combination of numerous NP-hard algorithms to solve, sometimes evoking each other exponentially many times. Although this is still NP-hard, it's much more intractable than any of its components. Deterministic global optimisation is a great example of this.

With that in mind, there are two main classes of convex problems: (i) continuous and (ii) mixed integer.

For mixed integer convex problems, we need to use methods such as branch-and-bound, so intuitively we can see why this is NP-hard and difficult in practice. In fact, solving a mixed integer convex problem is usually much harder than solving a nonconvex NLP to local optimality.

For convex NLPs, it comes down to solving a local optimisation problem, however satisfying the optimality conditions is also NP-hard. So why is this easier than mixed integer or non-convex?

The answer is that it's not "NP-harder". There are fewer NP-hard components in a convex NLP solver than in, say, a global solver. We need to satisfy the optimality conditions and that's it. We don't need to search for integer feasible points, we don't need to branch, we don't need to worry about missing the basin of attraction because of the step size, and so on, and this makes the problem much more tractable in practice.