The distinction between convex and non-convex problems is usually dubbed as the distinction between easy and hard problems. While in the convex case you are golden (local optima are global optima; almost every dumb algorithm that you can think of converges; differentiable and non-differentiable cases are pretty much the same, besides the rates of convergence that you can get), in the non-convex case not so much (there are few cases where you can relax to a convex problem and still get the exact solution, but in the general case you have to use approximate methods and/or heuristic methods like alternating minimization, relaxations, genetic algorithms, and so on).

My question is if there are non-convex problems which are easy to solve exactly, i.e., get a global optimum to arbitrary precision. I would like examples besides the best rank $k$ approximation to a given fixed matrix given by computing its SVD and keeping just the largest $k$ singular values. I also aware that there is something about submodular functions, but do not know many details.


When you say "non-convex problems", do you mean specifically non-convex optimization problems? That is what your the tags and the context suggest that is what you mean, but I just want to double-check.

Assuming that is the case, I also have an issue with your use of the phrase "exact solution". It is not going to be possible, even in exact arithmetic, to get the exact solution to most convex programs: the exact optimal value, and/or an exact optimal point. You can, in theory, do this for most linear programs by using the simplex method to identify an optimal basis---but the simplex method has worst-case exponential complexity! In fact, the polynomial algorithms for linear and convex programming are iterative, and approach an exact solution asymptotically. Even in exact arithmetic, you must trade computation time for precision. I am sure what you are referring to here is simply the "global" solution, not the "exact" solution, but I think it was worth making this distinction.

So, let me answer the following revised question: are there broad classes of non-convex optimization problems for which tractable algorithms exist to obtain the global solution to within predefined numerical accuracy, under modest conditions, and assuming exact arithmetic?

I would say the answer is no. The class of convex programs is certainly the most general class of tractable optimization problems that we know of. Yes, there are exceptions; you pointed to (the minimization of) submodular functions, for instance. But you then suggested that's not broad enough to count, and I agree. No such exceptions are even going to approach the breadth of convex programs.

Geometric programs form a class of tractable, non-convex optimization problems. When you consider the larger class of so-called generalized geometric programs (and you should; see the link), it's a relatively extensive class. But in fact, every GP (and GGP) can be mechanically converted to a convex program via a simple change of variables ($x\rightarrow e^y$). So I would argue this is really not a distinct class, but a subset of convex programs "in disguise".

Even SVDs, the other exception you mention, has ties to convex optimization. The maximum singular value is convex in the elements of the matrix, as is the sum of the largest $k$ singular values. So to obtain, say, the $k$th eigenvalue, you could in theory solve two convex programs, one for $\sum_{i=1}^k \sigma_i$ and one for $\sum_{i=1}^{k-1} \sigma_i$, and take the difference. Of course, you'd never do that, just like you'd never use a general purpose convex programming engine to solve a least-squares problem. (And indeed, accuracy would be an issue.) But the fact that you could speaks to the universality of convex optimization.

  • $\begingroup$ Yes, you are right. I meant getting a point that achieves the minimum to arbitrary precision. I was not concerned with not getting it exactly. Numerical computation has to deal with finite precision arithmetic; that is a given. You are also right about geometric programs. They are not really different. A simple change of variables of variables and you get back to a convex program. $\endgroup$ – rnegrinho May 28 '14 at 13:34
  • $\begingroup$ About the SVD, I was not very clear. What I meant was that you can get the best k-rank approximation according to the Frobenius norm to a given fixed matrix (the rank constraint makes it non-convex) by computing an SVD and keeping just the largest k singular values. I think that is somewhat unexpected that this is the case. Sorry if that was not clear. I will change the phrasing of the question to express some of these points. Thanks. $\endgroup$ – rnegrinho May 28 '14 at 13:34
  • $\begingroup$ No apologies needed. Indeed, you might not even want to edit your problem now, as perhaps this answer and question go together well (if I do say so myself). Remember, Math.SE questions and answers are for the benefit of future readers as well. Our back and forth is part of the value. $\endgroup$ – Michael Grant May 28 '14 at 13:39
  • 1
    $\begingroup$ As for the SVD. Of course, you are right: if you express the rank-$k$ optimization problems using a rank constraint, you get a non-convex model; but then, as you rightly point out, there is a tractable solution anyway. But isn't that often the case? That is, aren't there often problems that are non-convex as naturally conceived, but become convex after some novel rearrangement? $\endgroup$ – Michael Grant May 28 '14 at 13:41
  • $\begingroup$ Yes. The SVM reformulation comes to mind. Are you aware of any other examples? There is such a strike contrast between convex and non-convex optimization. I was expecting that somehow some non-convex problems would be nicer than others. For example, in some problems you would be able to quantify the degree by which you are suboptimal or have other guarantees. $\endgroup$ – rnegrinho May 28 '14 at 13:55

There are indeed some non-convex optimization problems which can be solved efficiently (in polynomial time) than the general class of non-convex optimization. Let me tell you about two such problems.

  1. We know that minimizing a general quadratic function is not that efficient. But minimizing such a function over a sphere is pretty efficient and the problem can be solved in polynomial time. See section 3 of 1 for further references.

  2. Another efficiently solvable non-convex problem is Fractional Linear Programming which is the problem of minimizing $$\frac{c^Tx+\gamma}{d^Tx+\delta}$$ subject to $AX \leq B$. This problem can also be solved using ellipsoid method and thus in polynomial time. See 2 for another approach to solve this problem.

[1] Stephen A. Vavasis. Complexity Issues in Global Optimization: A Survey.

[2] S. Schaible, Edmonton : Fractional Programming.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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