Optimality and least squares · Definition

First-order necessary condition

continuous optimizationoptimality and least squares

Before you start you need to know

Before searching for the minimum of a function, it helps to know what property that point must satisfy. The gradient gives the answer in the differentiable case.

Definition

A first-order necessary condition states that if \(x^*\) is a local minimizer of a differentiable function \(f\), then \(\nabla f(x^*)=0\).

\[x^* \text{ mín. local} \Rightarrow \nabla f(x^*) = 0\]

If \(f:\mathbb{R}^n\to\mathbb{R}\) is differentiable and \(x^*\) is a local minimizer, then for any direction \(d\) the function \(t\mapsto f(x^*+td)\) has a minimum at \(t=0\), so its derivative there is \(\nabla f(x^*)^\top d=0\). Since this holds for every \(d\), the gradient must be zero. This reasoning underpins the search for critical points.

Consider \(f(x,y)=(x-1)^2+(y+2)^2\). Its gradient is \((2(x-1),\,2(y+2))\), which vanishes at \((1,-2)\). That point is the only candidate for a local minimum, and in fact it is the global minimum, since \(f\) is convex.

A common mistake is to conclude that every point with zero gradient is a minimum. The condition is only necessary: for \(f(x)=x^3\), the point \(x=0\) has zero derivative but is not an extremum. Distinguishing it requires second-order conditions or further analysis.

Think about it

What happens if the gradient vanishes at a point that is not a local minimum?

It can be a maximum or a saddle point; the condition is only necessary, so the Hessian or further analysis must be checked.

Exercises 10

  1. What must the gradient of a differentiable function satisfy at an interior local minimum?
  2. State the first-order necessary condition for a local minimum of \(f\) at \(x^*\).
  3. What is the name of the condition requiring the gradient to vanish at a local minimum?
  4. If \(\nabla f(x^*)\neq 0\), can \(x^*\) be a local minimum of \(f\)?
  5. What kind of candidate points does the first-order condition identify for an unconstrained differentiable function?
  6. Solve \(\nabla f(x,y)=0\) for \(f(x,y)=(x-2)^2+(y+1)^2\).
  7. Find the critical point of \(f(x,y)=x^2-4x+y^2+6y\).
  8. For \(f(x,y)=x^2+xy+y^2-3x\), what is \(\partial f/\partial x\) evaluated at \((1,1)\)?
  9. For \(f(x,y)=x^2+xy+y^2-3x\), at which point does the gradient vanish?
  10. Find all critical points of \(f(x,y)=x^3-3x+y^2\) and say which one is a candidate for a local minimum.

References

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