Chapter 14

Unconstrained Optimization

We've developed some powerful tools for working with multivariable functions: we can take their partial derivatives, directional derivatives, and understand the relationship between the gradient and their level sets. Our next goal is to put this knowledge to work and learn how to find maximal and minimal values. This is a critical skill in real world applications, where we are looking to maximize efficiency, or minimize cost.

14.1Critical Points and Local Extrema

Definition 14.1 (Local Extrema and Saddle Points). An extremum is a catch-all term for a maximum or a minimum. A local minimum occurs at a point $⃗ 𝑝 = (𝑎, 𝑏)$ if $𝑓 (𝑥, 𝑦) \geq 𝑓 (𝑎, 𝑏)$ for all $(𝑥, 𝑦)$ near $(𝑎, 𝑏)$ . Analogously, a local maximum occurs at $(𝑎, 𝑏)$ if $𝑓 (𝑥, 𝑦) \leq 𝑓 (𝑎, 𝑏)$ for all $(𝑥, 𝑦)$ near $(𝑎, 𝑏)$ .

A saddle point is a point where every neighborhood contains points at which the function is both larger and smaller.

In this section we will mainly be concerned with how to find local maxima and minima. A global maximum or minimum compares a point with the entire domain, not merely nearby points. Global extrema may occur on a boundary, occur where a derivative does not exist, or fail to exist altogether; the following chapter develops the extra candidate checks needed for those problems.

How can we find an equation to specify local extrema? In calculus I we had a nice approach using differentiation: at a local max or min a function is neither increasing nor decreasing so its derivative is zero. The same technique works here, where we consider each partial derivative independently!

Theorem 14.2 (The Gradient at Extrema). At an interior local maximum or minimum where $𝑓$ is differentiable, every directional derivative is zero because the point is a local maximum or minimum in every direction. In particular, all partial derivatives are zero, so the gradient is zero.

Figure 14.1 Hunt for extrema by watching the tangent plane. The point tours the landscape, pausing wherever the plane lies dead level—and those are exactly the points where

\nabla 𝑓 = ⟨ 0, 0 ⟩

, all eight of them marked on the floor. At an interior maximum or minimum the plane must be flat, because any tilt leaves a direction that still goes uphill. So the flat spots are the complete list of differentiable interior candidates; sorting out which is which is the rest of the chapter.

Definition 14.3 (Critical Points). The critical points of a function are interior points where the gradient is zero or where one or more first partial derivatives do not exist.

Like in Calculus I, we have to be careful as not all critical points are actually maxima or minima. The standard example there is $𝑦 = 𝑥 3$ which has $𝑦' = 3 𝑥 2$ equal to zero at $𝑥 = 0$ , even though this is not the location of an extremum but rather a point of inflection. Similarly, for multivariable functions the existence of a critical point does not imply the existence of an extremum. The easiest and most common counter-example here is the saddle.

Figure 14.2 The warning, in its canonical form. At the origin of the saddle both axis slices have horizontal tangent lines—

\nabla 𝑓 (0, 0) = ⃗ 0

—yet there is no extremum: the slice along

𝑥

bottoms out while the slice along

𝑦

peaks, so every neighborhood contains both higher and lower ground. The second tab shows the one-variable ancestor,

𝑓 (𝑥) = 𝑥 3

at its inflection. A critical point is a candidate, not a conclusion.

Example 14.4 (Critical Points of $x^3+y^3+6xy$). Find the critical points of

𝑓 (𝑥, 𝑦) = 𝑥 3 + 𝑦 3 + 6 𝑥 𝑦 .

The gradient is

\nabla 𝑓 = ⟨ 3 𝑥 2 + 6 𝑦, 3 𝑦 2 + 6 𝑥 ⟩ .

Setting both components equal to zero gives

𝑥 2 + 2 𝑦 = 0, 𝑦 2 + 2 𝑥 = 0 .

Substitution yields the two solutions

(𝑥, 𝑦) = (0, 0) a n d (𝑥, 𝑦) = (- 2, - 2) .

These are the only critical points, but we still need second-order information to decide what happens at each one.

14.2Hessian Geometry and the Second-Derivative Test

Solving the system of equations arising from setting the gradient to zero is the analog of the first derivative test. What's the analog of the second derivative test? In Calculus I, this was looking for the "concavity" of the function, which was simply up or down. But we already know in multiple variables things are more complicated: there are hills, bowls and saddles to contend with.

Our tool to see which is the best local description is the quadratic approximation, which is particularly simple at a critical point. The zeroth order term is just a constant (which shifts a graph up or down but doesn't affect its shape), and the linear terms are zero - that's the definition of a critical point! Thus all we are left with are the quadratic terms, which were determined by the Hessian - the matrix of second derivatives.

Definition 14.5 (Quadratic Approximation at a Critical Point). Let $⃗ 𝑝 = (𝑎, 𝑏)$ be a critical point and write

𝐴 = 𝑓 𝑥 𝑥 (⃗ 𝑝), 𝐵 = 𝑓 𝑥 𝑦 (⃗ 𝑝), 𝐶 = 𝑓 𝑦 𝑦 (⃗ 𝑝) .

Near the critical point, the quadratic approximation is

𝑓 (𝑎 + ℎ, 𝑏 + 𝑘) \approx 𝑓 (𝑎, 𝑏) + 12 (𝐴 ℎ 2 + 2 𝐵 ℎ 𝑘 + 𝐶 𝑘 2) .

Once we have a quadratic approximation to a surface we have an even better understanding of what it looks like near a point. Of course, that requires that we know what quadratic surfaces look like - and hence why we spent time on those earlier this semester! Generic nondegenerate quadratic models come in three types: hills, bowls and saddles.

At a critical point, a positive quadratic expression gives a bowl and a local minimum, a negative quadratic expression gives a hill and a local maximum, and an expression which takes both signs gives a saddle.

Figure 14.3 At a critical point the linear terms vanish, so the quadratic terms are the whole local story—and three numbers write them:

𝑞 = 12 (𝐴 ℎ 2 + 2 𝐵 ℎ 𝑘 + 𝐶 𝑘 2)

. Steer the sliders and watch the surface and its level sets together: nested ellipses while

𝐷 = 𝐴 𝐶 - 𝐵 2 > 0

(a bowl or a hill, by the sign of

𝐴

), twisting into crossing hyperbolas the moment

𝐷

turns negative. The mixed term

𝐵

is the troublemaker—enough of it turns any bowl into a saddle, which is exactly why the test needs

𝐷

and not just

𝐴

and

𝐶

To determine whether our function has a maximum, minimum, or saddle at a given critical point, we need a formula involving $𝐴$ , $𝐵$ , and $𝐶$ that determines the shape of the graph. Suppose first that $𝐴 \neq 0$ . Completing the square gives

𝐴 ℎ 2 + 2 𝐵 ℎ 𝑘 + 𝐶 𝑘 2 = 𝐴 (ℎ + 𝐵 𝐴 𝑘) 2 + 𝐴 𝐶 - 𝐵 2 𝐴 𝑘 2 .

Set

𝐷 = 𝐴 𝐶 - 𝐵 2 = d e t 𝐻 𝑓 (⃗ 𝑝) .

If $𝐷 > 0$ , the coefficients $𝐴$ and $𝐷 / 𝐴$ have the same sign, so the quadratic expression is either always positive or always negative away from the origin. If $𝐷 < 0$ , those coefficients have opposite signs, so the expression takes both positive and negative values. This is the source of the second-derivative test.

Theorem 14.6 (Second-Derivative Test). Suppose $𝑓$ has continuous second partial derivatives near a critical point $⃗ 𝑝$ . Let

𝐷 = 𝑓 𝑥 𝑥 (⃗ 𝑝) 𝑓 𝑦 𝑦 (⃗ 𝑝) - 𝑓 𝑥 𝑦 (⃗ 𝑝) 2 .

Then

$⃗ 𝑝$ is a saddle if $𝐷 < 0$ .
$⃗ 𝑝$ is a local minimum if $𝐷 > 0$ and $𝑓 𝑥 𝑥 (⃗ 𝑝) > 0$ .
$⃗ 𝑝$ is a local maximum if $𝐷 > 0$ and $𝑓 𝑥 𝑥 (⃗ 𝑝) < 0$ .
If $𝐷 = 0$ , the test is inconclusive.

Although the completed-square calculation divided by $𝐴$ , the theorem also covers the edge case $𝐴 = 0$ . In particular, if $𝐷 < 0$ , the point is still a saddle. When $𝐷 = 0$ , there is a flat quadratic direction and higher-order terms may decide the shape. This is analogous to the one-variable case $𝑓 ″ (𝑎) = 0$ : the second-derivative test simply has no conclusion.

It is possible to go beyond the quadratic approximation and understand points for which this test is inconclusive, but doing so requires more complicated mathematics.

Figure 14.4 The test at work on

𝑓 = 𝑥 3 + 𝑦 3 + 6 𝑥 𝑦

. Its gradient vanishes at exactly two points; visit each, read off

𝐴

𝐵

𝐶

, and form

𝐷 = 𝐴 𝐶 - 𝐵 2

: the quadratic model standing over the point confirms the verdict—a saddle at the origin and a local maximum at

(- 2, - 2)

. Drag the point anywhere else and the test has nothing to say: where

\nabla 𝑓 \neq ⃗ 0

the function simply slopes, and no test is needed.

It is helpful to confirm that this test works in several examples.

Example 14.7 ($x^2+y^2-2x-6y+14$). Find and classify the critical points of

𝑓 (𝑥, 𝑦) = 𝑥 2 + 𝑦 2 - 2 𝑥 - 6 𝑦 + 14 .

Since

\nabla 𝑓 = ⟨ 2 𝑥 - 2, 2 𝑦 - 6 ⟩,

the only critical point is $(1, 3)$ . Here

𝐴 = 2, 𝐵 = 0, 𝐶 = 2, 𝐷 = 4 > 0 .

Because $𝐴 > 0$ , this point is a local minimum. Its value is $𝑓 (1, 3) = 4$ .

Example 14.8 ($x^3+y^3+6xy$). We already found the critical points $(0, 0)$ and $(- 2, - 2)$ . The Hessian data is

𝑓 𝑥 𝑥 = 6 𝑥, 𝑓 𝑥 𝑦 = 6, 𝑓 𝑦 𝑦 = 6 𝑦,

𝐷 = 36 𝑥 𝑦 - 36 .

At $(0, 0)$ , $𝐷 = - 36 < 0$ , so the origin is a saddle. At $(- 2, - 2)$ , $𝐷 = 108 > 0$ and $𝑓 𝑥 𝑥 = - 12 < 0$ , so $(- 2, - 2)$ is a local maximum.

Example 14.9 ($2x^3-xy+6xy^2$). Find and classify the critical points of

𝑓 (𝑥, 𝑦) = 2 𝑥 3 - 𝑥 𝑦 + 6 𝑥 𝑦 2 .

The first partial derivatives are

𝑓 𝑥 = 6 𝑥 2 - 𝑦 + 6 𝑦 2, 𝑓 𝑦 = 𝑥 (- 1 + 12 𝑦) .

Solving $𝑓 𝑥 = 𝑓 𝑦 = 0$ gives four critical points:

(0, 0), (0, 16), (112, 112), (- 112, 112) .

The second derivatives are

𝑓 𝑥 𝑥 = 12 𝑥, 𝑓 𝑥 𝑦 = - 1 + 12 𝑦, 𝑓 𝑦 𝑦 = 12 𝑥 .

Thus $(0, 0)$ and $(0, 1 / 6)$ have $𝐷 = - 1$ and are saddles. At $(1 / 12, 1 / 12)$ , $𝐷 = 1$ and $𝑓 𝑥 𝑥 = 1$ , giving a local minimum. At $(- 1 / 12, 1 / 12)$ , $𝐷 = 1$ and $𝑓 𝑥 𝑥 = - 1$ , giving a local maximum.

In higher dimensions, the same idea survives even though the two-variable determinant shortcut does not. If the quadratic term is positive in every direction, we have a local minimum; if it is negative in every direction, a local maximum; and if it takes both signs, a saddle.

14.3Critical Points and Contour Geometry

Having precise mathematical tools to understand the critical points of a function allows us to understand much of the local behavior of the function through its contour plot.

At a regular point, the gradient is nonzero and the linear approximation

𝑓 (⃗ 𝑝 + ⃗ ℎ) \approx 𝑓 (⃗ 𝑝) + \nabla 𝑓 (⃗ 𝑝) \cdot ⃗ ℎ

dominates nearby. The level sets of this linear model are parallel lines, which explains why sufficiently close to a regular point the contours look nearly parallel.

At a nondegenerate critical point, the linear term vanishes and one of three quadratic models controls the local picture:

𝑢 2 + 𝑣 2, - 𝑢 2 - 𝑣 2, 𝑢 2 - 𝑣 2 .

The first two produce nested contours around a minimum or maximum. The third produces hyperbolas, and at the saddle value its single singular level set crosses itself. Distinct level sets never cross.

We can plot and label critical points on an $𝑥 𝑦$ plane, and then draw little local models of what the contours must look like nearby, since we know the contours for maxima, minima, and saddles. We can then extend these curves to guide a larger qualitative sketch.

Figure 14.5 How to begin a contour plot you have never seen. First mark the nondegenerate critical points, then stamp the local model at each: nested loops around every maximum and minimum, a crossing at every saddle. Away from critical points, nearby contours look locally parallel and distinct levels do not cross. These facts strongly constrain a qualitative sketch, but local critical-point data does not uniquely determine every feature of the global contour plot. The bold saddle-level curves provide a useful skeleton for one compatible completion.

The observation behind this method is that nothing singular happens at a regular point: if the first derivative is nonzero, then the function is increasing in some direction, and the level sets nearby locally look like a set of parallel lines! This is a gateway to a huge amount of modern and advanced mathematics called Morse theory.

For sufficiently regular functions with nondegenerate critical points, Morse theory relates changes in level sets to the local models at those critical points. Degenerate critical points and global topology can produce subtler behavior, so the three clean pictures above are local models rather than a complete global classification.

Optional application: Gradient descent. Chapter 13 showed that $- \nabla 𝑓$ is the direction of steepest decrease. Gradient descent turns that geometric fact into an iterative algorithm:

⃗ 𝑥 𝑘 + 1 = ⃗ 𝑥 𝑘 - 𝜂 \nabla 𝑓 (⃗ 𝑥 𝑘),

where the positive number $𝜂$ is the learning rate. A small learning rate takes cautious steps; a large one can overshoot or bounce across a valley. The method may find different local minima from different starting points, and saddle points can slow or redirect the iteration.

Figure 14.6 The gradient's geometry, run as an algorithm: from the starting point, step against the gradient and repeat—

⃗ 𝑥 𝑘 + 1 = ⃗ 𝑥 𝑘 - 𝜂 \nabla 𝑓 (⃗ 𝑥 𝑘)

. In this example the landscape sits inside a steep circular basin, so every displayed descent settles in one of the blue minima. A small learning rate

𝜂

creeps reliably downhill; a large one overshoots the valley and ricochets between its walls. Move the start and the same rule finds different minima—descent only seeks a local minimum, and which one it reaches depends on where you begin.

This chapter found and classified unconstrained local behavior. The next chapter adds constraints: the allowable points may lie on a curve or inside a closed region, so boundaries and corners create new candidates that the equation $\nabla 𝑓 = ⃗ 0$ cannot see by itself.