Using Monotonicity to Prune Candidate Searches

Why Monotonicity Can Reduce the Search

Finding absolute extrema on a closed, bounded region often begins by identifying interior critical points and examining the boundary. But that does not mean every boundary piece needs the same amount of calculation. If the function is monotone in a direction across the region, then moving in that direction always improves or always decreases its value. One side of the region can therefore be ruled out for a maximum, a minimum, or both.

The same idea applies after restricting the function to a boundary curve. A derivative with a fixed sign along a parametrized boundary piece tells us that values progress in one direction along that piece. Its interior points do not need to be tested individually: the relevant extremum on the piece is at an endpoint.

Definition: A function \(g\) is increasing on an interval if \(a<b\) implies \(g(a)\leq g(b)\), and decreasing if \(a<b\) implies \(g(a)\geq g(b)\). If the corresponding inequalities are strict, the function is strictly increasing or strictly decreasing.

The Derivative Sign Test

The one-variable derivative sign test gives the justification for pruning. If \(g\) is continuous on \([a,b]\) and differentiable on \((a,b)\), then \(g'(t)>0\) throughout \((a,b)\) implies that \(g\) is strictly increasing on \([a,b]\). Similarly, \(g'(t)<0\) implies that \(g\) is strictly decreasing. A nonnegative derivative implies nondecreasing behavior; a nonpositive derivative implies nonincreasing behavior.

Here is the short proof of the strict-increase case. Choose any \(u,v\in[a,b]\) with \(u<v\). By the Mean Value Theorem, there is a \(c\in(u,v)\) such that

$$ g(v)-g(u)=g'(c)(v-u). $$

Both factors on the right are positive: \(g'(c)>0\) by assumption, and \(v-u>0\). Thus \(g(v)-g(u)>0\), so \(g(v)>g(u)\). The other sign cases follow in the same way, with weak inequalities when the derivative is only nonnegative or nonpositive.

Pruning rule: If a function increases along an interval, its minimum on that interval occurs at the left endpoint and its maximum at the right endpoint. If it decreases, the endpoint roles reverse. With a non-strict derivative sign, endpoints still attain the appropriate extreme values, but other points can tie with them.

Using Partial Derivatives on Interior Slices

To apply this idea to a function \(f(x,y)\), hold one coordinate fixed and vary the other. For example, at a fixed value \(y=y_0\), consider the one-variable function \(g(x)=f(x,y_0)\) on the part of the region that lies at that height. Its derivative is \(g'(x)=f_x(x,y_0)\), where \(f_x\) denotes the partial derivative with respect to \(x\).

If every such horizontal slice is an interval and \(f_x>0\) throughout the region, then \(f\) increases as \(x\) increases along each slice. For a maximum, only the right endpoint of each slice needs to be considered; for a minimum, only the left endpoint needs to be considered. These endpoints lie on the region’s boundary. If \(f_x<0\), the endpoint choices reverse.

The analogous procedure holds for vertical slices using \(f_y\). The interval condition matters: if a slice consists of several separate intervals, apply the sign test to each interval separately. A derivative sign on one direction also does not settle how values vary along the resulting boundary. That remaining question can be handled by parametrizing the boundary piece and checking a one-variable derivative.

Worked Example: Pruning the Sides of a Rectangle

Find the absolute minimum and maximum of \(f(x,y)=x^2+3y\) on \(D=[0,2]\times[-1,1]\). For fixed \(x\), the slice has \(-1\leq y\leq1\), and

\frac{\partial f}{\partial y}=3>0.

So \(f\) increases with \(y\) on every vertical slice. The minimum must occur on the bottom edge \(y=-1\), and the maximum must occur on the top edge \(y=1\). The other points of each vertical slice cannot improve on those edge values.

On the bottom edge, set \(g_-(x)=f(x,-1)=x^2-3\). On the top edge, set \(g_+(x)=f(x,1)=x^2+3\). For both restrictions,

g_-'(x)=2x,\qquad g_+'(x)=2x,\qquad 0\leq x\leq2.

These derivatives are nonnegative, so both functions are nondecreasing. Their endpoint values are

g_-(0)=0^2-3=-3,\qquad g_-(2)=2^2-3=1, $$ $$ g_+(0)=0^2+3=3,\qquad g_+(2)=2^2+3=7.

Therefore the smallest value on the bottom edge is \(-3\), at \((0,-1)\), and the largest value on the top edge is \(7\), at \((2,1)\). The slice test shows these give the global minimum and maximum on the rectangle. As a direct check, \(0\leq x^2\leq4\) and \(-3\leq3y\leq3\), so \(-3\leq f(x,y)\leq7\); both bounds are attained at the stated points.

Following the Boundary After the Slice Test

Once a slice test identifies a boundary piece, that piece may itself have a range of points to examine. Parametrize it by a variable \(t\), writing the points as \(\boldsymbol{\gamma}(t)=(x(t),y(t))\) for \(a\leq t\leq b\). The restricted function is \(h(t)=f(x(t),y(t))\). By the chain rule, where the derivatives exist,

$$ h'(t)=f_x(x(t),y(t))x'(t)+f_y(x(t),y(t))y'(t). $$

A fixed sign for \(h'\) means that the values move in one direction along the parametrized piece. If \(h'>0\), the minimum and maximum on that piece are at \(t=a\) and \(t=b\), respectively; if \(h'<0\), they are at \(t=b\) and \(t=a\). The endpoints must still be included, since a boundary piece may meet another piece there. If \(h'\) changes sign, monotonicity on the whole interval has not been established: interior points where \(h'=0\), as well as endpoints, may need to be checked.

Worked Example: Reducing a Triangle to Two Edges

Find the absolute extrema of \(f(x,y)=x+y^2\) on the triangular region \(D=\{(x,y):0\leq y\leq x\leq1\}\). Fix \(y\in[0,1]\). Along that horizontal slice, \(y\leq x\leq1\), and

\frac{\partial f}{\partial x}=1>0.

Thus \(f\) increases with \(x\) across each slice. For the minimum, it is enough to consider the left endpoint \(x=y\). For the maximum, it is enough to consider the right endpoint \(x=1\). These are the two edges \(x=y\) and \(x=1\).

Parametrize the edge \(x=y\) by \(\boldsymbol{\gamma}_1(t)=(t,t)\), \(0\leq t\leq1\). Its restriction and derivative are

h_1(t)=f(t,t)=t+t^2,\qquad h_1'(t)=1+2t>0.

So \(h_1\) increases from \(h_1(0)=0+0^2=0\) to \(h_1(1)=1+1^2=2\). Parametrize the edge \(x=1\) by \(\boldsymbol{\gamma}_2(t)=(1,t)\), \(0\leq t\leq1\). Then

h_2(t)=f(1,t)=1+t^2,\qquad h_2'(t)=2t\geq0.

This restriction is nondecreasing, from \(h_2(0)=1\) to \(h_2(1)=2\). The slice comparison means the minimum on the whole region is the smallest value on the left endpoints, and the maximum is the largest value on the right endpoints. The edge calculations give minimum \(0\) at \((0,0)\) and maximum \(2\) at \((1,1)\). To check, \(x\geq y\geq0\) gives \(f=x+y^2\geq0\); also \(x\leq1\) and \(y\leq1\) give \(f\leq1+1=2\). Equality holds at the stated points.

A Curved Boundary Can Be Pruned the Same Way

A boundary need not be a straight edge for the method to work. The key is to use a parameter that describes the boundary interval and then differentiate the restricted function. In the next example, the slice test points to a curved boundary for the minimum and a straight boundary for the maximum. Monotonicity along each of those pieces reduces the search to their endpoints.

Worked Example: A Region Below a Parabola

Find the absolute extrema of \(f(x,y)=x+y\) on \(D=\{(x,y):0\leq x\leq1,\ 0\leq y\leq x^2\}\). For a fixed \(y\in[0,1]\), the horizontal slice runs from \(x=\sqrt{y}\) to \(x=1\). Since

\frac{\partial f}{\partial x}=1>0,

\(f\) increases across each slice. The minimum is therefore on the curved edge \(y=x^2\), and the maximum is on the straight edge \(x=1\).

Parametrize the curved edge by \(\boldsymbol{\gamma}_1(t)=(t,t^2)\), \(0\leq t\leq1\). The restriction is

h_1(t)=f(t,t^2)=t+t^2,\qquad h_1'(t)=1+2t>0.

It increases from \(h_1(0)=0\) to \(h_1(1)=2\). The minimum on this edge is \(0\) at \((0,0)\). On the edge \(x=1\), parametrize by \(\boldsymbol{\gamma}_2(t)=(1,t)\), \(0\leq t\leq1\). Then

h_2(t)=f(1,t)=1+t,\qquad h_2'(t)=1>0.

This edge increases from \(h_2(0)=1\) at \((1,0)\) to \(h_2(1)=2\) at \((1,1)\). The slice test assigns the minimum to the curved edge and the maximum to \(x=1\), so the absolute minimum is \(0\) at \((0,0)\) and the absolute maximum is \(2\) at \((1,1)\). Directly, \(0\leq y\leq x^2\) implies \(0\leq x+y\leq x+x^2\leq2\), with equality at those same points.

What Monotonicity Does Not Let You Skip

A derivative sign is useful only where its hypotheses apply. Check the sign on the entire interval being considered, not just at a few sample points. If the sign changes, the function may turn around, and the points where the derivative is zero or undefined can matter. If the derivative is nonnegative but vanishes at some points, endpoint values still bound the function, but the extreme may also occur elsewhere.

Likewise, a partial derivative sign answers a directional question: how does the function change while one coordinate is held fixed? It does not by itself say how the function changes along an oblique or curved boundary. For that, use the derivative of the boundary restriction. And when a boundary has several pieces, apply the reasoning piece by piece, retaining junctions and endpoints as possible extrema.

Common pitfall: Seeing \(f_x>0\) and concluding that the maximum is at the rightmost point of the entire region ignores the need to compare different horizontal slices. The valid conclusion is that, on each fixed-\(y\) slice, the largest value is at that slice’s right endpoint. The values at those right endpoints can still vary with \(y\), so their boundary restriction must be examined before the global maximum is identified.

A Practical Pruning Sequence

Monotonicity is most effective as an early reduction in a candidate search, not as a substitute for checking the remaining candidates. A careful procedure is:

Choose a slice direction.
Identify whether horizontal or vertical slices have simple interval descriptions inside the region.

Check the partial-derivative sign.
Verify its sign throughout the relevant slices, including any conditions needed for differentiability.

Keep the appropriate slice endpoints.
For increasing behavior, keep left endpoints for minima and right endpoints for maxima; reverse these choices for decreasing behavior.

Restrict to the remaining boundary pieces.
Parametrize each piece and test the derivative of the one-variable restriction.

Retain endpoints and any unresolved candidates.
If monotonicity fails on a remaining interval, its interior critical points may still need consideration.

This method matters because an absolute-extrema search can contain many boundary points that are unnecessary to evaluate. A derivative sign can turn an entire slice into a comparison of its endpoints, and a second sign test can reduce a boundary interval to its ends. The result is a smaller candidate set and a clearer explanation of why omitted points cannot produce a better value.

Check Your Understanding

Use derivative signs to decide which parts of each search can be pruned.

If \(g'(t)>0\) throughout an interval \([a,b]\), where on that interval do the minimum and maximum occur?
Suppose \(f_y(x,y)<0\) throughout a rectangle. Which horizontal edge can be discarded when searching for a maximum, and which when searching for a minimum?
For a fixed \(y\), why does \(f_x(x,y)>0\) identify the right endpoint of that slice as its largest value?
If a boundary restriction has derivative \(h'(t)\geq0\), what can be concluded about its endpoint values? Can other points tie for an extreme?
What must be checked if the derivative of a boundary restriction changes sign inside its parameter interval?