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:

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

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

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

Ok, Aravind's awake :)

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.

Post a Comment