Andy's Math/CS page

Sunday, April 22, 2007

Where Does Convexity Come From?

I sometimes find it useful to distinguish between 'forwards' and 'backwards' orientations in mathematics. Given some object or family X, we can (in the 'forwards' direction) see what the existence of X entails--what kind of X there are, what more complex objects we can build out of X, etc.

In the backwards direction, we try to tell an 'origin story' about X. What is the question for which X is the answer? What is the process of which X is the result? There's usually no unique answer, and working in this direction gives a measure of creative freedom.

One important subset of backwards-focused activity is finding 'variational characterizations' of concepts. This means looking for maximization (or minimization) processes underlying the formation of the objects X. So, e.g., spheres at first sight seem like the most boring objects in geometry--they're easy to describe, they look the same from every direction, etc.--but the fact that they enclose volume with maximal efficiency is profound, and leads quickly to even deeper math when you look at double bubbles, tilings of space, and so on. Nature often 'tries' to minimize certain potential functions, and social agents try to maximize various perceived benefits, so whatever your area of interest, variational characterization may be an important way of making sense of observed patterns.

Here's a simple example. Why should we study convexity? I'll give a variational characterization from an economic perspective, which gives an origin story for a broad class of convex functions.


Peggy and Otto are friends, with different attitudes about nutrition. Peggy thinks it's all about the protein; Otto is buzzed over Omega-3 oils. (They read different magazines.)
In the first flush of enthusiasm for their new health ideas, protein and Omega-3's are the only food variables they care about.

This raises an issue whenever they buy food together: who gets what part of the food item? Ideally, they'd separate out the two key ingredients in a centrifuge, but for now, food items should be assumed to have, in each region, local 'densities' of the two nutrients that are nonseparable. The best the friends can do is break the food into tiny bits, estimate the protein and Omega-3 in each, and use this information to decide on an allocation.

We're not sure what's 'fair', exactly, but we can describe the 'frontier' of best possible trade-offs between Peggy and Otto's perceived benefits. Given a food item, define a function f(x) to be the maximum amount of Omega-3 that can be consumed by Otto, subject to the constraint that Peggy gets at least an x amount of protein.

Then f maps nonnegative reals to nonnegative reals. Moreover, it's convex down on the region where it's positive, that is, its underside is a convex body:

Why? Intuitively, we arrange the crumbs of the food item in increasing order of their protein-to-Omega-3 content ratio. As we begin giving Peggy more and more protein, we initially can do it most 'cost-effectively' by feeding her the crumbs for which this ratio is highest, but as we go on we are forced to give up more and more Omega-3 for each marginal unit of protein.

I leave it to hard-core readers to fill in details about exactly when this logic can be made rigorous; I have in mind continuous additive set measures over a compact set, and by 'maximum' I mean 'supremum'. However, I regard this result as 'morally true' (a phrase I adopted from Prof. Thomas Hunter at Swarthmore), that is, true with 'reasonable' assumptions and relatively robust to changes in the model.

What's more, the converse is also true: given any such function f(x) (nonnegative-to-nonnegative, convex down on its bounded support), I can make you a food item such that f(x) represents the set of optimal trade-offs between protein and Omega-3's.
($19.95 shipping and handling. Warning: product may taste like a soggy brick.)

So there you have it: a variational characterization of convexity, a 'recipe' if you will, with additive measures and optimization as the basic ingredients. Since many results in theoretical economics assume convexity of various types, recipes like this one (which is not new, but amounts to folklore as far as I can tell) are an important part of the 'pre-theory' of the discipline, motivating and making plausible such assumptions. Challenges to the use of these assumptions, then, should critically engage the pre-theory, for instance, by identifying cases, in both production and consumption of goods, where interaction between inputs makes additivity unrealistic. In the case at hand, of course, we know that the two friends are both wrong--nutritional 'value' is not an additive function of food consumed, as e.g. fats and protein are both necessary. (It's not even clear that nutrition should be considered a real-valued function, since there are multiple health/fitness goals one might be interested in.)


I'll end with a question to the readers: I am interested in the origin stories of probability distributions, and have from time to time skimmed over the literature regarding the trendiest distributions of them all, the power laws. I know there are a multitude of settings that give rise to them. So which ones should I study, and from which references?
I have no single criterion in mind, but am receptive to any of the following: rigor, interest, plausibility, generality, simplicity. I am also interested in critical analyses of the apparent power-law 'gold rush' in complexity studies. Thanks!

Labels: ,


  • Michael Mitzenmacher's papers are a good reference for "origin myths" for power laws from a mathematical perspective.

    See the second paragraph of this section

    By Blogger Suresh Venkatasubramanian, at 12:33 AM  

  • Thanks, Suresh!

    I've seen these passing-unrigorously-to-a-differential-equation
    arguments before, and have been curious whether there's a general theorem about justifying many of these. Guess I'll have to to look at the refs Mitzenmacher cites.

    By Blogger Andy D, at 6:14 PM  

  • I don't know about the context of power laws, but Mitzenmacher's thesis has a nice rigorous-passing-to-differential-equation argument. He uses it to analyze the power of two choices in the balls and bins model, but part of the exposition is the statement and proof of a general theorem. Recommended if you like seeing interplay between continuous and discrete math. :)
    He also has some interesting references to papers that introduced the rigorous method.

    By Anonymous Anonymous, at 2:46 AM  

Post a Comment

<< Home