Constrained optimization

$\newenvironment {prompt}{}{} \newcommand {\todo }[0]{} \newcommand {\oiint }[0]{{\large \bigcirc }\kern -1.56em\iint } \newcommand {\mooculus }[0]{\textsf {\textbf {MOOC}\textnormal {\textsf {ULUS}}}} \newcommand {\npnoround }[0]{\nprounddigits {-1}} \newcommand {\npnoroundexp }[0]{\nproundexpdigits {-1}} \newcommand {\npunitcommand }[1]{\ensuremath {\mathrm {#1}}} \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]{\mathop {}\!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}}}} \DeclareMathOperator {\proj }{\vec {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 {\HyperFirstAtBeginDocument }[0]{\AtBeginDocument } \newcommand {\epstopdfsetup }[0]{\setkeys {ETE}} changed the theorem header of amsthm failed\MessageBreak }}} \newcommand {\GetTitleStringSetup }[0]{\setkeys {gettitlestring}} \newcommand {\Sectionformat }[2]{#1}$

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$ .

We can find these values by evaluating the function at the critical values in the set and over the boundary of the set. Let’s see some examples.

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$ .

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

The triangle defining $S$ in the $(x,y)$ -plane is drawn with a dashed line. Above it is the surface described by $F$ . We are interested in the portion of $F$ enclosed by the “triangle” on the surface. Start by computing: $\grad F (x,y) =\vector {\answer [given]{2x}, \answer [given]{-2y}}$ It is not hard to see that there is only one critical point: $\vector {\answer [given]{0},\answer [given]{0}}$ We can compute $F(0,0) = \answer [given]{5}$ .

Since we are working within a closed and bounded set $S$ , we now find the maximum and minimum values that $F$ attains along the boundary of $S$ . 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 $[\answer [given]{-1},\answer [given]{2}]$ : $F(x,\answer [given]{-2}) = \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 $[\answer [given]{-1},\answer [given]{2}]$ 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 $[\answer [given]{-1},\answer [given]{0}]$ , 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 $[\answer [given]{0},\answer [given]{2}]$ , 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 the boundary of $S$ and the interior. We have evaluated $F$ at a total of $7$ 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 $(\answer [given]{0},\answer [given]{-2})$ .

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 the previous example, we restricted ourselves to considering a function only within the boundary of a triangle; here the boundary of the triangle was the “constraint.”

Constrained optimization problems are an 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.

The U.S. Postal Service states that the girth plus the length of Standard Post Package must not exceed $130\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$ . The girth is then $2(w+h) = 4w$ . The volume of the box is $V(w,l) = w\cdot h\cdot l$ since $w=h$ , we may express volume entirely in terms of $w$ and $l$ , we may write $V(w,l)= \answer [given]{w^2\cdot l}.$ We wish to maximize this volume subject to the constraint $4w+l\leq 130$ , or $l\leq 130-4w$ . Note, common sense also indicates that $l>0, w>0$ . We begin by finding the critical points of $V$ . Write with me $\grad V(w,l) = \vector {\answer [given]{2wl},\answer [given]{w^2}}$ The gradient vector is $\vec {0}$ when $w=\answer [given]{0}$ and $l=\answer [given]{0}$ . Since this corresponds to a volume of $\answer [given]{0}$ , this critical point cannot be a maximum, and so we ignore this critical point.

We now consider the volume along the constraint $l=130-4w.$ Along this line, we have: $V(w,l) = \answer [given]{130w^2-4w^3}$ Set $v(w) = \answer [given]{130w^2-4w^3}$ and find the critical points. Write with me: $v'(w) = \answer [given]{260w-12w^2}$ $v'(w)= 0$ when $w = \answer [given]{0}$ and $w= \frac {260}{12}$ . The constraint is applicable on the $w$ -interval $[\answer [given]{0},\answer [given]{32.5}]$ .

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

The volume function $V(w,l)$ is shown above along with the constraint $l = 130-4w$ . As done previously, the constraint is drawn dashed in the $(l,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.