Local vs Global Minima

Understanding the difference between local and global minima is crucial in optimization theory, as it affects the choice of algorithms and interpretation of results.

Definitions

Local Minimum

A point ${\theta }^{\ast }$ is a local minimum if $L({\theta }^{\ast })\le L(\theta )$ for all $\theta$ in some neighborhood of ${\theta }^{\ast }$.

• The objective function at this point is less than or equal to all nearby points
• Only considers the “local” behavior of the function
• Multiple local minima can exist within a single function

Global Minimum

A point ${\theta }^{\ast }$ is a global minimum if $L({\theta }^{\ast })\le L(\theta )$ for all $\theta$ in the entire feasible domain.

• The objective function at this point is less than or equal to all possible points
• Represents the absolute best solution to the optimization problem
• A function has only one global minimum value (though it might be achieved at multiple points)

Absolute Minima

For both local and global minima, we can define absolute minima by replacing $\le$ with $<$ in the definitions above. This means the function value is strictly less than at all other relevant points.

Visual Representation

In a one-dimensional problem, we can visualize local and global minima:

    L(θ)
    ^
    |
    |       /\
    |      /  \
    |     /    \     /\
    |    /      \   /  \
    |   /        \_/    \___
    |  /                    \_
    | /
    |/
    +--------------------------> θ
       ^           ^
       |           |
    Global       Local
    Minimum      Minimum

Unimodal vs Multimodal Functions

Unimodal Functions

A function is unimodal if it has only one local minimum (or maximum). For these functions:

• The local minimum is also the global minimum
• Many optimization algorithms are guaranteed to find the global optimum
• Examples include convex functions like quadratics

Multimodal Functions

A function is multimodal if it has multiple local minima (or maxima). For these functions:

• Finding the global minimum is significantly more challenging
• Most gradient-based algorithms may get trapped in local minima
• Global optimization techniques are required

Implications for Optimization Algorithms

Local Optimization Methods

Methods like gradient descent, Newton’s method, and quasi-Newton methods typically find local minima:

• They follow the local “downhill” direction
• They converge to the nearest local minimum to the starting point
• They cannot “climb hills” to escape local minima

Global Optimization Methods

Methods designed to find global minima include:

• Multiple random restarts of local methods
• Simulated annealing
• Genetic algorithms
• Particle swarm optimization
• Basin-hopping

These methods incorporate strategies to escape local minima, though they often require more computational resources.

Testing for Optimality

Necessary Conditions for Local Minima

For differentiable functions:

1. First-order condition: $\nabla L({\theta }^{\ast })=0$ (gradient is zero)
2. Second-order condition: ${\nabla }^{2}L({\theta }^{\ast })$ is positive semidefinite (Hessian matrix)

Sufficient Conditions for Local Minima

For twice-differentiable functions:

1. $\nabla L({\theta }^{\ast })=0$
2. ${\nabla }^{2}L({\theta }^{\ast })$ is positive definite

Global Optimality

Proving global optimality is generally difficult except for:

• Convex functions (where any local minimum is the global minimum)
• Special problem structures with known properties
• Exhaustive search of the entire feasible domain (rarely practical)

Related Pages

• Introduction to Optimisation
• Gradient-Based Methods
• Newton-Raphson Method
• Convex Optimization