Measure Theory/Convexity and the Product-to-Sum Bound

Convexity

edit

Recall from Lesson 0: Generalizing to Lp that we are interested in convexity because it may help us to find a bound for the product of any two real numbers. In particular, we would like to prove the inequality

  for arbitrary   and weights   such that  

Why is this inequality an instance of convexity? It will help to think about convexity in the context of an abstract vector space.

Intuitively, convexity means that for any two points in the shape, the line-segment between them lies inside the shape. For example, any triangle is always convex, a circle is convex, but there does exist a rectangle which is not convex. A shape that is not convex is called concave.


Exercise 1. Draw a Convex Shape


Draw a convex shape, just with the intuitive definition.

More rigorously, let's consider any abstract vector space V. Naturally you want to primarily imagine   for  .

Definition: line segment, convex shape

Let V be any vector space and  . We define the line segment between   and   by the set of points

 

We say that any subset   is convex if for every two points   the line segment between them is contained in S.

  for all  


Exercise 2. Prove a Convex Shape


In this exercise, consider the vector spaces   for positive natural numbers n.

Prove that the open unit circle is convex (i.e.  ).

Also prove convex shapes are closed under positive scalar multiplication and translation. That is to say, if   and   is convex, then

 

is convex. And if   then

 

is convex.

Now trying to relate this all back to our mission of proving the inequality at the start, we want to have a notion of the convexity of a function. We then home that this notion relates to the logarithm and the inequality at the beginning.

Therefore the following definition seems reasonable:

Definition: epigraph, convex function

Let   be a function on an interval of real numbers  .

Define the epigraph of f by the set of all points above the graph of f.

 

We say that f is convex if its epigraph is convex.

One may wonder, as I did, why we define a function to be convex if its epigraph is convex, rather than, say, its "hypograph" (i.e. the set of points below the graph)? As far as I can tell this is a mere convention -- a coin was tossed and I guess we live with the legacy of defining convexity of functions by their epigraph rather than hypograph.

Nothing much hinges on this. Although the logarithm is not convex, its negative is convex, i.e.   is a convex function, and that is enough to use the results that we will find about convex functions.


Exercise 3. Convex only at the Boundary


Show that a function's convexity is determined by its graph, in the sense that one does not need to consider any points not on the graph. More precisely, a function is convex if and only if for any points on the graph, the segment between them is contained in its epigraph.

Even more rigorously, let   be a real function on an interval I. Also let  . Note that any point on the segment between   and   is identified with a value of   such that the point is given by

 

(You will need to identify points with vectors, which is no big whoop, you just understand that   corresponds to the vector  .)

For the function to be convex, the point must be contained in the epigraph. For the point to be contained in the epigraph, this is the same as

 

So what you must show is that f is convex if and only if, for all   and  ,

 


Exercise 4. Convexity and Differentiation


Suppose that f is twice differentiable on an interval I. Now show that f is convex if and only if the second derivative is positive throughout I.

Infer that   and   are both convex.

Product-to-Sum Bound

edit

Finally we are in a position to deliver on what put us down this path so long ago!


Exercise 5. The Weighted AM-GM Proof


Infer

  for all   and   such that  

Infer further the weighted AM-GM inequality.

 


Exercise 6. The Product-to-Sum Bound


Recall that the point of proving the weighted AM-GM inequality was in the hopes that it will give us a useful bound on an arbitrary product of real numbers. Since we are interested in values  , this seems primarily useful only if we consider   in order to meet the condition on the weights, and correspondingly use the equation

 

in order to have another weighted value, q, for which the theorem applies.

But note that if we consider the equality   then there is no corresponding q. Could we take   in some sense? We will return to this idea in the last section, so for now only consider  .

Use this to infer a product-to-sum bound for the product of any two real numbers.

Hint: We said in Lesson 0: Generalizing to   that we could expect to have powers of p in our bound, since it is fine if our result is related to the   norm. So replace a in the weighted AM-GM inequality by   and so on.

Definition: conjugate

Let   be any real number. The number defined by

 

is called the conjugate of p. In this case, we write  .