Optimality and least squares · Definition

Local and global minima of convex functions

continuous optimizationoptimality and least squares

Before you start you need to know

In optimization, telling local minima apart from global ones determines whether a point found by an algorithm is truly the best solution. Convexity is the property that guarantees the two coincide.

Definition

A local minimum of a function is a point where no sufficiently small neighborhood contains smaller values, while a global minimum is a point where the function attains the lowest value over its entire domain.

\[f(x^*) \le f(x) \quad \forall x \in \mathrm{dom}\, f\]

If f is convex over a convex set, every local minimum is also global, and the set of minimizers is itself convex. Moreover, if f is strictly convex, the global minimum is unique. These properties follow directly from the convexity inequality and underpin the descent methods discussed by Boyd and Vandenberghe.

Consider \(f(x)=(x-1)^2\) on \(\mathbb{R}\). Its gradient \(2(x-1)\) vanishes only at \(x=1\), which is both a local and a global minimum. If the domain is restricted to \([2,5]\), the global minimum moves to \(x=2\), a boundary point where the gradient is not zero, showing that the zero-gradient condition applies only to interior minima.

A common mistake is to assume every critical point is a minimum. For instance, \(f(x)=x^3\) has zero gradient at \(x=0\), yet that point is an inflection point, not a minimum. In nonconvex functions, even a local minimum may lie far from the global one, as happens with functions containing several valleys.

Think about it

If f is convex but not strictly convex, can it have infinitely many global minima? Give an example.

Yes. For example, \(f(x)=\max(|x|-1,0)\) is convex and attains its minimum value 0 on the whole interval \([-1,1]\).

Exercises 10

  1. What is the minimum value of \(f(x)=x^2\) over \(\mathbb{R}\)?
  2. Is the point \(x=3\) a global minimum of \(f(x)=(x-3)^2\) over \(\mathbb{R}\)?
  3. For \(f(x)=x^4\), what is the global minimum over \(\mathbb{R}\)?
  4. Which set describes the minimizers of \(f(x)=|x|\) over \(\mathbb{R}\)?
  5. If a convex function has a local minimum at \(x_0\), what can be said?
  6. Let \(f(x)=(x-2)^2+1\) on \([0,5]\). What is the global minimum and where is it attained?
  7. Let \(f(x)=x^2-4x\) over \(\mathbb{R}\). What is the global minimum?
  8. Let \(f(x)=e^x\) on \([-1,2]\). What is the global minimum?
  9. Let \(f(x,y)=x^2+y^2-2x\) over \(\mathbb{R}^2\). What is the global minimum?
  10. Let \(f(x,y)=x^2+2y^2\) on the line \(x+y=3\). Find the global minimum of f restricted to that line.

References

  • Stephen Boyd, Lieven Vandenberghe, Convex Optimization, 1st edition, Cambridge University Press, 2004.
  • Jorge Nocedal, Stephen J. Wright, Numerical Optimization, 2nd edition, Springer, 2006.