Convex vs Strictly Quasiconvex Functions in Optimization

Question

I have read/heard quite a few time that in the old days, it was considered that linear programs constitute the class of optimization problems that can be solved efficiently in practice (as a rule of thumb) and that nowadays it's not that way anymore, that nowadays the class of efficiently solvable problems are the convex programs (again, as a rule of thumb).

However, according to the cited paper¹, one can convexify strictly quasiconvex programs. Then for what reason do people say that it is "convex problems" not "strictly quasiconvex", that we can solve. Aren't those the same while we can transform one to another using convexification?

_{[1] Gerencsér, L. On a close relation between quasi-convex and convex functions and related investigations. Statistics: A Journal of Theoretical and Applied Statistics. 4.3 (1973): 201-211.}

Answer 1

Even though I consider "convex is easy" to be a good rule of thumb, there are some important details to consider. Maybe surprisingly:

Convex programming is NP-hard in general

In this paper, Samuel Burer shows that every mixed integer quadratic program is equivalent to some convex program that is not significantly bigger. Because mixed integer programming is NP-hard, it must be that convex programming is also NP-hard.

Burer is able to obtain this result by adding a constraint of the form $X \in C^*_q$, for some matrix $X$ of variables. Here $C^*_q$ is the cone of $q$ by $q$ completely positive matrices, defined as follows:

$$C^*_q = \left\{ X \in \mathbb{R}^{q \times q} : X = ZZ^\top \textrm{ for some } Z \in \mathbb{R}_{\ge 0}^{q\times r} \textrm{ for some finite } r \right\}.$$

Only two details about this definition are relevant here:

1. The set $C^*_q$ is convex.
2. Checking if a given matrix $X$ is an element of $C^*_q$ is NP-hard.

The ellipsoid method can be used as a theoretical tool to prove that various convex programs are easy to solve. I gave an intuitive explanation of this algorithm in another answer. In this case, the ellipsoid method is not efficient, because we cannot efficiently check if the current point is feasible due to point 2. Or as I phrase it in the other question: it will be difficult to throw away the 'bad side' of the ellipsoid in each iteration.

Formally we say that for the problem above, we do not have a polynomial-time separation oracle (unless P = NP). A separation oracle is an algorithm that for a given point either returns that it is feasible, or returns a hyperplane that separates the point and the feasible set.

What is easy?

Some general classes for which it has been proven that they are polynomially solvable are

• Linear Programs (LP)
• Second Order Cone Programs (SOCP)
• Semi-Definite Programs (SDP)

My feeling is that we are extremely good at solving LPs, very good at solving SOCPs (which include convex quadratic programs), but large scale SDPs are still relatively difficult to solve in practice (feel free to correct me). But from a complexity standpoint, all of these are easy.

Many other convex problems that use well-known functions (like exponents, polynomials, and logarithms) are also polynomially solvable. Checking feasibility can be done by going over all individual constraints, and separating hyperplanes can be based on the gradients of the violated constraints. In practice, we have to take into account that software for more general problems is necessarily less specialized than the LP, SOCP, or SDP software, which may affect performance if you solve large scale problems.

We conclude that "convex is easy" is a reasonable rule of thumb.

Quasi-convex programs

There are various generalizations of convexity. A general class of programs for which every KKT point is a global optimum are type I invex programs. While definitely interesting from a theoretical viewpoint, many of these generalizations do not seem practically useful to me.

I have yet to encounter a practical problem for which a quasi-convex program or invex program is used to solve it. One reason for this could be that modeling with these functions is surprisingly difficult! Where convex functions remain convex if you sum them, it is not true that the sum of quasi-convex functions is quasi-convex. This already complicates modeling. Invex programs are even worse: the objective and all constraints need to be invex with respect to the same function, creating a dependency among constraints.

Summary

Convex programs are usually easy, but not always. Some more general programs are also easy to solve, but don't seem to be that useful in modeling practical problems. To me, it seems therefore unnecessary to mention them in our rule of thumb, at least for now.

---

_Reference

_{[1] Burer, S. (2009). On the copositive representation of binary and continuous nonconvex quadratic programs. Mathematical Programming. 120(2):479-495.}

Answer 2

My claim is that everything that can be formulated as a conic optimization problem using

• Linear cones
• Quadratic cones
• Power cones
• Exponential cones
• Semi definite cone (with some qualifications)

can be solved efficiently in practice. First of all there are surprisingly few convex optimization problems that fall outside this class of problems and secondly only efficient (near) symmetric primal-dual algorithms are known for this class of problems.

Note if you use the popular software software packages Cvx or Cvxpy they will only allow you to formulate problems that can converted to the above mentioned conic problems.

You can read more about conic problems in the Mosek modelling cookbook.