Can an integer optimization problem be convex?

Question

I'm trying to wrap my head around an apparent paradox that I've come across while trying to learn more about optimization algorithms:

• On one hand several sources state that convex optimization is easy, because every local minimum is a global minimum. In this video, starting at 27:00, Stephen Boyd from Stanford claims that convex optimization problems are tractable and in polynomial time.

• Other sources state that a convex optimization problem can be NP-hard. See for example this post.

See this post.

I can't wrap my head around the two statements, are convex optimization problems tractable or not?

As I try to dig deeper, one thing I noticed it that the term convex doesn't seem to be used the same way by different people when it comes to integer problems.

By some definitions, it seems that a convex integer optimization problem is impossible by definition: the very fact of constraining the variables to integer values removes the convexity of the problem, since for a problem to be convex, both the objective function and the feasible set have to be convex.

Other places seem to consider problems where if aside from the integer constraint, all other constraints and the objective function are convex, to be convex optimization problems.

Which one of the two is correct? Can an integer programming problem be convex? Or is it non-convex by definition, given the restrictions it puts on the feasible set?

If it is possible for an integer programming problem to be convex, then in what sense are convex optimization problems "easier" that non-convex problems, since both are NP-Hard?

Answer 1

Feels like you are asking two things, tractability of convex problems and convexity of integer problems.

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 an iterate $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 whose representation grows at an exponential rate $2^n$.

Regarding the second issue whether an integer problem is convex, the answer is no, and that follows directly from geometry (unless there is only 1 solution). However, as shown by Sam Burer, nononvex mixed-binary quadratic programs can be rewritten as convex optimization over the co-positive cone. Remember from the discussion above though, this only implies we've made a convex reformulation, not that the problem has been made tractable.

Answer 2

Mathematically, mixed-integer programs (MIPs) are non-convex, for the very reason you stated: the set $x \in \{0,1\}$ is inherently non-convex. In fact, for a convex optimization problem (e.g. linear programming), you can find the solution in polynomial time using interior-point methods.

The reason the optimization community is going against the pure "mathematical" grain lies in the way that MIPs are solved: to find the best combination of binary variables, the problem is relaxed, e.g. $x\in \{0,1\} \rightarrow x \in [0,1]$. In other words, the problem is "made" continuous. If then the objective function and constraints are convex, this relaxed version of the problem is also convex and can be solved in polynomial time. This allows e.g. branch-and-bound algorithms to be computationally sensible, as they have to solve these subproblems many, many times to solve a MIP.

However, MIPs are, in general, NP-hard, precisely because they are non-convex.

Answer 3

The terminology here is a bit ambiguous. I've heard the term "convex MINLP" being used in two different ways:

1. As others said, a problem where the continuous relaxation of the integer variables results in a convex problem, and
2. An MINLP with a linear integer part and a convex continuous part (which is a subset of the previous definition). This is important for certain techniques, e.g. generalised Benders decomposition.