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 .
Leave a Reply
You must be logged in to post a comment.