Why Convexity?

Etymologically, the term convex originates from the latin word convexus—which translates to arched. It is not uncommon for one to wonder why convexity seems to accompany the word “optimization” in almost every context? Why are convex functions, sets, and formulations so important? Why is there a convex relaxation (such as LASSO) craze sweeping the machine learning community, both in academia and industry?

T. Rockafellar’s Convex Analysis contains over 400 concise pages on the remarkable properties and consequences of convexity. That is to say: There are too many reasons to count. Perhaps most-notably, convex functions are unimodal—any optimum of a convex surface is in fact the global optimum.

gen_unimodal.png

This explains why convexity and optimization come hand-in-hand: Convex functions are more or less a class of functions that are readily optimizable. However, unlike general unimodal (or quasiconvex) functions, convex functions are closed under non-negative combination and scaling, inducing the powerful theory of convex duality. Even more, convex functions always lie below the interior of the secant connecting two points; always lie above any tangent plane; and are almost everywhere differentiable, that is, the set of points at which convex functions are non-differentiable is necessarily infinitesimally small.

chords

By contrast, non-linear functions can be everywhere non-differentiable and, in the general case, locating only a local minimum (which can be and typically is a highly non-optimal point) is utterly intractable! These justifications of convexity, along with many others, have ignited considerable research activity as practitioners search for convex formulations of what were previously non-convex problems.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s