Friday, August 24, 2007

Extreme-point fallacy

First, some administrative notes. Thanks to the readers for the feedback. I got requests for research advice and explanations of techniques from my thesis; I promise to post on both topics shortly.

Do take a look at Daniel's problem in this comment thread. It combines the features of being theoretically interesting and challenging while also being of great practical importance. If anyone has thoughts or literature pointers, please do share them with me or Daniel!

And here's a little teaser to see who's awake. Let D be a subset of R^n of the nicest possible kind: a finitely generated compact convex polytope. Thus, D is nothing more than the convex hull of finitely many points. Let f and g be two convex functions mapping D to R. A mathematician (let's call him Hermann) would like to prove that
f(x) <= g(x)
for all x in D. Now Hermann reasons as follows. He knows (from reading Papadimitriou and Steiglitz, for example) that an affine function achieves its extreme values on the extreme points of a convex domain. From this he concludes that a convex function achieves its maximal values on the extreme points of a convex domain (can you also make this deduction? Hint: the epigraph of a convex function lies above its derivative.). "Aha!" he exclaims. "All I need to do is check that f(x) <= g(x) on the extreme points of D. But there are finitely many of these -- they're just the corners of the polytope!"

You'll agree that verifying f(x)<=g(x) on the finitely many corners of D is, in general, a much simpler task than doing this for all of D. Is there something wrong with Hermann's reasoning, however?

[This is in no way meant to imply that any mathematician named Hermann ever claimed anything of this sort!]

5 comments:

Anonymous said...

sure, here's a trivial counterexample in one dimension. let D = [0,1], f(x) = x, and g(x) = x*x. we have f(0) = g(0) and f(1) = g(1), but in fact, f(x) > g(x) for all x in the interior of D.

aravind

Leo said...

Sure, that's a counter-example all right. So what was wrong with "Hermann's" reasoning?

Anonymous said...

f(x) - g(x) is not necessarily convex, that's the reason .. aravind

Leo said...

Ok, Aravind's awake :)

pharmacy drugstore said...

Thanks for explain us a little bit about these techniques, that's perfect because we can take some ideas from here in order to apply them to our thesis.