Chapter 15

Constrained Optimization

Realistic optimization problems often involve some sort of a constraint:

What is the best product we can make, with a fixed budget?
What is the most efficient rocket we can build of a fixed mass?
What is the least expensive building design, given the external factors of material and labor costs?

Abstractly, all of these questions ask the following: what are the extreme values of $𝑓 (𝑥, 𝑦)$ given that we constrain the points $(𝑥, 𝑦)$ by some function, $𝑔 (𝑥, 𝑦) = 𝑐$ ? In this section, we learn a couple methods to deal with such questions.

15.1Reducing Dimension by Substitution

The first method is to solve the constraint for one of the variables and substitute it into the function you wish to optimize. This forces the inputs to obey the constraint, reducing the number of variables by one.

Example 15.1 (Substitution on a Line). Maximize $𝑧 = 4 - 2 𝑥 2 - 3 𝑦 2 + 𝑥 - 𝑦$ subject to the constraint $𝑥 + 𝑦 = 2$ .

The constraint gives $𝑦 = 2 - 𝑥$ . Substituting this into the objective produces the one-variable function

ℎ (𝑥) = 4 - 2 𝑥 2 - 3 (2 - 𝑥) 2 + 𝑥 - (2 - 𝑥) = - 5 𝑥 2 + 14 𝑥 - 10 .

Since

ℎ' (𝑥) = - 10 𝑥 + 14,

the only critical point is $𝑥 = 7 / 5$ , which is a maximum because $ℎ$ is a downward-opening parabola. Therefore

(𝑥, 𝑦) = (75, 35), 𝑧 m a x = - 15 .

Figure 15.1 A constraint takes away a dimension. The problem may only stand on the red line

𝑥 + 𝑦 = 2

, so the surface hardly matters: what matters is the wall of values over the line, and substituting

𝑦 = 2 - 𝑥

hands you exactly that wall flattened out—

ℎ (𝑥) = 𝑓 (𝑥, 2 - 𝑥)

, an ordinary one-variable function whose ordinary maximum at

ℎ' (𝑥) = 0

answers the question.

This also works in higher dimensions: we can take a problem of three variables with one constraint and turn it into a problem of two variables with no constraints.

Example 15.2 (A Box on a Fixed Budget). Find the maximum value of $𝑥 𝑦 𝑧$ subject to

𝑥 + 𝑦 + 𝑧 = 1, 𝑥, 𝑦, 𝑧 \geq 0 .

The nonnegativity conditions matter: they make $𝑥, 𝑦, 𝑧$ possible side lengths and restrict the constraint to a closed triangle. Solving for $𝑧$ gives

𝑧 = 1 - 𝑥 - 𝑦,

so we maximize

ℎ (𝑥, 𝑦) = 𝑥 𝑦 (1 - 𝑥 - 𝑦)

over $𝑥 \geq 0$ , $𝑦 \geq 0$ , and $𝑥 + 𝑦 \leq 1$ . In the interior,

ℎ 𝑥 = 𝑦 (1 - 2 𝑥 - 𝑦), ℎ 𝑦 = 𝑥 (1 - 𝑥 - 2 𝑦) .

The interior critical point is

𝑥 = 𝑦 = 13, 𝑧 = 13 .

The product is zero along the boundary of the triangle, while at this point it is $1 / 27$ . Thus

(𝑥, 𝑦, 𝑧) = (13, 13, 13)

gives the maximum.

Figure 15.2 The same idea, one dimension up. A box's corner

(𝑥, 𝑦, 𝑧)

must spend the whole budget

𝑥 + 𝑦 + 𝑧 = 1

, so the corner lives on a triangle—a two-dimensional domain. Substituting

𝑧 = 1 - 𝑥 - 𝑦

makes the volume a free function of two variables, and the triangle wears that function's contour plot to prove it: nested loops closing in on the best box, the cube

𝑥 = 𝑦 = 𝑧 = 13

Unfortunately, this method relies on being able to solve the constraint for a given variable and substitute it into the objective function. This is often impossible: many relations of two variables cannot be solved for either variable independently.

15.2Lagrange Multipliers

What are we to do if we cannot substitute the constraint? It helps to think geometrically: in a two-variable problem, we can draw the function $𝑧 = 𝑓 (𝑥, 𝑦)$ as a surface in $ℝ 3$ and the constraint $𝑔 (𝑥, 𝑦) = 𝑐$ as a curve in the domain, the $𝑥 𝑦$ -plane.

It's even more helpful to draw this as a contour plot with level sets. The constraint (our hiker's trajectory) still appears as a curve, but we can easily read off exactly where our hiker is going uphill or downhill by looking at how they are crossing contours.

Figure 15.3 When substitution fails, walk the constraint and watch the height. Beside the map, the same journey stands in space: a pane of glass filling in the values of

𝑓

straight over the circle, its rim rising and falling as the walker goes. The marked points are the rim's crests and troughs—the constrained maxima and minima—and the walker passes them on both pictures at once. The question the next figure answers: what is special about those spots on the map?

Whenever the hiker is crossing a contour they are either increasing or decreasing in elevation, and so cannot be at an extremum. Indeed, at a regular constrained extremum, their path must be tangent to a level set! This is the fundamental insight.

A regular constrained extremum can occur only where the constraint is tangent to a level set of the objective.

Everything follows from this: but the work is in turning this qualitative insight into a system of equations. The first observation we can make is that the constraint itself $𝑔 (𝑥, 𝑦) = 𝑐$ is a level set - just of a different function. So extreme values of $𝑓$ along the constraint can occur where this constraint level set is tangent to a level set of $𝑓$ .

Figure 15.4 The same walk, now watching the level set underfoot. Wherever that level set cuts across the constraint, the walker can keep climbing or descending along the circle, so no crossing point is an extremum. At each marked max and min the two curves do not cross—they kiss, running along the one shared golden direction. Tangency is the geometric secret: at regular constrained extrema, the constraint is tangent to a level set of

𝑓

But this relation of is tangent to is still difficult to deal with. To help, we remember that the gradient vector is perpendicular to level sets! Thus, $\nabla 𝑓$ and $\nabla 𝑔$ are both perpendicular to their level sets, and thus these vectors must be parallel since the level sets are tangent.

Now we've really made some progress! We just need to remember that parallel means are scalar multiples of each other and give this scalar multiple a name: its traditional name is the Greek letter $𝜆$ .

Theorem 15.3 (Lagrange Multipliers). If $𝑓$ has a constrained local extremum at a point $⃗ 𝑝$ on the constraint

𝑔 (⃗ 𝑥) = 𝑐

and $\nabla 𝑔 (⃗ 𝑝) \neq ⃗ 0$ , then there is a number $𝜆$ such that

\nabla 𝑓 (⃗ 𝑝) = 𝜆 \nabla 𝑔 (⃗ 𝑝) .

Figure 15.5 Tangency, restated with vectors—and nothing moving. The gradient field of

𝑓

fills the background, the level curves that touch the circle without crossing it are picked out in color, and at every marked candidate two arrows stand side by side at full size: the circle's normal in red and

\nabla 𝑓

in ink, exactly parallel or exactly anti-parallel. Each arrow is perpendicular to its own curve, and there the two curves are tangent, so the directions have no choice:

\nabla 𝑓 = 𝜆 \nabla 𝑔

. Had a critical point of

𝑓

sat right on the circle, its

\nabla 𝑓

would be the zero vector—a dot, the

𝜆 = 0

case—and the equation would hold trivially.

This is now a fully precise, quantitative claim: it tells us that we can find candidates for the constrained extrema by solving a system of equations!

{\nabla 𝑓 (𝑥, 𝑦) = 𝜆 \nabla 𝑔 (𝑥, 𝑦), 𝑔 (𝑥, 𝑦) = 𝑐 .

Recalling that the gradient is the vector of partial derivatives, this is just the system of equations

⎧ { {⎨ { {⎩ 𝑓 𝑥 (𝑥, 𝑦) = 𝜆 𝑔 𝑥 (𝑥, 𝑦), 𝑓 𝑦 (𝑥, 𝑦) = 𝜆 𝑔 𝑦 (𝑥, 𝑦), 𝑔 (𝑥, 𝑦) = 𝑐 .

There is no single strategy for solving all such systems beyond the substitution and elimination techniques familiar from precalculus. The solutions are candidates, not automatic maxima or minima: evaluate $𝑓$ at every candidate and compare the values.

The condition $\nabla 𝑔 \neq ⃗ 0$ is essential. If $\nabla 𝑔 = ⃗ 0$ at a point of the constraint, the theorem does not apply and that singular constraint point must be checked separately. On the other hand, $\nabla 𝑓 = ⃗ 0$ is allowed; it corresponds to $𝜆 = 0$ .

It is illustrative to redo the original example from the substitution section using the method of multipliers.

Example 15.4 (The Line Constraint Revisited). Maximize $𝑓 (𝑥, 𝑦) = 4 - 2 𝑥 2 - 3 𝑦 2 + 𝑥 - 𝑦$ subject to the constraint $𝑥 + 𝑦 = 2$ .

Let $𝑔 (𝑥, 𝑦) = 𝑥 + 𝑦$ . Then

\nabla 𝑓 = ⟨ - 4 𝑥 + 1, - 6 𝑦 - 1 ⟩, \nabla 𝑔 = ⟨ 1, 1 ⟩ .

The Lagrange equations are

- 4 𝑥 + 1 = 𝜆, - 6 𝑦 - 1 = 𝜆, 𝑥 + 𝑦 = 2 .

Solving gives

(𝑥, 𝑦) = (75, 35),

the same point found by substitution. The restriction of $𝑓$ to the line is a downward-opening parabola, so this candidate is the constrained maximum, with value $- 1 / 5$ .

Example 15.5 (An Ellipse on a Circle). Maximize $𝑓 (𝑥, 𝑦) = 𝑥 2 + 2 𝑦 2$ subject to the constraint $𝑥 2 + 𝑦 2 = 1$ .

With $𝑔 (𝑥, 𝑦) = 𝑥 2 + 𝑦 2$ , the equations

⟨ 2 𝑥, 4 𝑦 ⟩ = 𝜆 ⟨ 2 𝑥, 2 𝑦 ⟩

together with $𝑥 2 + 𝑦 2 = 1$ give the candidates

(\pm 1, 0) a n d (0, \pm 1) .

The objective has value $1$ at $(\pm 1, 0)$ and value $2$ at $(0, \pm 1)$ . Therefore the constrained maximum is $2$ , attained at $(0, \pm 1)$ ; the constrained minimum is $1$ , attained at $(\pm 1, 0)$ .

Example 15.6 (The Box Revisited). Find the maximum value of $𝑥 𝑦 𝑧$ subject to

𝑥 + 𝑦 + 𝑧 = 1, 𝑥, 𝑦, 𝑧 \geq 0 .

For an interior candidate with $𝑥, 𝑦, 𝑧 > 0$ , the Lagrange equations are

𝑦 𝑧 = 𝜆, 𝑥 𝑧 = 𝜆, 𝑥 𝑦 = 𝜆, 𝑥 + 𝑦 + 𝑧 = 1 .

They imply $𝑥 = 𝑦 = 𝑧 = 1 / 3$ , where the product is $1 / 27$ . On the boundary at least one side length is zero, so the product is zero. Thus the interior candidate is the absolute maximum.

15.3Inequality Constraints and Boundaries

For an inequality constraint, we break the problem into two cases. On each smooth boundary component, where the constraint is an equality, we use either Lagrange multipliers or substitution. In the interior, we perform standard unconstrained optimization and consider only critical points inside the domain. Corners, endpoints, and singular boundary points must be checked separately.

A continuous function on a closed and bounded feasible region attains an absolute maximum and minimum. To find them:

Find critical points in the interior.
Optimize on each smooth boundary component using substitution or Lagrange multipliers.
Check corners, endpoints, and singular boundary points separately.
Evaluate the objective at every candidate.
Compare the resulting values.

This will result in several sets of potential extrema: those occurring on the inside, those occurring on smooth boundaries, and possibly corners or singular points. How do you find the absolute max or min? That's easy! Just take the largest or smallest overall result.

Figure 15.6 An inequality constraint means two hunts and one comparison. Inside the allowed region—shaded on the map, its boundary drawn on the surface beside it—hunt critical points as in the last chapter; on the boundary, hunt constrained candidates as in this one: for the disk they are the same tangency points as the figures above. Then evaluate every candidate and compare. The ringed points win, and on the surface you can see why: the absolute max and min stand visibly highest and lowest of all the ground the constraint allows. The second tab swaps the disk for a square, whose boundary brings a third list: the four corners, where two edges meet and no derivative condition applies, are candidates by their mere existence.

Example 15.7 (Optimization on a Closed Disk). Find the absolute maximum and minimum of

𝑓 (𝑥, 𝑦) = 𝑥 2 + 2 𝑦 2

subject to

𝑥 2 + 𝑦 2 \leq 1 .

In the interior,

\nabla 𝑓 = ⟨ 2 𝑥, 4 𝑦 ⟩ = ⃗ 0

only at $(0, 0)$ , where $𝑓 = 0$ . On the boundary circle, the Lagrange calculation above gives $(\pm 1, 0)$ with value $1$ and $(0, \pm 1)$ with value $2$ . Comparing all candidates, the absolute minimum is $0$ at $(0, 0)$ and the absolute maximum is $2$ at $(0, \pm 1)$ .

This completes our study of differentiation. In Part IV, we reverse the point of view: instead of measuring local change, we accumulate quantities over two- and three-dimensional regions.