Convex Functions: Local vs. Global Minima

Recommended resources

The freely available resources this lesson will direct you to.

Hello! Welcome to our next lesson on the theory of unconstrained optimization.

Introduction

In our previous lesson, we established the formal definitions of convex sets and functions. We saw that for differentiable functions, convexity is equivalent to the Hessian matrix being positive semidefinite, and that the tangent hyperplane at any point on a convex function serves as a global underestimator. These properties are not just mathematical curiosities; they are the foundation for why many optimization algorithms in machine learning succeed.

Today, we will prove the single most important consequence of convexity in the context of optimization. This lesson's learning outcome is to prove that for a convex function, any local minimum is also a global minimum. This theorem is the linchpin that connects the theory of convexity to the practice of optimization, assuring us that if we find a "bottom" in any small region of a convex function, we have found the bottom for the entire function.

Part 1: Setting the Stage for the Proof

Before diving into the formal proof, let's ensure we have a clear visual and formal understanding of the components.

Global Minimum of a Convex Function — This image illustrates the ideal scenario in convex optimization. The function has a distinct "bowl" shape, and its single local minimum at minimizer $x^*$ is also its global minimum.

To prove this property, we need two precise definitions that you'll recall from our previous work:

Convex Function: A function $f$ is convex if its domain is a convex set and for all points $x$ , $y$ in its domain and any $θ \in [0, 1]$ :
$f (θ x + (1 - θ) y) \leq θ f (x) + (1 - θ) f (y)$
Geometrically, the function's graph never goes below the straight line segment connecting two points on the graph.
Local Minimum: A point $x^{*}$ is a local minimum of $f$ if there exists some neighborhood around it (e.g., a ball of radius $ϵ > 0$ ) such that for any point $x$ within that neighborhood, $f (x^{*}) \leq f (x)$ .

The following video provides an excellent and concise review of these definitions and then walks through a complete, rigorous proof of the theorem.

Convex: Local vs Global Minimum

This video, "Convex: Local vs Global Minimum", provides a clear and rigorous argument from first principles. It starts by carefully defining the necessary concepts before constructing the proof.

Please watch from the beginning up to 07:32. This will reinforce the formal definitions of convexity and a local minimum, which are the two essential building blocks for the proof.

Part 2: The Formal Proof

Now that we have reviewed the necessary definitions, we are ready to prove the main theorem. There are several ways to structure this proof. We will explore two common and powerful approaches.

Method 1: A Direct Argument

The first method, which is presented in the video you just started, is a direct constructive argument. The logic is as follows:

Start with a local minimum, $x^{*}$ .
Pick any other arbitrary point in the domain, let's call it $z$ . Our goal is to show that $f (z) \geq f (x^{*})$ .
Consider the line segment connecting $x^{*}$ and $z$ . We can find a point on this line that is very close to $x^{*}$ and therefore falls within its local neighborhood.
Apply both the definition of a local minimum and the definition of convexity to this new point to establish the desired inequality, $f (z) \geq f (x^{*})$ .

Please watch the remainder of the video for a step-by-step walkthrough of this proof.

Convex: Local vs Global Minimum

Let's continue with the video "Convex: Local vs Global Minimum". This section masterfully assembles the definitions into a formal proof.

Watch from 07:32 to the end (10:45). Pay close attention to how the argument constructs a point inside the local neighborhood and uses the convexity inequality to relate the function value at \mathbf{z} back to the function value at \mathbf{x}^*.

Method 2: Proof by Contradiction

Another classic and powerful technique is proof by contradiction. This is the approach taken in many formal optimization texts. The logic is:

Assume the opposite of what we want to prove. That is, assume we have a local minimum $x^{*}$ that is not a global minimum.
This assumption implies that there must exist some other point, $x ~$ , such that $f (x ~) < f (x^{*})$ .
Use the definition of convexity on the line segment between $x^{*}$ and $x ~$ to show that there are points arbitrarily close to $x^{*}$ whose function values are also less than $f (x^{*})$ .
This directly contradicts our starting premise that $x^{*}$ is a local minimum.
Therefore, our initial assumption must be false, and the theorem must be true.

The following document from the Stanford AI Lab provides a concise and rigorous proof using this method.

Convexity

The document "Convexity" contains a formal statement of the theorem (as Proposition 1) and a classic proof by contradiction. Reading this will solidify your understanding and expose you to a standard proof technique in mathematics.

Please read the section titled "Proof" under "Proposition 1". It's short but dense. Focus on how the assumption f(x̃) < f(x*) is used in the convexity inequality to create the contradiction.

Test your understanding!

The proofs show that any local minimum is a global minimum. Now, consider a strictly convex function, where $f (θ x + (1 - θ) y) < θ f (x) + (1 - θ) f (y)$ for $x \neq = y$ . What can you say about the global minimum in this case? Is it possible for a strictly convex function to have multiple global minima?

Show answer

For a strictly convex function, the global minimum is unique.

Here's a proof by contradiction: Assume there are two distinct global minima, $x_{1}^{*}$ and $x_{2}^{*}$ , where $x_{1}^{*} \neq = x_{2}^{*}$ . By the definition of a global minimum, they must have the same minimum value, $f (x_{1}^{*}) = f (x_{2}^{*}) = f_{min}$ .

Now, consider the midpoint $m = \frac{1}{2} x_{1}^{*} + \frac{1}{2} x_{2}^{*}$ . By the definition of strict convexity:

f (m) = f (\frac{1}{2} x_{1}^{*} + \frac{1}{2} x_{2}^{*}) < \frac{1}{2} f (x_{1}^{*}) + \frac{1}{2} f (x_{2}^{*}) = \frac{1}{2} f_{min} + \frac{1}{2} f_{min} = f_{min}

This implies $f (m) < f_{min}$ , which contradicts the fact that $f_{min}$ is the global minimum value. Therefore, our assumption of two distinct global minima must be false. The global minimum must be unique.

Part 3: An Alternative View for Differentiable Functions

The proofs we've studied are powerful because they apply to all convex functions, even non-differentiable ones. However, for functions that are differentiable, we can use a property from our last lesson to arrive at the same conclusion in a very elegant way.

Recall the first-order condition for convexity: a differentiable function $f$ is convex if and only if for all $x, y$ in its domain:

f (y) \geq f (x) + \nabla f (x)^{T} (y - x)

Now, let $x^{*}$ be a local minimum. A necessary condition for a point to be a local minimum of a differentiable function is that its gradient is zero, i.e., $\nabla f (x^{*}) = 0$ .

If we substitute $x = x^{*}$ into the first-order convexity condition, we get:

f (y) \geq f (x^{*}) + \nabla f (x^{*})^{T} (y - x^{*})

Since $\nabla f (x^{*}) = 0$ , this simplifies to:

f (y) \geq f (x^{*}) + 0^{T} (y - x^{*}) ⟹ f (y) \geq f (x^{*})

This inequality holds for any $y$ in the function's domain. This is precisely the definition of a global minimum. This demonstrates how the local condition ( $\nabla f (x^{*}) = 0$ ) combines with the global property of convexity to guarantee a global result.

Conclusion

Today we have formally proven the central theorem of convex optimization. This result is the bridge between the theoretical properties of a function and the practical guarantees of an optimization algorithm.

Key Takeaways:

For any function that is convex, every local minimum is also a global minimum.
We proved this theorem using two different techniques: a direct argument and a proof by contradiction. Both rely on combining the formal definitions of a local minimum and a convex function.
For differentiable convex functions, this property is also a direct consequence of the first-order condition for convexity ( $f (y) \geq f (x) + \nabla f (x)^{T} (y - x)$ ) combined with the fact that the gradient is zero at a minimum.

Preview of the Next Lesson:
We have established that we can confidently seek a single global minimum for convex functions. The natural next question is how do we find it? In the next lesson, we will begin to answer this by deriving the update rule for gradient descent, the most fundamental iterative optimization algorithm in all of machine learning.