Constrained optimization

$\newenvironment {prompt}{}{} \newcommand {\accordion }[0]{} \newcommand {\ungraded }[0]{} \newcommand {\xmDefaultPreamble }[0]{xmPreamble.tex} \newcommand {\xmDefaultPrintstyle }[0]{xmPrintstyle.sty} \newcommand {\todo }[0]{} \newcommand {\oiint }[0]{{\large \bigcirc }\kern -1.56em\iint } \newcommand {\mooculus }[0]{\textsf {\textbf {MOOC}\textnormal {\textsf {ULUS}}}} \newcommand {\tkzTabSlope }[1]{\foreach \x /\y /\z in {#1}{\node [left = 3pt] at (Z\x 1) {\scriptsize $\y $}; \node [right = 3pt] at (Z\x 1) {\scriptsize $\z $}; }} \newcommand {\RR }[0]{\mathbb R} \newcommand {\R }[0]{\mathbb R} \newcommand {\N }[0]{\mathbb N} \newcommand {\Z }[0]{\mathbb Z} \newcommand {\sagemath }[0]{\textsf {SageMath}} \newcommand {\d }[0]{\,d} \newcommand {\l }[0]{\ell } \newcommand {\ddx }[0]{\frac {d}{\d x}} \newcommand {\zeroOverZero }[0]{\ensuremath {\boldsymbol {\tfrac {0}{0}}}} \newcommand {\inftyOverInfty }[0]{\ensuremath {\boldsymbol {\tfrac {\infty }{\infty }}}} \newcommand {\zeroOverInfty }[0]{\ensuremath {\boldsymbol {\tfrac {0}{\infty }}}} \newcommand {\zeroTimesInfty }[0]{\ensuremath {\small \boldsymbol {0\cdot \infty }}} \newcommand {\inftyMinusInfty }[0]{\ensuremath {\small \boldsymbol {\infty - \infty }}} \newcommand {\oneToInfty }[0]{\ensuremath {\boldsymbol {1^\infty }}} \newcommand {\zeroToZero }[0]{\ensuremath {\boldsymbol {0^0}}} \newcommand {\inftyToZero }[0]{\ensuremath {\boldsymbol {\infty ^0}}} \newcommand {\numOverZero }[0]{\ensuremath {\boldsymbol {\tfrac {\#}{0}}}} \newcommand {\dfn }[0]{\textbf } \newcommand {\unit }[0]{\mathop {}\!\mathrm } \newcommand {\eval }[1]{\bigg [ #1 \bigg ]} \newcommand {\seq }[1]{\left ( #1 \right )} \newcommand {\epsilon }[0]{\varepsilon } \newcommand {\phi }[0]{\varphi } \newcommand {\iff }[0]{\Leftrightarrow } \DeclareMathOperator {\arccot }{arccot} \DeclareMathOperator {\arcsec }{arcsec} \DeclareMathOperator {\arccsc }{arccsc} \DeclareMathOperator {\si }{Si} \DeclareMathOperator {\scal }{scal} \DeclareMathOperator {\sign }{sign} \newcommand {\arrowvec }[1]{{\overset {\rightharpoonup }{#1}}} \newcommand {\vec }[1]{{\overset {\boldsymbol {\rightharpoonup }}{\mathbf {#1}}}\hspace {0in}} \newcommand {\point }[1]{\left (#1\right )} \newcommand {\pt }[1]{\mathbf {#1}} \newcommand {\Lim }[2]{\lim _{\point {#1} \to \point {#2}}} \DeclareMathOperator {\proj }{\mathbf {proj}} \newcommand {\veci }[0]{{\boldsymbol {\hat {\imath }}}} \newcommand {\vecj }[0]{{\boldsymbol {\hat {\jmath }}}} \newcommand {\veck }[0]{{\boldsymbol {\hat {k}}}} \newcommand {\vecl }[0]{\vec {\boldsymbol {\l }}} \newcommand {\uvec }[1]{\mathbf {\hat {#1}}} \newcommand {\utan }[0]{\mathbf {\hat {t}}} \newcommand {\unormal }[0]{\mathbf {\hat {n}}} \newcommand {\ubinormal }[0]{\mathbf {\hat {b}}} \newcommand {\dotp }[0]{\bullet } \newcommand {\cross }[0]{\boldsymbol \times } \newcommand {\grad }[0]{\boldsymbol \nabla } \newcommand {\divergence }[0]{\grad \dotp } \newcommand {\curl }[0]{\grad \cross } \newcommand {\lto }[0]{\mathop {\longrightarrow \,}\limits } \newcommand {\bar }[0]{\overline } \newcommand {\surfaceColor }[0]{violet} \newcommand {\surfaceColorTwo }[0]{redyellow} \newcommand {\sliceColor }[0]{greenyellow} \newcommand {\vector }[1]{\left \langle #1\right \rangle } \newcommand {\sectionOutcomes }[0]{} \newcommand {\luastring }[1]{"\luatexluaescapestring {#1}"} \newcommand {\luastringO }[1]{\luastring {\unexpanded \expandafter {#1}}} \newcommand {\luastringN }[1]{\luastring {\unexpanded {#1}}} \newcommand {\RestoreMathJaxEnvironment }[1]{\expandafter \let \csname #1\expandafter \endcsname \csname mathjax-#1\endcsname \expandafter \let \csname end#1\expandafter \endcsname \csname mathjax-end#1\endcsname } \newcommand {\DeclareMicrotypeVariants }[1]{} \newcommand {\DeclareMicrotypeAlias }[2]{} \newcommand {\LoadMicrotypeFile }[1]{} \newcommand {\DeclareMicrotypeFilePrefix }[1]{} \newcommand {\DeclareMicrotypeBabelHook }[2]{} \newcommand {\microtypesetup }[1]{} \newcommand {\microtypecontext }[1]{} \newcommand {\textmicrotypecontext }[2]{#2} \newcommand {\leftprotrusion }[1]{#1} \newcommand {\rightprotrusion }[1]{#1} \newcommand {\noprotrusionifhmode }[0]{} \newcommand {\lsstyle }[0]{} \newcommand {\lslig }[1]{#1} \newcommand {\maketitle }[0]{} \newcommand {\problem }[0]{ } \newcommand {\exercise }[0]{ } \newcommand {\question }[0]{ } \newcommand {\exploration }[0]{ } \newcommand {\hint }[0]{ } \newcommand {\ConfigureTheoremEnv }[1]{\renewenvironment {#1}[1][]{\refstepcounter {problem}\ifthenelse {\equal {###1}{}}{}{\HCode {<span class="theorem-like-title">}###1\HCode {</span>}}}{} \ConfigureEnv {#1}{\stepcounter {identification}\ifvmode \IgnorePar \fi \EndP \HCode {<div class="theorem-like problem-environment #1" id="problem\arabic {identification}" titletext=" \GetTranslation {#1}">}}{\ifvmode \IgnorePar \fi \EndP \HCode {</div>}\IgnoreIndent }{}{}} \newcommand {\dialogue }[0]{\begin {description}} \newcommand {\foldable }[0]{\stepcounter {identification}\ifvmode \IgnorePar \fi \EndP \HCode {<div id="foldable\arabic {identification}" class="foldable">}} \newcommand {\expandable }[0]{\stepcounter {identification}\ifvmode \IgnorePar \fi \EndP \HCode {<div data-original="expandable" id="foldable\arabic {identification}" class="foldable">}} \newcommand {\unfoldable }[1]{\HCode {<span class="unfoldable">}#1\HCode {</span>}} \newcommand {\selectAll }[0]{\refstepcounter {problem}} \newcommand {\freeResponse }[0]{\refstepcounter {problem}} \newcommand {\javascript }[0]{\NoFonts } \newcommand {\sageCell }[0]{\NoFonts } \newcommand {\sageOutput }[0]{\NoFonts } \newcommand {\sagesilent }[0]{\NoFonts } \newcommand {\ungraded }[0]{\ifvmode \IgnorePar \fi \EndP \HCode {<div class="ungraded">}\IgnoreIndent } \newcommand {\accordion }[0]{\ifvmode \IgnorePar \fi \EndP \HCode {<div class="accordion">} } \newcommand {\paragraph }[1]{\HCode {<span class="paragraphHead">}#1\HCode {</span>}\par \IgnorePar } \newcommand {\subparagraph }[1]{\HCode {<span class="subparagraphHead">}#1\HCode {</span>}\par \IgnorePar } \newcommand {\outcome }[1]{\HCode {<span class="learning-outcome">#1</span>} } \newcommand {\javascriptCode }[0]{\NoFonts } \newcommand {\GetTranslation }[1]{#1} \newcommand {\d }[0]{\,d} \newcommand {\ref }[1]{\HCode {<a class="reference" href="\##1">#1</a>}}$

We learn to optimize surfaces along and within given paths.

When optimizing functions of one variable $f:\R \to \R $, we have the Extreme Value Theorem:

Extreme Value Theorem If $f$ is a continuous function for all $x$ in the closed interval $[a,b]$, then there are points $c$ and $d$ in $[a,b]$, such that $(c,f(c))$ is a global maximum and $(d,f(d))$ is a global minimum on $[a, b]$.

Below, we see a geometric interpretation of this theorem.

A similar theorem applies to functions of several variables.

Extreme Value Theorem Let $F:\R ^n\to \R $ be a continuous function on a closed, bounded set $S$. Then $F$ has a maximum and minimum value on $S$.

When finding extrema of functions in your first calculus course, you had to check inside an interval and at the end-points. Now we need to check the interior of a region and the boundary curve. If we check those critical points, then the Extreme Value Theorem tells us that we have found the extrema! No other tests are necessary.

To check the interior of a region, one finds where the gradient vector is zero or undefined—we did that in the last section. Hence in this section, we will focus on how one finds extrema on the boundary. In this case, the Extreme Value Theorem still applies, and so we will be sure that we found the extrema on the boundary. Let’s see some examples, we start with a classic real-world problem.

The U.S. Postal Service states that the girth plus the length of Standard Post Package must not exceed $108\unit {in}$. Given a rectangular box, the “length” is the longest side, and the “girth” is the perimeter of the base.

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?

Let $w$, $h$ and $\l $ denote the width, height and length of a rectangular box. We assume here that $w=h$, so the girth is $4w$. Hence the volume of the box is

\[ V(w,\l ) = w^2\cdot \l \]

We wish to maximize this volume subject to the constraint $4w+\l \leq 108$. Note, common sense tells us that the volume will be maximized when

\[ 4w + \l = \answer [given]{108} \]

and that both $w$ and $\l $ are nonnegative. We may now rewrite our constraint as:

\[ \l = \answer [given]{108 - 4w} \]

and this is applicable on the $w$-interval $\left [\answer [given]{0},\answer [given]{27}\right ]$.

We now consider the volume along the constraint $\l =108-4w$. Along this line, we have:

\begin{align*} V(w,\l ) &= V(w,108-4w)\\ &= \answer [given]{108w^2-4w^3} \end{align*}

Set $v(w) = \answer [given]{108w^2-4w^3}$ and find the critical points. Write with me:

\[ v'(w) = \answer [given]{216w-12w^2} \]

$v'(w)= 0$ when $w = 0$ and $w= \answer [given]{18}$.

We found two critical values: when $w=0$ and when $w=18$. We ignore the $w=0$ solution. Thus the maximum volume, subject to the constraint, comes at $w=h=18$, $\l = 108-4(18) =36$. This gives a volume of $V(18,36) = \answer [given]{11664}\unit {in}^3$.

The volume function $V(w,\l )$ is shown above along with the constraint $\l = 108-4w$. As done previously, the constraint is drawn dashed in the $(w,\l )$-plane and also along the surface of the function. The Extreme Value Theorem guarantees that we found the extrema. The point where the volume is maximized is indicated.

This portion of the text is entitled “Constrained optimization” because we want to find extrema of a function subject to a constraint, meaning there are limitations to what values the function can attain. In our first example the constraint was set by the U.S. Post office. Constrained optimization problems are an important topic in applied mathematics. The techniques developed here are the basis for solving larger problems, where the constraints are either more complex or more than two variables are involved.

Let $F(x,y) = x^2-y^2+5$ and let $T$ be the triangle with vertices $(-1,-2)$, $(0,1)$, and $(2,-2)$.

Find the maximum and minimum values of $F$ on $T$.

Let’s see a graph of $F$ along with the set $T$:

The triangle defining $T$ in the $(x,y)$-plane is drawn with a dashed line. Above it is the surface described by $F$.

Since we are working within a closed and bounded set $T$, we now find the maximum and minimum values that $F$ attains along $T$. This means we find the extrema of $F$ along the edges of the triangle.

Start with the bottom edge of the triangle, along the line $y=\answer [given]{-2}$ while $x$ runs from $\left [\answer [given]{-1},\answer [given]{2}\right ]$:

\[ F\left (x,\answer [given]{-2}\right ) = \answer [given]{x^2+1} \]

Now set

\[ f_{\mathrm {bottom}}(x) = x^2+1, \]

as this represents the bottom edge of the triangular boundary. We want to maximize/minimize $f_{\mathrm {bottom}}$ on the interval $[-1,2]$. To do so, we evaluate $f_1(x)$ at its critical points and at the endpoints. First find the critical points of $f_{\mathrm {bottom}}$:

\[ f_{\mathrm {bottom}}'(x)= \answer [given]{2x} \]

We see that $x= \answer [given]{0}$ is the only critical point of $f_{\mathrm {bottom}}$. Evaluating $f_{\mathrm {bottom}}$ at its critical point and at the endpoints of $\left [\answer [given]{-1},\answer [given]{2}\right ]$ gives:

\[ \begin{array}{lcl} f_{\mathrm {bottom}}(-1) = \answer [given]{2} &\Rightarrow & F(-1,-2) = \answer [given]{2}\\ f_{\mathrm {bottom}}(0) = \answer [given]{1} &\Rightarrow & F(0,-2) = \answer [given]{1}\\ f_{\mathrm {bottom}}(2) = \answer [given]{5} &\Rightarrow & F(2,-2) = \answer [given]{5}. \end{array} \]

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)$:

\begin{align*} f_{\mathrm {left}} &= F(x,3x+1)\\ &= -8x^2-6x+4 \end{align*}

We want the maximum and minimum values of $f_{\mathrm {left}}$ on the interval $\left [\answer [given]{-1},\answer [given]{0}\right ]$, so we evaluate $f_{\mathrm {left}}$ at its critical points and the endpoints of the interval. First find the critical points of $f_{\mathrm {left}}$:

\[ f'_{\mathrm {left}}(x) = \answer [given]{-16x-6} \]

We see that $x = \answer [given]{-3/8}$ is the only critical point of $f_{\mathrm {left}}$. Evaluating $f_{\mathrm {left}}$ at its critical point and the endpoints of $[-1,0]$ gives:

\[ \begin{array}{lcl} f_{\mathrm {left}}(-1) = \answer [given]{2} &\Rightarrow& F(-1,-2) = \answer [given]{2}\\ f_{\mathrm {left}}(-3/8) = \answer [given]{41/8} &\Rightarrow & F(-3/8,-1/8) = \answer [given]{41/8} \\ f_{\mathrm {left}}(0) = \answer [given]{4} &\Rightarrow & F(0,1) = \answer [given]{4}. \end{array} \]

Finally, we evaluate $F$ along the right edge of the triangle, where $y = (-3/2)x+1$:

\begin{align*} f_{\mathrm {right}} &= F(x,(-3/2)x+1)\\ &= \answer [given]{\frac {-5x^2}{4}+3x+4} \end{align*}

We want the maximum and minimum values of $f_{\mathrm {right}}$ on the interval $\left [\answer [given]{0},\answer [given]{2}\right ]$, so we evaluate $f_{\mathrm {right}}$ at its critical points and the endpoints of the interval. First find the critical points of $f_{\mathrm {right}}$:

\[ f'_{\mathrm {right}}(x) = \answer [given]{\frac {-5x}{2}+3} \]

We see that $x = \answer [given]{6/5}$ is the only critical point. Evaluating $f_{\mathrm {right}}$ at this critical point and at the endpoints of the interval $[0,2]$:

\[ \begin{array}{lcl} f_{\mathrm {right}}(0) = \answer [given]{4} &\Rightarrow & F(0,1) = \answer [given]{4}\\ f_{\mathrm {right}}(1.2) = \answer [given]{5.8} &\Rightarrow & F(1.2,-0.8) = \answer [given]{5.8}\\ f_{\mathrm {right}}(2) = \answer [given]{5} &\Rightarrow& F(2,-2) = 5. \end{array} \]

Check out the following graph:

Above we see the surface described by $F$ along with important points along $T$. We have evaluated $F$ at a total of $6$ different places, all shown above. 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 $\answer [given]{5.8}$, found at $\left (\answer [given]{1.2},\answer [given]{-0.8}\right )$; the minimum is $\answer [given]{1}$, found at $\left (\answer [given]{0},\answer [given]{-2}\right )$.

When working constrained optimization problems, there is often more than one way to proceed. Let’s do the previous problem again, but this time we will use vector-valued functions and the chain rule.

Let $F(x,y) = x^2-y^2+5$ and let $T$ be the triangle with vertices $(-1,-2)$, $(0,1)$, and $(2,-2)$.

Find the maximum and minimum values of $F$ on $T$.

Since we are working within a closed and bounded set $T$, the Extreme Value Theorem tells us that the extrema will occur. We now find the maximum and minimum values that $F$ attains along $T$. This means we find the extrema of $F$ along the edges of the triangle. This time we’ll use the chain rule. Starting along the bottom edge, write with me:

\begin{align*} \dd {t} F(\vecl _{\mathrm {B}}(t)) &= \vector {\answer [given]{2(-1+3t)},\answer [given]{4}}\dotp \vector {\answer [given]{3},\answer [given]{0}}\\ &=\answer [given]{-6+18t} \end{align*}

We see that $t= \answer [given]{1/3}$ is the only critical point of $F(\vecl _{\mathrm {B}}(t))$. Evaluating this at its critical point and at the endpoints of $\left [\answer [given]{0},\answer [given]{1}\right ]$ gives:

\begin{align*} F(\vecl _{\mathrm {B}}(0)) &= \answer [given]{2}\\ F(\vecl _{\mathrm {B}}(1/3)) &= \answer [given]{1}\\ F(\vecl _{\mathrm {B}}(1)) &= \answer [given]{5}. \end{align*}

We need to do this process twice more, for the other two edges of the triangle. For the left edge, write with me:

\begin{align*} \dd {t} F(\vecl _{\mathrm {L}}(t)) &= \vector {\answer [given]{2(-t)},\answer [given]{-2(1-3t)}}\dotp \vector {\answer [given]{-1},\answer [given]{-3}}\\ &=\answer [given]{6-16t} \end{align*}

We see that $t= \answer [given]{3/8}$ is the only critical point of $F(\vecl _{\mathrm {B}}(t))$. Evaluating this at its critical point and at the endpoints of $\left [\answer [given]{0},\answer [given]{1}\right ]$ gives:

\begin{align*} F(\vecl _{\mathrm {L}}(0)) &= \answer [given]{4}\\ F(\vecl _{\mathrm {L}}(3/8)) &= \answer [given]{5.125}\\ F(\vecl _{\mathrm {L}}(1)) &= \answer [given]{2}. \end{align*}

Now for the right edge, write with me:

\begin{align*} \dd {t} F(\vecl _{\mathrm {R}}(t)) &= \vector {\answer [given]{2(2t)},\answer [given]{-2(1-3t)}}\dotp \vector {\answer [given]{2},\answer [given]{-3}}\\ &=\answer [given]{6-10t} \end{align*}

We see that $t= \answer [given]{3/5}$ is the only critical point of $F(\vecl _{\mathrm {B}}(t))$. Evaluating this at its critical point and at the endpoints of $\left [\answer [given]{0},\answer [given]{1}\right ]$ gives:

\begin{align*} F(\vecl _{\mathrm {R}}(0)) &= \answer [given]{4}\\ F(\vecl _{\mathrm {R}}(3/5)) &= \answer [given]{5.8}\\ F(\vecl _{\mathrm {R}}(1)) &= \answer [given]{5}. \end{align*}

Again, check out the following graph:

So far, our constraints have all been lines. This doesn’t have to be the case.

Let $F(x,y) = 4x^3+4y^2-4x$ and let $C$ the set

\[ C = \{(x,y):x^2 + y^2 =1\} \]

Find the maximum and minimum values of $F$ on $C$.

One way to do this is to find a vector-valued function that draws $C$. Since $C$ is a circle, we know $C$ is draw by:

\[ \vec {c}(t) = \vector {\cos (t),\sin (t)} \]

for $0\le t<2\pi $. Now compute $\dd {t} F(\vec {c}(t))$. The chain rule says:

\[ \dd {t} F(\vec {c}(t)) = \grad F(\vec {c}(t))\dotp \vec {c}'(t) \]

So let’s compute:

\[ \grad F(x,y) =\vector {\answer [given]{12x^2-4},\answer [given]{8y}} \]

and

\[ \vec {c}'(t) = \vector {\answer [given]{-\sin (t)},\answer [given]{\cos (t)}} \]

Putting this together, we see

\begin{align*} \dd {t} F(\vec {c}(t)) &= \vector {\answer [given]{12\cos ^2(t)-4},\answer [given]{8\sin (t)}}\dotp \vector {\answer [given]{-\sin (t)},\answer [given]{\cos (t)}}\\ &=\answer [given]{4\sin (t)+8\cos (t)\sin (t) -12\cos ^2(t)\sin (t)} \end{align*}

Now we set $\dd [F]{t} = 0$. Here you may be tempted to solve for $t$, but this author suggestions that you instead solve for $\cos (t)$ and $\sin (t)$. Note that if

\[ 4\sin (t)+8\cos (t)\sin (t) -12\cos ^2(t)\sin (t) =0 \]

one solution is $\sin (t) = 0$. This corresponds to the points

\[ \left (1,0\right ) \quad \text {and}\quad \left (-1,0\right ) \]

Now assume that $\sin (t) \ne 0$ and divide the equation above by $4\sin (t)$. We now have

\[ 1+2\cos (t) -3\cos ^2(t) =0 \]

Using the quadratic formula we find

\[ \cos (t) = \frac {-1\pm 2}{-3} \]

This corresponded to points

\[ \left (\frac {-1}{3},\frac {-\sqrt {8}}{3}\right ) \quad \text {and}\quad \left (\frac {-1}{3},\frac {\sqrt {8}}{3}\right ) \]

Plugging these points back into $F$, we find that the minimum value of $F$ on $C$ is $\answer [given]{0}$ and the maximum value is $\answer [given]{128/27}$.

It is hard to overemphasize the importance of optimization. As humans, we routinely seek to make something better. By expressing the something as a mathematical function, “making something better” means “optimize some function.”