5 Optimization

5.1 The necessity of being optimal

One of the main uses for derivatives is to solve optimization problems, where we try to find the inputs that lead to the lowest (minimal) or highest (maximal) values of a function. Optimization problems are everywhere in both statistics and formal theory. In statistics, we want to find the parameter estimates that best fit the data. In game theory, we want to find the optimal strategy out of all of the options available to a player.

For functions with a finite domain, it is conceptually simple (though perhaps tedious in practice) to find the maximum and minimum values. Plug in every x \in X, find the associated function values f(x), and track which inputs lead to the highest and lowest values. It is not so simple when the domain is infinite, such as an interval of real numbers. We cannot enumerate every possible value of f(x), so we must be more clever to make firm statements about maximal and minimal values.

Using derivatives, we can sharply narrow down the set of inputs x \in X that might lead to a maximal or minimal value of the function f(x). If you look at the graph of a differentiable function at the top of a peak or the bottom of a valley, it is basically flat.

Figure 5.1: Differentiable functions are approximately flat at their peaks and valleys.

In calculus terms, the derivative of the function is 0 at the peak or valley. This is not an accident or a quirk of particular functions. When we search for maximal or minimal values of a differentiable function, we will be focusing on those points where its derivative equals 0.

5.2 Definitions

Like a mountain range or a long-running TV series, a function can have many peaks and valleys, as in Figure 5.2 below.

Figure 5.2: A function with multiple peaks and valleys.

Here are the points of interest in this graph:

At a, the lower endpoint, the function is increasing. When x is just above a, the function value is greater than f(a).
The first peak occurs at x_1. The function value here, f(x_1), is greater than the values when x is just above or just below x_1. Consequently, we call x_1 a local maximizer. However, as we’ll see, it’s not the highest peak of the function.
There’s a valley at x_2. The function value here, f(x_2), is lower than the values when x is just above or just below x_2, making x_2 a local minimizer. However, this is not the overall low point of the function.
There’s a second peak at x_3, and this is where the function reaches its highest value overall. As such, we call x_3 a global maximizer of the function.
At b, the upper endpoint, the function reaches its lowest value overall. This makes b the global minimizer of the function.

The formal definition of a global maximizer is reasonably straightforward: it is the point along the domain where the function reaches its highest value.

Definition 5.1 (Global maximizers and minimizers) Consider a function f : X \to \mathbb{R}.

We call x^* \in X a global maximizer of f when f(x^*) \geq f(x) for all x \in X. If x^* is a global maximizer of f, then we call f(x^*) the maximum of f: f(x^*) = \max_{x \in X} f(x).

Similarly, we call x^* \in X a global minimizer of f when f(x^*) \leq f(x) for all x \in X. If x^* is a global minimizer of f, then we call f(x^*) the minimum of f: f(x^*) = \min_{x \in X} f(x).

A function may have multiple global maximizers or minimizers. As a trivial example, consider the constant function f : \mathbb{R} \to \mathbb{R} defined by f(x) = 0 for all x \in \mathbb{R}. Every real number is both a global maximizer and a global minimizer of this function.

It is a bit trickier to define a “local” maximizer. Intuitively, we want to say that the value of the function at the local maximizer is at least as high as at any other nearby point. But what qualifies as “nearby”? To define this, we will use the same kind of logic as in our definition of the limit of a function (Proposition 2.1 and Proposition 2.2). Specifically, we will call x^* a local maximizer if there is an interval of any positive width around it where the function value doesn’t go higher.

Definition 5.2 (Local maximizers and minimizers) Consider a function f : X \to \mathbb{R}, where X \subseteq \mathbb{R}.

We call x^* \in X a local maximizer of f when there is some d > 0 such that f(x^*) \geq f(x) for all x \in X \cap (x^* - d, x^* + d).

Similarly, we call x^* \in X a local minimizer of f when there is some d > 0 such that f(x^*) \leq f(x) for all x \in X \cap (x^* - d, x^* + d).

To try and unpack this definition, let’s work through an example of proving—without yet using derivatives—that a particular point is a local maximizer. Consider the function f : [-2, 2] \to \mathbb{R} defined as follows, which has a sort of W-shaped graph (see Figure 5.3): \begin{aligned} f(x) &= \begin{cases} -2x - 3 & \text{if $x \leq -1$,} \\ -x^2 & \text{if $-1 < x < 1$,} \\ 2x - 3 & \text{if $x \geq 1$.} \end{cases} \end{aligned} \tag{5.1}

Figure 5.3: A W-shaped function with a local maximum at x = 0.

We can see from the graph that there is a local maximum at x = 0. We have f(0) = 0, yet f(x) < 0 for any other x in the vicinity of 0, making x = 0 a local maximizer. How do we make this argument using the formal definition? Well, we need to find a small enough interval around x = 0 for which all f(x) \leq 0. From looking at the definition of the function, it seems that an interval of any length less than 1 will suffice.

To formally prove that x = 0 is a local maximizer as defined by Definition 5.2, take any d that satisfies 0 < d < 1. For all x \in (0 - d, 0 + d), we have f(x) = -x^2 \leq 0 = f(0). Therefore, x = 0 is a local maximizer of f.

Exercise 5.1 Prove that x = 1 is a local minimizer of the W-shaped function f from Equation 5.1.

Answer

Take any d that satisfies 0 < d < 1, so that (1 - d, 1 + d) \subseteq (0, 2). For all x \in (1 - d, 1), we have 0 < x < 1, so f(x) = -x^2 > -1 = f(1). For all x \in [1, 1 + d), we have f(x) = 2x - 3 \geq -1 = f(1). Therefore, x = 1 is a local minimizer of f.

5.3 Existence and non-existence of solutions

A maximization or minimization problem may not have a solution. For example, consider the identity function on the entire real line: f : \mathbb{R} \to \mathbb{R} defined by f(x) = x. No point x \in \mathbb{R} can be a maximizer of this function, because x + 1 is also in the domain and yet f(x + 1) > f(x). For similar reasons, no point x \in \mathbb{R} can be a minimizer either.

It is certainly frustrating to work on a problem only to find that it has no solution. One way to avoid this frustration is to work on problems that we know must have a solution, even if perhaps we don’t know what that solution is. The following theorem, which is an application of the Weierstrass extreme value theorem, gives us sufficient conditions for the existence of a global maximizer and minimizer.

Theorem 5.1 (Extreme value theorem) If f : [a, b] \to \mathbb{R} is continuous, then it has a global minimizer and maximizer; i.e., \min_{x \in [a, b]} f(x) and \max_{x \in [a, b]} f(x) are well-defined.

A more general statement of the extreme value theorem

The statement here is actually true for any continuous function f : X \to \mathbb{R} whose domain X \subseteq \mathbb{R} is closed and bounded.

X is closed if it meets the following condition: for any real number y, if y \notin X, then there is a real number d > 0 such that (y - d, y + d) \cap X = \emptyset. A way to think about this is that for any point outside of X, there is some non-zero amount of “separation” between that point and the boundary of X.

An interval that contains its endpoints, [a, b], is perhaps the simplest example of a closed set. But there are many other closed sets. For example, any finite set is closed, and so is a finite union of closed sets like [a, b] \cup [b + 1, c]. Finally, the set of all real numbers, \mathbb{R}, is closed—there is no real number y that is not in \mathbb{R}, so the condition to be closed is satisfied trivially.

The boundedness condition is perhaps easier to wrap your head around. X is bounded if there exist numbers \ell \in \mathbb{R} and h \in \mathbb{R} such that \ell \leq x \leq h for all x \in X.

Theorem 5.1 is giving us three conditions which, together, guarantee the existence of solutions to the global optimization problem.

Continuity. This condition ensures that the function can’t get closer and closer to a maximum or minimum, but then suddenly jump away.

See Figure 5.4 for an example of how a discontinuous function may lack a global maximum or minimum. From the graph, it looks like the global minimizer “should” be 0, as the function approaches a low point as we get closer and closer to x = 0. But then the value of the function suddenly jumps up once we actually reach x = 0. Consequently, there is no global minimizer. You can get close to the low point by picking some value of x that’s really close to 0—but there will always be some x whose function value is a bit lower.

Figure 5.4: A discontinuous function with no global maximizer or minimizer.
Bounded domain. This ensures that the function cannot go off to infinity in either direction.

Figure 5.5 shows why a function with an unbounded domain might not have a global maximizer or minimizer. It plots the identity function, f(x) = x, which as discussed at the start of this section, does not have any global optima—no matter where you are on the x-axis, you can always find a value of the function that’s higher (by moving to the right) or lower (by moving to the left).

Figure 5.5: A function on an unbounded domain with no global maximizer or minimizer.
Closed domain. This one is actually similar to the continuity condition. It ensures that the function can’t get closer and closer to a maximum or minimum at a boundary point, only to be undefined at the boundary point itself.

Figure 5.6 illustrates this condition. It plots the identity function, f(x) = x, on a domain that does not include its endpoints. So the function approaches what “should” be its global minimizer as we approach the lower endpoint on the x-axis, but it never quite gets there. Same for the global maximizer as we approach the upper endpoint.

Figure 5.6: A function on a non-closed domain with no global maximizer or minimizer.

Continuity and a closed, bounded domain are sufficient for the existence of global optima, but not necessary. Discontinuous functions, functions with unbounded domains, and functions with domains that are not closed may have global maximizers and minimizers. So when you have such a function, you don’t have to give up on trying to optimize it—you just can’t go in assuming there’s a solution, as you could with a continuous function on a closed and bounded domain.

Exercise 5.2 (Optimization when the sufficient conditions fail) Come up with an example of a function f : X \to \mathbb{R} that is not continuous, whose domain is unbounded, and whose domain is not closed, but which has a global minimizer and maximizer.

Answer

There are infinitely many examples I could give, but here is a relatively simple one. Consider the function f : (0, \infty) \to \mathbb{R} defined by \begin{aligned} f(x) = \begin{cases} 0 & \text{if $x \neq 7$,} \\ 1 & \text{if $x = 7$.} \end{cases} \end{aligned} f is discontinuous, as \lim_{x \to 7} f(x) = 0 \neq f(7). Its domain is unbounded, and it is not closed as it does not contain the lower endpoint at 0. However, we have f(1) = 0 \leq f(x) \leq 1 = f(7) for all x \in (0, \infty), so 1 is a global minimizer and 7 is a global maximizer.

5.4 Derivative conditions for local optima

5.4.1 First-order conditions

You might have noticed that a function tends to be nearly flat in the vicinity of a local maximum or minimum, with the possible exception of one that occurs at the endpoint of its domain. To illustrate, let’s look at the “interior” (i.e., not at the endpoints) local maximizers and minimizers of the function from Figure 5.2.

Figure 5.7: The function from Figure 5.2 is flat at its interior local maximizers and local minimizer.

In fact, for a function that is differentiable on its entire domain, we can rule out a local maximizer or minimizer at any interior point where f'(x) \neq 0. For example, imagine that f'(x) > 0, meaning that the function is increasing at x. Then at any value y just above x, it must be the case that f(y) > f(x). Therefore, x is not a local maximizer. But it is also not a local minimizer, as at any value w just below x, we must have f(w) < f(x). You can use a mirror image of this argument to rule out a local maximizer or minimizer at a point where f'(x) < 0.

Now we’ve seen why f'(x) \neq 0 implies that x is not a local maximizer or minimizer (unless perhaps x is one of the endpoints of the domain). Therefore, if x is a local maximizer or minimizer, it must be the case that f'(x) = 0. We call this requirement the first-order condition for a local optimum.

Theorem 5.2 (First-order necessary condition) Let f : X \to \mathbb{R} be differentiable, where X \subseteq \mathbb{R} is an interval. If x^* is a local maximizer or minimizer of f and is not an endpoint of X, then x^* is a critical point, meaning f'(x^*) = 0.

Formal proof of Theorem 5.2

I will prove the following equivalent statement (formally, the contrapositive of Theorem 5.2): if x^* is not an endpoint of X and f'(x^*) \neq 0, then x^* is neither a local maximizer nor a local minimizer.

Suppose x^* is not an endpoint of X, meaning there is a value \eta > 0 such that (x - \eta, x + \eta) \subseteq X, and that f'(x^*) \neq 0. We will consider the case in which f'(x^*) > 0. (The proof for the opposite case is so similar that it would be a waste of my time to type it out and a waste of your time to read it. Or, in math-speak, “The proof for the opposite case is analogous.”) By the definition of the derivative, \lim_{x \to x^*} \frac{f(x) - f(x^*)}{x - x^*} = f'(x^*) > 0. According to the formal definition of a limit (Definition 2.6), there is a \delta \in (0, \eta) such that \frac{f(x) - f(x^*)}{x - x^*} > 0 for all x \in (x^* - \delta, x^*) \cup (x^*, x^* + \delta).

For x \in (x^*, x^* + \delta), the denominator x - x^* is positive, so the numerator must be positive too: f(x) > f(x^*). Every interval around x^*, no matter how small, contains such points, so x^* is not a local maximizer.
For x \in (x^* - \delta, x^*), the denominator x - x^* is negative, so the numerator must be negative too: f(x) < f(x^*). Every interval around x^*, no matter how small, contains such points, so x^* is not a local minimizer.

We have shown that if f'(x^*) \neq 0, then x^* is not a local maximizer or minimizer. It is logically equivalent that if x^* is a local maximizer or minimizer, then f'(x^*) = 0.

Theorem 5.2 drastically reduces the amount of guess-and-check we have to do to find the maximizers and minimizers of a differentiable function. It tells us that any local (and thus any global) optimum must occur at a critical point or an endpoint. Therefore, to find the global optimizers of a differentiable function on a domain [a, b], we can follow an algorithm:

Find all critical points by solving for x in the equation f'(x) = 0.
Letting x_1, \ldots, x_M denote the critical points of the function, plug these and the endpoints into the function to calculate the values f(a), f(x_1), \ldots, f(x_M), f(b).
The global minimizer(s) are whichever input(s) gave the lowest value in the last step. The global maximizer(s) are the one(s) that gave the highest value.

Exercise 5.3 (Optimization by brute force) Find the global minimizers and maximizers of f : [-3, 3] \to \mathbb{R} defined by f(x) = 2 x^3 - 3 x^2 - 12 x + 4.

Answer

First let’s find the critical points. Using the sum rule, the constant multiple rule, and the power rule, we have \begin{aligned} f'(x) &= 6 x^2 - 6 x - 12 \\ &= 6 (x^2 - x - 2) \\ &= 6 (x - 2) (x + 1). \end{aligned} Therefore, the critical points of the function are x = -1 and x = 2. This gives us four points to evaluate to find the global optima, namely the two endpoints and the two critical points.

f(-3) = 2 \cdot (-27) - 3 \cdot 9 - 12 \cdot (-3) + 4 = -41.
f(-1) = 2 \cdot (-1) - 3 \cdot 1 - 12 \cdot (-1) + 4 = 11.
f(2) = 2 \cdot 8 - 3 \cdot 4 - 12 \cdot 2 + 4 = -16.
f(3) = 2 \cdot 27 - 3 \cdot 9 - 12 \cdot 3 + 4 = -5.

Therefore, the global maximizer is x = -1 and the global minimizer is x = -3.

5.4.2 Second-order conditions

You might have noticed that a function tends to look concave near a local maximum, and it tends to look convex near a local minimum. For example, let me take the function from Figure 5.2 above and label the regions where it is concave versus where it is convex.

Figure 5.8: The function from Figure 5.2, with its concave regions shaded.

This pattern—concave near a maximum, convex near a minimum—is not a fluke of this particular graph. To see why, think about a critical point x^* where the second derivative is negative. (The same logic, in reverse, will apply when the second derivative is positive.)

Because f''(x^*) < 0, the first derivative is decreasing as we pass through x^*.
Because x^* is a critical point, the first derivative is decreasing through zero. So it must be positive at values of x just below x^*, and negative at values of x just above x^*.
Positive f' just below x^* means the function is going up as we approach x^* from the left. Negative f' just above x^* means the function is going down as we leave x^* to the right. So x^* is at the top of a hill—a local maximizer.

In other words, the value of the second derivative at a critical point can tell us whether that point is a local maximizer or minimizer. Because we are evaluating the second derivative to determine the type of local optimum, we call this a second-order condition.

Theorem 5.3 (Second-order sufficient condition) Let f : X \to \mathbb{R} be twice differentiable, where X \subseteq \mathbb{R} is an interval. Let x^* be a critical point of f that is not an endpoint of X.

If f''(x^*) < 0, then x^* is a local maximizer of f.
If f''(x^*) > 0, then x^* is a local minimizer of f.

Very often, we can identify all interior local maximizers and minimizers of a function just through the first- and second-order conditions. We find all critical points for solving for x in the first-order condition f'(x) = 0, then we calculate f''(x) at each critical point to determine whether it is a local maximizer or minimizer.

Exercise 5.4 (Applying the second-order condition) Consider the function from Exercise 5.3, f(x) = 2 x^3 - 3 x^2 - 12 x + 4. Use the second-order sufficient conditions to show that x = -1 is a local maximizer and that x = 2 is a local minimizer.

Answer

We have the first and second derivatives \begin{aligned} f'(x) &= 6 x^2 - 6 x - 12, \\ f''(x) &= 12 x - 6. \end{aligned} We already saw in the answer to Exercise 5.3 that x = -1 and x = 2 are critical points. Then, we have f''(-1) = -12 - 6 = -18 < 0, so x = -1 is a local maximizer, and we have f''(2) = 24 - 6 = 18 > 0, so x = 2 is a local minimizer.

The second-order conditions say nothing about the status of a critical point at which the second derivative equals zero. It could be a local maximizer, a local minimizer, or neither—you can’t tell from the second derivative alone.

Exercise 5.5 (Zero second derivative at a local minimizer) Consider the function f : \mathbb{R} \to \mathbb{R} defined by f(x) = x^4. Show that f'(0) = 0, that f''(0) = 0, and that x = 0 is a local (and indeed global) minimizer of f.

Answer

By the power rule, we have f'(x) = 4 x^3 and f''(x) = 12 x^2, which together imply f'(0) = f''(0) = 0. But we know that x = 0 is a local and global minimizer because f(0) = 0, while for all x \neq 0 we have f(x) = x^4 > 0.

Exercise 5.6 (A critical point that isn’t a local optimum) Consider the function f : \mathbb{R} \to \mathbb{R} defined by f(x) = x^3. Show that f'(0) = 0, that f''(0) = 0, and that x = 0 is neither a local maximizer nor a local minimizer.

Answer

By the power rule, we have f'(x) = 3 x^2 and f''(x) = 6 x, which together imply f'(0) = f''(0) = 0.

To see that x = 0 is not a local maximizer or minimizer, take any interval of width d > 0 around x = 0, i.e., (-d, d). For any w \in (-d, 0), we have f(w) < f(0). Similarly, for any y \in (0, d), we have f(y) > f(0). Therefore, no matter how small an interval we look at around x = 0, the point x = 0 is not a global maximizer or minimizer restricted to that interval—meaning x = 0 is not a local maximizer or minimizer of the function overall.

5.5 Global optimization

In both statistics and formal theory, we are typically interested in the global optimum more so than a local optimum. In statistics, we want to find the parameter estimates that best fit the data, not just the ones where no other “nearby” estimate would fit the data better. In game theory, we want to find the optimal strategy out of all of the options available to a player, not just the best among a few similar options. These are both global optimization problems.

For functions with bounded, closed domains, we have seen that we can brute force our way to the global maximizers and minimizers by evaluating the function at the critical points and the endpoints. But sometimes we run into problems where we can’t sensibly place bounds on the domain. For example, think about finding the regression slope that best fits a particular dataset—you want to find the best of all possible slopes, not to place some kind of arbitrary a priori constraint on the set of coefficients under consideration.

With some optimization problems, we are lucky enough to be able to make statements about a global maximizer or minimizer on the basis of calculus criteria alone. In particular, in the special case where the second derivative of a function has the same sign throughout the entire domain, the first-order condition is not only necessary for a local optimum, but sufficient for a global optimum.

Theorem 5.4 (Sufficient conditions for global optimization) Let f : X \to \mathbb{R} be twice differentiable, where X \subseteq \mathbb{R} is an interval. (The restriction to an interval is not limited to bounded intervals; intervals like (0, \infty) or even the entire real line also count.)

If f''(x) < 0 for all x \in X, then there is at most one critical point x^* \in X. If such a critical point exists, it is the unique global maximizer (i.e., no other point in the domain is a global maximizer).
If f''(x) > 0 for all x \in X, then there is at most one critical point x^* \in X. If such a critical point exists, it is the unique global minimizer.

Here’s the intuition behind this result. If the second derivative is negative throughout the domain, then the function is strictly concave. A strictly concave function can have one of three shapes:

Strictly increasing on its domain, so the right endpoint (if included in the domain) is the global maximizer.
Strictly decreasing on its domain, so the left endpoint (if included in the domain) is the global maximizer.
Strictly increasing for low x and then strictly decreasing thereafter, so there is one interior local maximizer and this is also the global maximizer.

Figure 5.9: Possible shapes of a strictly concave function.

Once the function has started decreasing as you move to the right along the x-axis, it can’t flip back to increasing—that would mean the first derivative is going from negative to positive, which in turn would imply a positive second derivative in that region of the domain. Therefore, a function with a negative second derivative throughout its domain cannot have an interior local minimizer.

Exercise 5.7 (A global maximizer on an unbounded domain) Consider the function f : (0, \infty) \to \mathbb{R} defined by f(x) = \log x - x.

Use Theorem 5.4 to show that x = 1 is the unique global maximizer of f.
Show that f has no global minimizer.

Answer

The first and second derivatives are \begin{aligned} f'(x) &= \frac{1}{x} - 1, \\ f''(x) &= -\frac{1}{x^2}. \end{aligned} The second derivative is continuous and satisfies f''(x) < 0 for all x \in (0, \infty). We have f'(1) = 1 - 1 = 0, so x = 1 is a critical point. Because the domain is an interval, Theorem 5.4 implies that x = 1 is the unique global maximizer.
For any x \in (0, \infty), we can find a domain point with a lower function value. Let n be any positive whole number with n > -f(x), and consider the domain point e^{-n}. Then f(e^{-n}) = -n - e^{-n} < -n < f(x). So no domain point can be a global minimizer. (This doesn’t contradict the extreme value theorem, because the domain is neither bounded nor closed.)

5.6 Concept review

Global maximizers and minimizers: A domain point x^* is a global maximizer (minimizer) of the function f if f(x^*) \geq (\leq) f(x) for all x in the domain.
Maximum and minimum: If x^* is a global maximizer (minimizer) of f, then f(x^*) is the maximum (minimum) of f.
Local maximizers and minimizers: A domain point x^* is a local maximizer (minimizer) of the function f if there is a value d > 0 for which f(x^*) \geq (\leq) f(x) for all domain points x that satisfy x^* - d < x < x^* + d.
First-order condition: The requirement that f'(x) = 0 at any local maximizer or minimizer that is not at an endpoint of the domain.
Critical point: A point x in the domain of a differentiable function is a critical point if f'(x) = 0.
Second-order condition: Any critical point at which the second derivative is negative (positive) is a local maximizer (minimizer).

Critical point: A point x in the domain of a differentiable function is a critical point if f'(x) = 0.
First-order condition: The requirement that f'(x) = 0 at any local maximizer or minimizer that is not at an endpoint of the domain.
Global maximizers and minimizers: A domain point x^* is a global maximizer (minimizer) of the function f if f(x^*) \geq (\leq) f(x) for all x in the domain.
Local maximizers and minimizers: A domain point x^* is a local maximizer (minimizer) of the function f if there is a value d > 0 for which f(x^*) \geq (\leq) f(x) for all domain points x that satisfy x^* - d < x < x^* + d.
Maximum and minimum: If x^* is a global maximizer (minimizer) of f, then f(x^*) is the maximum (minimum) of f.
Second-order condition: Any critical point at which the second derivative is negative (positive) is a local maximizer (minimizer).