Math 5311 – Optimization Notes

January 26, 2009

1 Minimizers
What is a minimizer? It’s a point a for which f ( x ) > f ( a) at all neighboring points x. Let’s make that precise.
Definition 1. Let V be a vector space. A local minimizer of f : V → R on a subset Ω ⊂ V is a point a for which
you can find an open ball B such that f ( a) < f ( x ) ∀ x ∈ ( B ∩ Ω)\ a.

Whenever you see a definition, you should pick it apart word-by-word and ask yourself why each stipulation
was included. For example, in this definition, you should ask yourself the following questions:

1. Why did we have to assume f : V → R instead of the more general f : V → R N ?

2. Why was B taken to be an open ball rather than a closed ball?
3. Why was it necessary to exclude a from B ∩ Ω?
4. Why was it necessary to intersect B and Ω?

For each definition you encounter, try to come up with similar questions.
Definition 2. Let V be a vector space. The global minimizer of f : V → R on a subset Ω ⊂ V is the point a for
which f ( a) < f ( x ) ∀ x ∈ Ω\ a.

Provide one exists, a global minimizer is necessarily unique (you should prove it).
In cases where we’re minimizing a function over an entire vector space (as opposed to a subset Ω ⊂ V) we
have the following useful theorem.
Theorem 3. A point a is a global minimizer of f : V → R on V if and only if f ( a) < f ( a + h) ∀(h 6= 0) ∈ V.

2 Convexity
Definition 4. Let V be a vector space. A subset S ⊂ V is said to be convex if for every a ∈ S, b ∈ S, and
t ∈ [0, 1], the convex combination ta + (1 − t)b is a member of S.

Convex sets provide a setting for convex functions.

Definition 5. Let Ω be a convex set. A function f : Ω → R is convex on Ω if f (tx + (1 − t)y) ≤ t f ( x ) + (1 −
t) f (y) for every x ∈ Ω, y ∈ Ω, t ∈ [0, 1]. If we have a strict inequality for t ∈ (0, 1) then the function is called
strictly convex.

There is an important uniqueness theorem for optimization of convex functions.

Theorem 6. A function that is strictly convex on Ω has a unique minimizer on Ω.

1
Proof. Assume the contrary, that f ( x ) is convex yet there are two points a and b in Ω such that f ( a) and f (b)
are local minima. Because of the convexity of Ω every point on the secant line ta + (1 − t)b is in Ω. Without
loss of generality suppose f ( a) ≥ f (b); if this is not the case, simply relabel the points. We then have

t f ( a ) + (1 − t ) f ( b ) < f ( a ) ∀t ∈ (0, 1).

However, because f is assumed strictly convex, we also have

f (ta + (1 − t)b) < f ( a) ∀t ∈ (0, 1).

As we take t arbitrarily close to 0 along the secant line, x = ta + (1 − t)b remains in Ω (because Ω is convex)
and f ( x ) remains strictly below f ( a) (because f is strictly convex). Therefore, there is no open ball B 3 a such
that f ( a) < f ( x ) ∀ x ∈ ( B ∩ Ω)\ a. Therefore, a is not a local minimizer, which is a contradiction.

Notice that we’ve said nothing yet about derivatives. In calculus, you learned to find extrema by setting first
derivatives to zero and distinguish minima and maxima using signs of second derivatives. The definitions
given here are valid for differentiable functions, but also for non-differentiable functions such as | x |. Notice
also that we’ve set nothing yet about linear algebra.

3 Application to minimization of quadratic forms

Theorem 7. A quadratic form p : V → R, p( x ) = c − 2x T f + x T Kx, is convex if and only if K is positive definite.

Theorems 6 and 7 together establish a necessary and sufficient condition for a quadratic form to have a unique
global minimizer. Theorem 8 tells us how to find a minimizer:
Theorem 8. A point x ∗ is the global minimizer of the quadratic form p( x ) = c − 2x T f + x T Kx if and only if K is
positive definite and x ∗ is the solution to Kx ∗ = f .

4 Exercises
1. Suppose that a sloppy mathematician defined a local minimizer in the same way I did, but with one
(apparently) minor change: B can be a closed ball, not an open ball as in the correct definition. Show that
this definition leads to the not-very-useful conclusion that every point in Ω is a local minimizer!
2. Prove that any vector space is convex.
3. Let T : R N → R N be a linear transformation, and let Ω be a convex subset of R N . Define Ω0 to be the
image of Ω under the transformation T. Prove that Ω0 is convex.
4. Let K ABC be the triangle bounded by the points A, B, and C in R2 . Prove that K ABC is convex.
5. Prove that f ( x ) = | x | is convex but not strictly convex.
6. Using the definition of convexity (i.e., without using calculus) prove that f ( x ) = x2 is strictly convex.
7. Find a convex subset Ω ∈ R such that f ( x ) = xe− x is convex on Ω. You may use calculus.
8. Prove that the intersection of two convex sets is convex.
9. Is the union of two convex sets convex? Prove or find a counterexample.
10. Prove that every vector space is a convex set
11. Prove that every convex function is continuous
12. Theorem 8 above is similar to Theorem 4.1 in the textbook, but the two theorems are not identical. How
do they differ?