## Posts Tagged ‘optimization’

### Visualizing Elementary Calculus: Optimization

April 26, 2011

Geometric thinking sometimes lets us skip a bunch of algebraic steps in basic min/max problems. Here are some common problems solved geometrically. I learned to think about optimization this way from The Feynman Lectures.

This series:

### Parabola

Where is the vertex of the parabola $y = ax^2 + bx + c$ ?

A parabola looks like this, with the vertex at the lowest part (or highest if it opens down) If you’re at the bottom like that, the tangent line must be flat. Otherwise, you could take a small step in whichever direction on the tangent line went down, and you’d get to something smaller, and hence you weren’t at the bottom to begin with.

So to find the vertex, we simply need to look for where the tangent is horizontal. In the previous post, we saw that the slope of the tangent is the derivative, so we need to set the derivative to zero. $y = ax^2 + bx + c$ $\frac{\textrm{d}y}{\textrm{d}x} = 2ax + b = 0$ $x = \frac{-b}{2a}$,

a fact you may remember from algebra.

### Fence

Suppose we want to put up some fence to make a rectangular pen. We only have 90m of fence to use, and we want the biggest possible pen.

It’s easy guess by symmetry that the optimal shape is a square, but what if we twist the problem slightly? Say the fence is going up against the side of a cliff, and so we get one side of it for free. Now what is the best rectangular pen?

The fence has a length and a width like this: To maximize or minimize $A$ respect to $B$, $\textrm{d}A/\textrm{d}B$ must be zero. So we want the derivative of area with respect to side length to be zero. We draw a picture to show the product rule  $\textrm{d}A = l\textrm{d}w + w \textrm{d}l = 0$

If we take away 1 meter from the vertical length of the fence, it has to be split in two to go on the horizontal widths, so they only add half a meter. $\textrm{d}w = -\frac{1}{2} \textrm{d}l$, so $\textrm{d}A = \frac{-1}{2} l \textrm{d} l + w \textrm{d} l = 0$ $l = 2w$

so the vertical length of the fence should be twice the horizontal width.

### Distance to a line

Here is a easy problem: Given a line and a point, what is the shortest path from the point to the line? There are many ways to go from the point to the line. Here are a few: If the point of contact with the line is called $x$ and the distance from our original point to the line is called $l$, we can form the derivative $\textrm{d}l/\textrm{d}x$. This derivative tells us how the distance to the line changes as we move the point around.

If we find $x$ that minimizes $l$, the $\textrm{d}l/\textrm{d}x$ is zero there. We can make a little picture to illustrate $\textrm{d}l$ and $\textrm{d}x$. $\textrm{d}x$ is a little distance along the line.  $\textrm{d}l$ is the change in the length of the segment. To find it, draw a circle with the center at the point off the line going through one of the candidate points on the line. The circle shows everywhere that’s equidistant, so the length of the other segment outside the circle is how much longer it is. In order for the extra bit to shrink to zero, indicating the derivative is zero, we must have the circle be tangent to the line. Tangents to circle are perpendicular to radii, so the shortest possible path from a point to a line is perpendicular to the line. This is a result you could probably get without calculus, but it’s a good warm up for the next bit.

### Fermat’s Principle

Fermat’s principle for optics says that light takes the whatever path from A to B is fastest. We can find such paths by calculus, keeping in mind “the fastest path” means the derivative of the time of travel is zero.

Take two arbitrary points on the same side of a flat mirror. What is the fastest route from A to B? The answer is a straight line, ignoring the mirror. But what is the fastest route that also touches the mirror somewhere? There are many potential places to touch the mirror, and therefore many potential paths. The fastest one has the derivative of path length with respect to contact point equal to zero, so take two nearby points and compare. In this picture, segment $AC$ is clearly shorter than segment $AD$. How much shorter? Draw a circle with $AC$ as a radius. The purple segment shows the discrepancy. We would like to find its length. Zoom in on the interesting area. Since this is calculus, we are letting the points $C$ and $D$ get be separated by a very small distance $\textrm{d}x$. When we zoom in, the circle appears indistinguishable from its tangent line, which is a line perpendicular to $AC$. Also, as $C$ and $D$ get closer together, $AC$ become parallel to $AD$, so the circle is also perpendicular to $AD$. The purple segment’s length is just $\sin\theta \textrm{d}x$.

Next we want to do basically the same thing to figure out how much longer $CB$ is than $DB$. Again, we zoom in on the interesting area, making the same linear approximations as the separation $\textrm{d}x$ becomes very small. This time, we get that the extra length is $\textrm{d}x\sin\phi$.

These two extra lengths must cancel each other out if the paths are going to be the same length, so $\textrm{d}x\sin\theta = \textrm{d}x\sin\phi$

so $\theta = \phi$. $\theta$ is the angle that the incoming rays make with the vertical, and $\phi$ is the angle that the outgoing rays make with the vertical (exercise). So Fermat’s principle says that light bounces off a mirror at the same angle it came in.

A similar problem is the “lifeguard problem”. You’re a lifeguard. You see a drowning person, and you want to go save them, but you have to decide what path is fastest. You run part way on sand and swim part way in the water. What path should you choose?

You go faster on the beach, so you probably shouldn’t take a straight line. Instead, run further on the beach and turn a bit when you enter the water. We want to know how much you should turn. Again, take two nearby points and find the condition so that the difference in path lengths sums to zero. Let’s bring those green circles and purple segments back again.

They’re different lengths, which is actually what we want. We want those two purple segments to take the same amount of time to traverse, not to be the same length. That way, the two nearby paths take equal total time and the derivative of the time with respect to the entry point is zero.

From here, you can follow the details through to find $v_{water} \sin\theta = v_{land} \sin \phi$, which is called Snell’s Law.

Fermat’s principle does not really state that light takes a path of least time – in fact having the derivative be zero is enough. In most cases the time is least, in some applications, images actually form where the time is at a maximum compared to nearby paths, or even where it is a “stationary point” – the derivative is zero but not a minimum or maximum, which happens, for example, at the origin of the graph of $y = x^3$. ### Witches with unusually-shaped heads

This example is somewhat artificial, but what is the largest cylinder (an unusual head shape) that fits inside a given right circular cone (witch’s hat)?

The correct cylinder is clearly something along these lines: We want to optimize $V$ by changing $h$, so we had better set $\textrm{d}V/\textrm{d}h = 0$.

As the cylinder gets a little taller, it sweeps out some volume with its top, and sucks in some volume with its sides, so $\textrm{d}V = A_{top}\textrm{d}h - A_{sides} \textrm{d}r$ $\textrm{d}h$ and $\textrm{d}r$ are related by the slope of the cone, which is $R/H$, so we have $\textrm{d}V = \pi r^2\textrm{d}h - 2\pi r h \textrm{d}h * \frac{R}{H} = 0$

which is equivalent to $\frac{r}{h} = 2\frac{R}{H}$

This happens when $h = \frac{H}{3}$ $r = \frac{2R}{3}$

These toy optimization problems are given to calculus students for practice. This is a useful skill, but many real optimization problems are more difficult because they involve many variables (even infinitely many). These problems are extremely important to physics, though. In the next posts, we’ll see some physics examples.

### Exercises

1. Write down the quadratic formula and stare at it until you understand how it shows you what the vertex of a parabola is.
2. What is the smallest and largest value of the function $f(x) = \sin(x)/x$? (you can check your answer like this.)
3. Where are the “humps” in the graph of the cubic equation $y = ax^3 + bx^2 + cx + d$? Under what conditions does it have humps? How can you use this to tell whether a cubic has one real zero or three?
4. Use the Pythagorean theorem and some algebra to solve the problem of finding the shortest segment from a point to a line.
5. Prove the result about bouncing off the flat mirror using the concept of an image point. Create a new point, called $B'$ on the other side of the mirror opposite $B$. For every path from $A$ to the mirror to $B$, there is an equally-long path from $A$ to the same point on the mirror to $B'$. Now use the fact that the fastest route from $A$ to $B'$ is a straight line to find the fastest route from $A$ to $B$ touching the mirror.
6. Imagine that instead of a single pen, we want to make a whole grid of pens (or cubicles) enclosed on all sides. Our grid is $m$ pens wide and $n$ pens tall. If we have a fixed amount of fencing, what should the aspect ratio of the pens be to maximize their area? (Answer: $m+1 : n+1$
7. Find the optimal height for a cylinder with fixed surface area and maximal volume. Compare this to a cylinder with only one end cap, and then one with no end caps. (Answer: r = 3/2 h, r = 3h, and unbounded)
8. Here’s a modified version of the lifeguard problem. The pool has become an ellipse. What path should the lifeguard take? Try to find a condition such that there are three equal, optimal paths.