# Mathematical Food for Thought

Serves a Daily Special and an All-You-Can-Eat Course in Problem Solving. Courtesy of me, Jeffrey Wang.

• ## Meta

Bigger Means Better. Topic: Algebra/Inequalities/Sets. Level: Olympiad. May 12th, 2007

Definition: A set is said to be convex if, for any and , we have .

——————–

Definition: Let be a real-valued function defined on a convex set . We say that is convex if, for all and , we have

.

——————–

Theorem: (Jensen’s Inequality) Let be a real-valued, convex function defined on a convex set . Given and nonnegative reals such that , we have

or, more concisely,

.

Proof: We proceed by induction on .

Base Case – , we have which is trivially true. , we have with which is true by the definition of convexity.

Induction Step – Suppose . We wish to show

for nonnegative reals that sum to . Well,

by the definition of convexity. But since , by our inductive hypothesis (the term case) we must have

.

Combining this into the above inequality, we obtain

as desired, completing the induction. QED.

——————–

Definition: The convex hull of a set is defined to be the smallest convex set containing . It is the set of all points that can be written as , where is a natural number, are nonnegative reals that sum to , and .

——————–

Definition: A vertex of a set is a point such that for all not equal to and we have .

——————–

Theorem: Let be the set of vertices of a compact convex set . The convex hull of is .

Example: The set of vertices of a convex polygon is, in fact, its vertices as traditionally defined in geometry. Any point inside the polygon can be written as a convex combination of its vertices.

——————–

Theorem: If is a real-valued, convex function defined on a compact convex set , then , where is the set of vertices of .

Proof: We will show that for all .

Let where are nonnegative reals that sum to and . This is possible by the preceding theorem. Then by Jensen’s Inequality we get

.

And since , we have for all . Furthermore, since is a subset of , we know that this maximum is attained, thus

as desired. QED.

——————–

Comment: This is a very useful result, as it allows us to limit our search for the maximum of a function to its set of vertices, which is usually a considerably smaller set, though it may still be infinite (think sphere). In any case, this works well for constrained optimization problems in which the domain is limited to a polygon, the easiest application of this theorem.

——————–

Practice Problem: Let and be real numbers satisfying and . Find the maximum value of .

### 3 Responses to “Bigger Means Better. Topic: Algebra/Inequalities/Sets. Level: Olympiad.”

1. blue_giraffe Says:

O_O so little people aren’t as better as big people O_O

2. t0rajir0u Says:

In retrospect, that proof should’ve been obvious. Tricky!

3. Katia Says:

OMG ur mom’s blog is so cool!