$$\newcommand{\id}{\mathrm{id}}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\kernel}{\mathrm{null}\,}$$ $$\newcommand{\range}{\mathrm{range}\,}$$ $$\newcommand{\RealPart}{\mathrm{Re}}$$ $$\newcommand{\ImaginaryPart}{\mathrm{Im}}$$ $$\newcommand{\Argument}{\mathrm{Arg}}$$ $$\newcommand{\norm}[1]{\| #1 \|}$$ $$\newcommand{\inner}[2]{\langle #1, #2 \rangle}$$ $$\newcommand{\Span}{\mathrm{span}}$$

# 13.9: Constrained Optimization

[ "article:topic" ]

$$\newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} }$$

$$\newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}}$$

When optimizing functions of one variable such as $$y=f(x)$$, we made use of Theorem 25, the Extreme Value Theorem, that said that over a closed interval $$I$$, a continuous function has both a maximum and minimum value. To find these maximum and minimum values, we evaluated $$f$$ at all critical points in the interval, as well as at the endpoints (the "boundary'') of the interval.

A similar theorem and procedure applies to functions of two variables. A continuous function over a closed set also attains a maximum and minimum value (see the following theorem). We can find these values by evaluating the function at the critical values in the set and over the boundary of the set. After formally stating this extreme value theorem, we give examples.

theorem 116 Extreme Value Theorem

Let $$z=f(x,y)$$ be a continuous function on a closed, bounded set $$S$$. Then $$f$$ has a maximum and minimum value on $$S$$.

Example $$\PageIndex{6}$$: Finding extrema on a closed set

Let $$f(x,y) = x^2-y^2+5$$ and let $$S$$ be the triangle with vertices $$(-1,-2)$$, $$(0,1)$$ and $$(2,-2)$$. Find the maximum and minimum values of $$f$$ on $$S$$.

SOLUTION
It can help to see a graph of $$f$$ along with the set $$S$$. In Figure 12.31(a) the triangle defining $$S$$ is shown in the $$x$$-$$y$$ plane in a dashed line. Above it is the surface of $$f$$; we are only concerned with the portion of $$f$$ enclosed by the "triangle'' on its surface.

Figure 12.31: Plotting the surface of $$f$$ along with the restricted domain S.

We begin by finding the critical points of $$f$$. With $$f_x = 2x$$ and $$f_y = -2y$$, we find only one critical point, at $$(0,0)$$.

We now find the maximum and minimum values that $$f$$ attains along the boundary of $$S$$, that is, along the edges of the triangle. In Figure 12.31(b) we see the triangle sketched in the plane with the equations of the lines forming its edges labeled.

Start with the bottom edge, along the line $$y=-2$$. If $$y$$ is $$-2$$, then on the surface, we are considering points $$f(x,-2)$$; that is, our function reduces to $$f(x,-2) = x^2-(-2)^2+5 = x^2+1=f_1(x)$$. We want to maximize/minimize $$f_1(x)=x^2+1$$ on the interval $$[-1,2]$$. To do so, we evaluate $$f_1(x)$$ at its critical points and at the endpoints.

The critical points of $$f_1$$ are found by setting its derivative equal to 0:
$f'_1(x)=0\qquad \Rightarrow x=0.$
Evaluating $$f_1$$ at this critical point, and at the endpoints of $$[-1,1]$$ gives:
\begin{align*} f_1(-1) = 2 \qquad&\Rightarrow\qquad f(-1,-2) = 2\\ f_1(0) = 1 \qquad&\Rightarrow \qquad f(0,-2) = 1\\ f_1(2) = 5 \qquad&\Rightarrow \qquad f(2,-2) = 5. \end{align*}
Notice how evaluating $$f_1$$ at a point is the same as evaluating $$f$$ at its corresponding point.

We need to do this process twice more, for the other two edges of the triangle.

Along the left edge, along the line $$y=3x+1$$, we substitute $$3x+1$$ in for $$y$$ in $$f(x,y)$$:
$f(x,y) = f(x,3x+1) = x^2-(3x+1)^2+5 = -8x^2-6x+4 = f_2(x).$
We want the maximum and minimum values of $$f_2$$ on the interval $$[-1,0]$$, so we evaluate $$f_2$$ at its critical points and the endpoints of the interval. We find the critical points:
$f'_2(x) = -16x-6=0 \qquad \Rightarrow \qquad x=-3/8.$

Evaluate $$f_2$$ at its critical point and the endpoints of $$[-1,0]$$:
\begin{align*} f_2(-1) = 2 \qquad&\Rightarrow\qquad f(-1,-2) = 2\\ f_2(-3/8) = 41/8=5.125 \qquad&\Rightarrow \qquad f(-3/8,-0.125) = 5.125\\ f_2(0) = 1 \qquad&\Rightarrow \qquad f(0,1) = 4. \end{align*}

Finally, we evaluate $$f$$ along the right edge of the triangle, where $$y = -3/2x+1$$.
$f(x,y) = f(x,-3/2x+1) = x^2-(-3/2x+1)^2+5 = -\frac54x^2+3x+4=f_3(x).$
The critical points of $$f_3(x)$$ are:
$f'_3(x) = 0 \qquad \Rightarrow \qquad x=6/5=1.2.$
We evaluate $$f_3$$ at this critical point and at the endpoints of the interval $$[0,2]$$:
\begin{align*} f_3(0) = 4 \qquad&\Rightarrow\qquad f(0,1) = 4\\ f_3(1.2) = 5.8 \qquad&\Rightarrow \qquad f(1.2,-0.8) = 5.8\\ f_3(2) = 5 \qquad&\Rightarrow \qquad f(2,-2) = 5. \end{align*}
One last point to test: the critical point of $$f$$, $$(0,0)$$. We find $$f(0,0) = 5$$.

Figure 12.32: The surface of $$f$$ along with important points along the boundary of S and the interior.

We have evaluated $$f$$ at a total of 7 different places, all shown in Figure 12.32. We checked each vertex of the triangle twice, as each showed up as the endpoint of an interval twice. Of all the $$z$$-values found, the maximum is 5.8, found at $$(1.2,-0.8)$$; the minimum is 1, found at $$(0,-2)$$.

This portion of the text is entitled "Constrained Optimization'' because we want to optimize a function (i.e., find its maximum and/or minimum values) subject to a constraint -- some limit to what values the function can attain. In the previous example, we constrained ourselves by considering a function only within the boundary of a triangle. This was largely arbitrary; the function and the boundary were chosen just as an example, with no real "meaning'' behind the function or the chosen constraint.

However, solving constrained optimization problems is a very important topic in applied mathematics. The techniques developed here are the basis for solving larger problems, where more than two variables are involved.

We illustrate the technique once more with a classic problem.

Example $$\PageIndex{7}$$: Constrained Optimization

The U.S. Postal Service states that the girth+length of Standard Post Package must not exceed 130''. Given a rectangular box, the "length'' is the longest side, and the "girth'' is twice the width+height.

Given a rectangular box where the width and height are equal, what are the dimensions of the box that give the maximum volume subject to the constraint of the size of a Standard Post Package?

SOLUTION

Let $$w$$, $$h$$ and $$\ell$$ denote the width, height and length of a rectangular box; we assume here that $$w=h$$. The girth is then $$2(w+h) = 4w$$. The volume of the box is $$V(w,\ell) = wh\ell = w^2\ell$$. We wish to maximize this volume subject to the constraint $$4w+\ell\leq 130$$, or $$\ell\leq 130-4w$$. (Common sense also indicates that $$\ell>0, w>0$$.)

We begin by finding the critical values of $$V$$. We find that $$V_w = 2w\ell$$ and $$V_\ell = w^2$$; these are simultaneously 0 only at $$(0,0)$$. This gives a volume of 0, so we can ignore this critical point.

We now consider the volume along the constraint $$\ell=130-4w.$$ Along this line, we have:
$V(w\ell) = V(w,130-4w) = w^2(130-4w) = 130w^2-4w^3 = V_1(w).$
The constraint is applicable on the $$w$$-interval $$[0,32.5]$$ as indicated in the figure. Thus we want to maximize $$V_1$$ on $$[0,32.5]$$.

Finding the critical values of $$V_1$$, we take the derivative and set it equal to 0:
$V\,'_1(w) = 260w-12w^2 = 0 \quad \Rightarrow \quad w(260-12w)= 0 \quad \Rightarrow \quad w=0,\frac{260}{12}\approx 21.67.$

We found two critical values: when $$w=0$$ and when $$w=21.67$$. We again ignore the $$w=0$$ solution; the maximum volume, subject to the constraint, comes at $$w=h=21.67$$, $$\ell = 130-4(21.6) =43.33.$$ This gives a volume of $$V(21.67,43.33) \approx 19,408$$in$$^3$$.

Figure 12.33: Graphing the volume of a box with girth 4w and length $$l$$, subject to a size constraint.

The volume function $$V(w,\ell)$$ is shown in Figure 12.33 along with the constraint $$\ell = 130-4w$$. As done previously, the constraint is drawn dashed in the $$x$$-$$y$$ plane and also along the surface of the function. The point where the volume is maximized is indicated.

It is hard to overemphasize the importance of optimization. In "the real world,'' we routinely seek to make something better. By expressing the something as a mathematical function, "making something better'' means "optimize some function.''

The techniques shown here are only the beginning of an incredibly important field. Many functions that we seek to optimize are incredibly complex, making the step of "find the gradient and set it equal to $$\vec 0$$'' highly nontrivial. Mastery of the principles here are key to being able to tackle these more complicated problems.