Applied Optimization

How do you solve an applied optimization problem?

An optimization problem asks for the best value of something: the rectangle of fixed perimeter with the most area, the cheapest can for a given volume, the production run with the largest profit. The best value is a largest or smallest value of a function, and the closed interval method already tells us how to find it. What is new is that the function is not given: you have to build it from a description in words.

The four steps. 1. Read the problem until you know what is given and which unknown is to be maximized or minimized. 2. Introduce variables. Name every relevant quantity, list every relation between them as an equation, and draw a picture whenever you can. 3. Write the function. Use the relations to express the unknown as a function of a single variable, and say for which values of that variable the situation makes sense. This is the longest step. 4. Test the critical points and the endpoints of that domain, with whatever you know about the shape of the graph, and use f' and f'' to classify the critical points.

Example. You have 800 m of wire to fence a rectangular field that lies along a river, so only three sides need a fence. What is the largest area? The unknown is the area A. Call the two sides that meet the river x and the side parallel to it y; the wire gives 2x+y=800, so y=800-2x and A(x)=x(800-2x), 0\le x\le400, because neither side can be negative. Then A'(x)=800-4x is zero at x=200, and the values are A(0)=0, A(200)=80000 and A(400)=0. The largest area is 80000 m², with sides 200 m and y=400 m: the side along the river is twice each of the others, not equal to them.

How do you optimize boxes, cans and inscribed shapes?

Geometry problems are the best place to practice step 3, because a constraint such as a fixed volume or a fixed perimeter must be used to remove a variable.

Example 1: the open box. An open-top box is made from a 12 cm by 12 cm sheet of tin by cutting a square of side x from each corner and folding up the sides. The box has base (12-2x)×(12-2x) and height x, so V(x)=x(12-2x)^2=144x-48x^2+4x^3. The sheet is only 12 cm wide, so 0\le x\le6. Then V'(x)=144-96x+12x^2=12(x-2)(x-6), which is zero at x=2 and x=6; the second is an endpoint, and V(0)=V(6)=0. The only interior critical point gives V(2)=128, so the largest volume is 128 cm³ with squares of side 2 cm (a box 8 by 8 by 2). The widget in the article on extreme values lets you change the sheet.

Example 2: the one-liter can. A closed can shaped like a cylinder must hold 1000 cm³. The metal used is the surface area A=2π r^2+2π rh, and the volume gives π r^2h=1000, so h=(1000)/(π r^2) and A(r)=2π r^2+(2000)/(r), r>0. The domain has no endpoints, so look at the derivative: A'(r)=4π r-(2000)/(r^2)=0 gives r^3=(500)/(π), that is r=(500)/(π)^(1/3)≈5.42 cm. Since A''(r)=4π+(4000)/(r^3)>0 for every r>0, the graph is concave up everywhere and this critical point is the absolute minimum. Then h=(1000)/(π r^2)=2r≈10.84 cm. For any volume the best closed can has h=2r: as tall as it is wide. Real cans differ because of seams, thicker lids, and the shelf they stand on, which are not in the model. With no lid the ends cost half as much and the best can has h=r; if the ends are cut from squares of side 2r and the waste counts, the metal is 8r^2+2π rh and the best ratio is \frac hr=\frac8π≈2.55.

Example 3: the rectangle in a semicircle. A rectangle is inscribed in a semicircle of radius 2, with one side on the diameter. Put the center at the origin and let the upper right corner be \left(x,√(4-x^2)\right). The rectangle has length 2x, height √(4-x^2) and area A(x)=2x√(4-x^2), 0\le x\le2. Then A'(x)=2√(4-x^2)-(2x^2)/(√(4-x^2))=(8-4x^2)/(√(4-x^2)), zero at x=√2 and not defined at the endpoint x=2. With A(0)=A(2)=0 and A(√2)=4, the largest area is 4, for a rectangle 2√2 long and √2 high. For a semicircle of radius R the same steps give x=(R)/(√2) and area R^2: the corner sits at 45^\circ. A useful trick: A is largest where A^2=4x^2(4-x^2) is largest, which has no root to differentiate.

Choose a problem below. The widget shows the same four steps for fifteen textbook problems: what x stands for, the relations, the domain, the graph, the table of critical points and ends with the best one marked, and the answer in the words of the problem.

The can deserves its own look, because its answer does not depend on the volume. Change the volume, the kind of can and the radius below: the best radius changes with V, but the ratio \frac hr does not.

Why does light obey Snell’s law?

Fermat's principle says that light travels from one point to another along the path of least time, and from it the law of refraction follows as a calculus problem. In a uniform medium the quickest path is the shortest, a straight line. When the path crosses from a medium where light has speed c_1 into one where it has speed c_2, it bends, and calculus tells us exactly how much.

Example 4: refraction. Let the boundary between the media be the x-axis, put A=(0,a) in the first medium and B=(d,-b) in the second, and let the ray cross at P=(x,0) for some x in [0,d]. Distance is rate times time, so the time is distance divided by speed on each piece: t(x)=(√(a^2+x^2))/(c_1)+(√(b^2+(d-x)^2))/(c_2), 0\le x\le d. The derivative is t'(x)=(x)/(c_1√(a^2+x^2))-(d-x)/(c_2√(b^2+(d-x)^2))=(\sinθ_1)/(c_1)-(\sinθ_2)/(c_2), where θ_1 and θ_2 are the angles that the two pieces make with the normal to the boundary. This is continuous, it is negative at x=0 and positive at x=d, and it is increasing because t''(x)=(a^2)/(c_1\left(a^2+x^2\right)^3/2)+(b^2)/(c_2\left(b^2+(d-x)^2\right)^3/2)>0. So t' has exactly one zero, the Intermediate Value Theorem finds it, and it is the absolute minimum of t. At that point (\sinθ_1)/(c_1)=(\sinθ_2)/(c_2), which is Snell's law, the law of refraction. The ray bends toward the normal in the slower medium.

A mirror. If the ray bounces off a plane mirror and B is on the same side, the speed is the same on both pieces, c_1=c_2, and t'=0 says \sinθ_1=\sinθ_2: the angle of incidence equals the angle of reflection. The same equation describes a lifeguard who runs on the sand and swims in the water, or Jane rowing and walking in the gallery above.

Change the two media, the positions and the crossing point below. The orange path is yours and the green one is the quickest.

How do cost, profit and inventory problems work?

In economics the best level of production is usually where the marginal revenue equals the marginal cost. Let r(x) be the revenue from selling x items, c(x) the cost of producing them, and p(x)=r(x)-c(x) the profit. Items are whole numbers, but we learn most by treating x as a real number and the functions as differentiable. The derivatives r', c' and p' are the marginal revenue, marginal cost and marginal profit (see marginal analysis). If the profit has a maximum at a critical point, then p'(x)=r'(x)-c'(x)=0,\qquadso r'(x)=c'(x). At a production level that maximizes profit, marginal revenue equals marginal cost.

Example 5: MP3 players. Suppose r(x)=9x and c(x)=x^3-6x^2+15x are the revenue and the cost in millions of dollars, with x in millions of players. Then r'(x)=9 and c'(x)=3x^2-12x+15, and c'(x)=r'(x) gives 3x^2-12x+6=0, that is x^2-4x+2=0 and x=2±√2, about 0.586 and 3.414. The second derivative of the profit is p''(x)=-c''(x)=-(6x-12), which is negative at x=2+√2 and positive at x=2-√2. So a maximum profit occurs at x≈3.414 million players, where p=4+4√2≈9.66 million dollars, and a maximum loss at x≈0.586 million. The company breaks even where r=c, at x=3±√3, so the maximum profit is between the break-even points. If the price falls below 3 the equation has no solution, because the marginal cost is never below 3: every extra player then costs more than it earns, and the best plan is to make none.

Example 6: how often to deliver. A cabinetmaker uses 5 units of cherry wood a day. Each delivery costs 5000 dollars, and storing a unit costs 10 dollars a day. If a delivery comes every x days she must order 5x units, and the average amount in storage is about (5x)/(2) units, held for x days. The cost of one cycle is 5000+(5x)/(2)·10· x, and the average daily cost is that divided by x: c(x)=(5000)/(x)+25x, x>0. Then c'(x)=-(5000)/(x^2)+25=0 gives x^2=200, x=10√2≈14.14 days (the negative root is outside the domain), and c''(x)=(10000)/(x^3)>0 on the whole domain, so this is the absolute minimum: c≈707.11 dollars a day, for an order of about 70 units. Whole days are better for the schedule: 14 days costs 707.14 and 15 days costs 708.33.

The general rule. With a cost K per delivery, d units used a day and a storage cost h per unit per day, c(x)=\frac Kx+(hd)/(2)x has its minimum at x=√((2K)/(hd)), and there the two terms are equal, \frac Kx=(hd)/(2)x: the delivery cost per day equals the storage cost per day. In inventory management the same result is the Wilson lot size formula: for an average weekly cost A(q)=(km)/(q)+cm+(hq)/(2) of ordering, paying for and holding q items, the best order is q=√((2km)/(h)).

Drag the price and the production level in the first widget and the costs in the second.

What if the domain is open, or has no endpoint to test?

When the domain is open, such as r>0, there is no endpoint to compare, so you show that the critical point is the absolute extreme by the shape of the function. Four tools do it, from the strongest to the most common.

1. The sign of f'' on the whole domain. If f''>0 everywhere, the graph is concave up, a critical point is a minimum and it is the absolute minimum. This settled the can and the delivery cycle.
2. The sign of f'. If f'<0 to the left of the only critical point and f'>0 to its right, the function falls and then rises, which is the First Derivative Test, and the point is the absolute minimum.
3. Limits at the open ends. If f grows without bound at both ends, then no end can beat the critical value, so the lowest critical value is the absolute minimum. If f only levels off toward a value, compare the critical value with that limit: a function can approach a value it never reaches, and then the extreme does not exist.
4. One critical point. A continuous function on an interval that has a single critical point cannot turn around anywhere else, so a local minimum there is the absolute minimum on the interval.

Example 7: the poster. A poster needs 312.5 cm² of print, with margins of 10 cm at the top and bottom and 5 cm on each side. If the print is x wide it is (312.5)/(x) high, and the paper is x+10 by (312.5)/(x)+20: P(x)=(x+10)\left((312.5)/(x)+20\right)=20x+(3125)/(x)+512.5, x>0. Then P'(x)=20-(3125)/(x^2)=0 gives x=12.5, and P''(x)=(6250)/(x^3)>0, so it is the absolute minimum: print 12.5 by 25, paper 22.5 by 45 cm, using 1012.5 cm² of paper. As x→0^+ and as x→∞ the area P→∞, so there is no largest poster, and asking for one would have no answer.

Whole numbers. If x counts people or days, the real optimum is only a guide. The best whole number is one of the two on either side of it, and you compare their values, as with 14 and 15 days above. A tour with x people at a fare of 300-2x dollars, fixed cost 6000 and 32 per person, has profit p(x)=268x-2x^2-6000 on 50\le x\le80, with p'(x)=268-4x=0 at x=67, which happens to be a whole number: 67 people, a fare of 166 and a profit of 2978. The widget above includes this problem.

Check the answer. Does it fall inside the domain? Is it a maximum or a minimum, as the problem asks? Are the units consistent? Does it answer the question asked, such as the dimensions or the least amount of material, and not just the value of x?

How do you optimize in code?

In code, SymPy follows the four steps exactly: differentiate, solve f'=0, keep the roots inside the domain, and compare them with the value or limit at each end. Without a CAS, a derivative-free search finds the minimum of a function that falls and then rises (a unimodal function): the golden-section search shrinks the interval around the minimum by the same ratio each time, and bisection on the sign of f' does the same with the derivative. A search that uses only values of f can locate the minimum to about the square root of the machine precision, roughly 10^-8, because f is flat there; the derivative gives a better answer.

import sympy as sp

x = sp.symbols('x', positive=True)


def optimize(f, a, b, want='min'):
    """Best value of f on (a, b): the critical points inside, plus the value or limit at each end."""
    rows = [(s, sp.simplify(f.subs(x, s))) for s in sp.solve(sp.diff(f, x), x) if s.is_real and a < s < b]
    rows += [(end, sp.limit(f, x, end)) for end in (a, b)]
    pick = min if want == 'min' else max
    return pick(rows, key=lambda row: float(row[1])), rows


problems = (
    ('box', x * (12 - 2 * x) ** 2, 0, 6, 'max'),                                    # Example 1
    ('can', 2 * sp.pi * x ** 2 + 2000 / x, 0, sp.oo, 'min'),                         # Example 2
    ('poster', 20 * x + 3125 / x + sp.Rational(1025, 2), 0, sp.oo, 'min'),          # Example 7
    ('beam over a wall', (x + 5) * sp.sqrt(1 + 4 / x ** 2), 0, sp.oo, 'min'),       # a 2 m wall, 5 m from a building
)
for name, f, a, b, want in problems:
    (xb, fb), _ = optimize(f, a, b, want)
    print(name, xb, '->', sp.simplify(fb), '=', round(float(fb), 4))
# box 2 -> 128 = 128.0
# can 5*2**(2/3)/pi**(1/3) -> 300*2**(1/3)*pi**(1/3) = 553.581
# poster 25/2 -> 2025/2 = 1012.5
# beam over a wall 20**(1/3) -> sqrt(5)*(20**(1/3) + 5)**(3/2)/5 = 9.5823

// golden-section search: the smallest value of a function that falls and then rises on [a, b]
const golden = (f, a, b, tol = 1e-9) => {
  const g = (Math.sqrt(5) - 1) / 2
  let c = b - g * (b - a)
  let d = a + g * (b - a)
  while (b - a > tol) {
    if (f(c) < f(d)) b = d
    else a = c
    c = b - g * (b - a)
    d = a + g * (b - a)
  }
  return (a + b) / 2
}
const can = (r) => 2 * Math.PI * r * r + 2000 / r             // the one-liter can of Example 2
const r = golden(can, 0.1, 50)
;[r, 1000 / (Math.PI * r * r), can(r)].map((v) => +v.toFixed(4))     // [5.4193, 10.8385, 553.581]
const beam = (x) => (x + 5) * Math.sqrt(1 + 4 / (x * x))      // the shortest beam over a wall
const xb = golden(beam, 0.1, 50)
;[xb, beam(xb)].map((v) => +v.toFixed(4))                            // [2.7144, 9.5823]
// the same radius from the derivative: bisect on the sign of A'(r) = 4 pi r - 2000 / r^2
let lo = 0.1
let hi = 50
for (let i = 0; i < 60; i++) {
  const mid = (lo + hi) / 2
  if (4 * Math.PI * mid - 2000 / (mid * mid) < 0) lo = mid
  else hi = mid
}
+lo.toFixed(6)                                                       // 5.419261

#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;

double area(double r) {
  return 2 * 3.14159265358979 * r * r + 2000 / r;        // metal for a one-liter can
}

int main() {
  double lo = 0.1;
  double hi = 50;
  for (int i = 0; i < 100; i++) {                        // ternary search: the area falls and then rises
    double m1 = lo + (hi - lo) / 3;
    double m2 = hi - (hi - lo) / 3;
    if (area(m1) < area(m2)) hi = m2;
    else lo = m1;
  }
  double r = (lo + hi) / 2;
  double h = 1000 / (3.14159265358979 * r * r);
  printf("r=%.4f h=%.4f A=%.4f\n", r, h, area(r));
  printf("h/r=%.4f\n", h / r);                         // the best closed can is as tall as it is wide
  return 0;
}

/* output:
r=5.4193 h=10.8385 A=553.5810
h/r=2.0000
*/

Where does optimization come from?

The oldest optimization problems are geometric, and the calculus way of solving them is only about four centuries old.

• Dido's problem, ancient. The legend in Virgil's Aeneid says that Queen Dido was allowed as much land as an ox hide could surround, and cut the hide into a thin strip: how should a given length enclose the largest area? The answer, a circle, is among the first optimization problems.
• Johannes Kepler, 1615. Kepler studied the volume of wine barrels and noticed that near the largest volume a small change of shape hardly changes the volume. That flatness at the top is exactly what f'=0 says.
• Pierre de Fermat, about 1629–1636. Fermat described a method for maxima and minima: compare f(x) with f(x+e), divide by e, and then set e to zero. Without the name, it is the derivative equal to zero.
• Snell and Fermat, 1621 and 1662. Willebrord Snell found the law of refraction around 1621 without publishing it; Descartes printed it in 1637. In 1662 Fermat showed that it follows from the principle that light takes the path of least time, one of the first physical laws stated as an optimization.
• Harris and Wilson, 1913 and 1934. Ford W. Harris derived the economic order quantity in 1913, and R. H. Wilson popularized it in 1934, which is why the inventory result is called the Wilson lot size formula.
• Today. Setting the derivative to zero, and its many-variable version with the gradient, is the core of fitting a line to data and of training machine-learning models, where the minimum is found by a search that moves downhill.

What mistakes do people make in optimization problems?

The most common mistakes in applied optimization are the nine below, each with the correct statement.

Practice: test your understanding

These questions mix everything above. A wrong answer costs nothing here: read the hint and try again.

Summary: applied optimization at a glance

• The four steps: read; introduce variables and relations; write the objective as a function of one variable with its domain; test critical points and endpoints.
• Domain: from the situation; closed means compare the endpoints, open means limits at the ends or the sign of f' and f''.
• Geometry: closed can h=2r, open can h=r, field on a river twice as long as it is wide, rectangle in a semicircle of radius R has area R^2.
• Light: the quickest path gives (\sinθ_1)/(c_1)=(\sinθ_2)/(c_2); a mirror gives equal angles.
• Economics: r'(x)=c'(x) at maximum profit; the delivery cycle x=√((2K)/(hd)); the Wilson lot size q=√((2km)/(h)).
• Whole numbers: compare the two whole numbers around the optimum.
• Check: units, domain, maximum or minimum, and the quantity asked.
• Code: SymPy diff, solve, limit, or a golden-section search for a function that falls and then rises.

Glossary: key terms

Objective function

The quantity to be made largest or smallest, written as a function of one variable.

Constraint

A relation between the variables, such as a fixed volume or a fixed length of wire, used to remove all but one of them.

Domain

The values of the variable for which the situation makes sense, which may be closed or open.

Critical point

An interior point of the domain where the derivative is zero or does not exist.

Marginal cost

The derivative of the cost function, about the cost of making one more item.

Fermat’s principle

Light travels between two points along the path that takes the least time.

Snell’s law

The law of refraction: the sine of the angle from the normal divided by the speed is the same on both sides of a boundary.

Wilson lot size

The order quantity that minimizes the average cost of ordering and holding stock, the square root of twice the ordering cost times the demand over the holding cost.

Frequently asked questions

References

1. Joel Hass, Christopher Heil, Maurice D. Weir et al. (2023). Thomas' Calculus: Early Transcendentals in SI Units (15th ed.), Section 4.6: Applied Optimization. Pearson.
2. James Stewart (2015). Calculus (8th ed.), section 4.7: Optimization Problems. Cengage Learning.
3. Pierre de Fermat (1636). Methodus ad disquirendam maximam et minimam. Oeuvres de Fermat, Paris.
4. Ford W. Harris (1913). How Many Parts to Make at Once. Factory, The Magazine of Management.

Related articles

• Extreme Values of Functions on Closed Intervals: Extreme values on closed intervals: absolute and local extremes, the Extreme Value Theorem, critical points and the closed interval method, with examples and code.
• Concavity and Curve Sketching: Concavity and curve sketching: the second derivative, points of inflection, the Second Derivative Test and seven steps to sketch a graph, with examples and code.
• Monotonic Functions and the First Derivative Test: Monotonic functions and the First Derivative Test: where a function rises and falls from the sign of f′, local extrema, sign charts and inequalities, with code.
• The Derivative as a Rate of Change: The derivative as a rate of change: velocity, speed, acceleration and jerk, free fall, marginal cost and revenue, sensitivity to change, and rates from data in code.