Stretching the Definitions

Some problems aren't convex but are close enough.

This is the live blog of Lecture 5 of my graduate class “Convex Optimization.” A Table of Contents is here.

One of the main points of emphasis of this course is being able to see convexity in nonconvexity. Some modeling problems that feel very nonconvex can be massaged into a list of convex constraints and costs that are potentially solvable. 

One of the simplest sets of nearby models are functions that are convex after applying an invertible function. Let’s say we have some invertible function h and consider the family of functions where h(f) is convex or concave. For lack of a better naming convention, we could call such a function h-convex or h-concave. Any such functions should be easy to optimize because all you’d have to do is apply h and then perform local search. You can also use h-convex functions in constraints. If f is h-convex, the set f(x)≤B is convex because it is equal to the set h(f(x))≤h(B). Hence if you end up with an h-convex or h-concave function in your modeling problem, don’t fear.

The most common instance of this sort of thing is log-concavity. A function is log-concave if its logarithm is concave. Log-concavity gets its own special name because of its ubiquity in probability and statistics. Almost all of the probability distributions we learn in statistics are log-concave. The normal distribution, the exponential distribution, the uniform distribution, and the logistic distribution are all log-concave. For most parameter regimes of interest, the Wishart distribution, the Dirichlet distribution, the gamma distribution, the chi-square distribution, the beta distribution, and the Weibull distribution are also log-concave.

Finding the maximum of the density of a log-concave distribution can be done by local search. For many such models, maximum likelihood estimation is similarly a convex optimization problem (statisticians love maximum likelihood estimation). Another surprising feature of the log-concave distributions is that they are closed under statistical operations. A sum of independent log-concave random variables is log-concave. Moreover, the marginal distribution of log-concave distributions is also log-concave.¹

These computational facts explain more than anything else why we use these distributions. We know almost nothing is really normally distributed, but it’s so convenient to use the normal distribution that we throw up our hands and force ourselves to see the world as if it were normal. Hidden convexity explains many of our modeling habits.

Beyond log-concave functions, there are log-convex functions, exp-convex functions, exp-concave functions, and so on. You can and should add all of these to your modeling toolbox.

Beyond the simple notion of h-convexity, we can take a further step into the weird by looking at quasiconvex functions. Quasiconvexity generalizes the idea of unimodality. If a function is nonincreasing up to some point and then nonincreasing after that, it should be easy to optimize:

Such a function is called unimodal. One key feature of this function is all of the sublevel sets (the set of all x whose function values are less than B) are intervals.

Quasiconvexity generalizes this phenomenon to higher dimensions. A quasiconvex function is one whose sublevel sets are convex. In other words, constraints of the form f(x)≤B define convex sets for any value of B. This means that they can perhaps be used as constraints in convex optimization problems. The only tricky part is deriving algorithms to handle such constraints. We’ll see some ways of handling this later in the semester.

Unimodal functions can be optimized using a bracketing search that successively narrows down the interval where an extreme point occurs. In other words, these are functions that can be minimized using

scipy.optimize.minimize_scalar()

In higher dimensions, quasiconvex functions can often also be minimized by a generalization of this algorithm. If you can check if there is a point less than a prescribed value, then you can globally optimize a quasiconvex function.

Quasiconvex functions are pretty weird, though. The function f(x,y) = xy is quasiconvex. Getting weirder, the ceiling function that returns the smallest integer greater than or equal to a point is quasiconvex:

Even weirder, the function that counts the number of nonzero elements in a vector is quasiconvex on the nonnegative orthant. Quasiconvexity is, in other words, probably too general. We’ll see examples of solvable problems in the class, but these tend to be special cases. Nonetheless, a core part of this course is identifying the nonconvex problems that we can solve with convex optimization. Many quasiconvex problems fall into this bucket.

1. Both of these facts require some annoying analytic manipulation of integrals. See this paper if you’re interested in the gory details.