Why Nonconvex Regions Need a Careful Boundary Search
A nonconvex region can bend around a missing portion of the plane. Its boundary may therefore contain pieces that face inward, as well as pieces that form the outer outline. Those inward-facing pieces are still part of the boundary. A maximum or minimum can occur on one of them, so checking only the apparent outer outline can produce an incomplete candidate list.
The reliable method is to divide the boundary into manageable pieces, restrict the function to each piece, and collect its stationary values and endpoint values. Interior critical points must be checked separately. The final comparison is only valid once every part of the boundary has been included.
Regions, Interiors, and Boundary Pieces
A region \(R\) is a subset of the plane. Its interior consists of points that have a small open disk lying entirely inside \(R\); its boundary consists of points for which every small disk meets both \(R\) and points outside \(R\). A region is nonconvex if there are two points in it for which the line segment joining them is not entirely contained in the region.
For the searches in this tutorial, suppose \(R\) is closed and bounded, and \(f\) is continuous on \(R\). Suppose also that \(f\) is differentiable in the interior, and that the boundary can be divided into finitely many smooth pieces, each parametrized over a closed interval, with \(f\) restricted to each piece differentiable in the parameter. If a restriction fails to be differentiable at some interior parameter value, include that value among the boundary candidates. The pieces can be straight edges or smooth arcs. Their endpoints must be included in the search.
Because \(R\) is closed and bounded, it is compact. The extreme value theorem says that a continuous function on a compact region attains both an absolute maximum and an absolute minimum. Thus a complete search must locate candidates that include both extrema. The interior-and-boundary candidate principle gives a way to do that.
The Candidate Principle and Why It Works
Here, an interior critical point is a point in the interior where both first partial derivatives are zero (assuming \(f\) is differentiable there). For a boundary parametrization \(\mathbf{r}(t)\), the restricted function is \(g(t)=f(\mathbf{r}(t))\). A stationary point on the piece occurs at an interior parameter value where \(g'(t)=0\). If a restriction has no stationary point in the interval’s interior, its extrema occur at endpoints.
The reasoning is a short consequence of familiar necessary conditions for extrema. A global extremum exists by compactness and continuity. If it occurs in the interior, it is also a local extremum of a differentiable function on an open neighborhood, so both partial derivatives must vanish. If it occurs on the boundary, it belongs to at least one boundary piece. Along that piece, the restricted one-variable function has an extremum; an interior parameter value at such an extremum has derivative zero, while an endpoint is included explicitly. Therefore, the candidate list contains every possible location of an absolute extremum.
This argument identifies where to look; it does not say that every candidate is an extremum. The function values must still be compared. A stationary point of a boundary restriction may be a maximum, a minimum, or neither relative to the whole region.
Worked Example: A Quadratic on an L-Shaped Region
Worked Example: Check All Six Boundary Pieces
Consider the closed L-shaped region \(R=([0,3]\times[0,1])\cup([0,1]\times[1,3])\) and the function \(f(x,y)=(x-\frac12)^2+(y-\frac12)^2\). Find its absolute minimum and maximum.
The interior consists of the interiors of the two rectangular arms, together with their shared interior portion. The gradient is \(\nabla f=(2(x-\frac12),2(y-\frac12))\), so the only interior critical point is \((\frac12,\frac12)\). This point lies in the region’s interior, and \(f(\frac12,\frac12)=0\).
The boundary has six segments: the bottom \(y=0,\ 0\le x\le3\); the right edge \(x=3,\ 0\le y\le1\); the inward-facing horizontal edge \(y=1,\ 1\le x\le3\); the inward-facing vertical edge \(x=1,\ 1\le y\le3\); the top \(y=3,\ 0\le x\le1\); and the left edge \(x=0,\ 0\le y\le3\).
On the bottom edge, the restriction is \(f(x,0)=(x-\frac12)^2+\frac14\). Its derivative is \(2(x-\frac12)\), so the stationary point is \(x=\frac12\), with value \(\frac14\). The endpoints give \(f(0,0)=\frac12\) and \(f(3,0)=\frac{13}{2}\).
On the right edge, \(f(3,y)=\frac{25}{4}+(y-\frac12)^2\). The stationary point is \(y=\frac12\), with value \(\frac{25}{4}\). At both endpoints the value is \(\frac{13}{2}\): specifically, \(f(3,0)=\frac{25}{4}+\frac14=\frac{13}{2}\) and \(f(3,1)=\frac{25}{4}+\frac14=\frac{13}{2}\).
On the inward-facing horizontal edge, \(f(x,1)=(x-\frac12)^2+\frac14\). Its stationary point as a formula is \(x=\frac12\), but that parameter is outside the segment \(1\le x\le3\). The endpoints give \(f(1,1)=\frac12\) and \(f(3,1)=\frac{13}{2}\).
On the inward-facing vertical edge, \(f(1,y)=\frac14+(y-\frac12)^2\). Its stationary point as a formula is \(y=\frac12\), outside the segment \(1\le y\le3\). The endpoints give \(f(1,1)=\frac12\) and \(f(1,3)=\frac{13}{2}\).
On the top edge, \(f(x,3)=(x-\frac12)^2+\frac{25}{4}\). The stationary point \(x=\frac12\) lies on the segment and gives \(\frac{25}{4}\). Each endpoint gives \(\frac{13}{2}\), since \(f(0,3)=\frac14+\frac{25}{4}=\frac{13}{2}\) and \(f(1,3)=\frac14+\frac{25}{4}=\frac{13}{2}\).
On the left edge, \(f(0,y)=\frac14+(y-\frac12)^2\). The stationary point \(y=\frac12\) gives \(\frac14\). The endpoints give \(f(0,0)=\frac12\) and \(f(0,3)=\frac{13}{2}\).
All candidate values are at least \(0\), and the interior point gives \(0\), so the absolute minimum is \(0\) at \((\frac12,\frac12)\). The largest candidate value is \(\frac{13}{2}\), attained at \((3,0)\), \((3,1)\), \((1,3)\), and \((0,3)\). Thus the absolute maximum is \(\frac{13}{2}\). Substitution into the original function confirms each listed maximum value; for instance, \(f(3,1)=(\frac52)^2+(\frac12)^2=\frac{26}{4}=\frac{13}{2}\).
This example shows why a boundary restriction’s stationary point must lie on the segment being considered. It also shows why every endpoint must be evaluated, even when a restriction has an interior stationary point.
Worked Example: A Linear Function on a Cross
Worked Example: Include the Inward Corners
Let \(R=([-2,2]\times[-1,1])\cup([-1,1]\times[-2,2])\), a compact cross-shaped nonconvex region, and let \(f(x,y)=x+2y\). Find its absolute extrema.
The partial derivatives are \(f_x=1\) and \(f_y=2\). They cannot both be zero, so there are no interior critical points. The boundary is a polygon with twelve edges. On a horizontal edge, \(f\) varies linearly with nonzero slope \(1\); on a vertical edge, it varies linearly with nonzero slope \(2\). Thus no edge has an interior stationary point, and the candidate values occur at the boundary vertices.
In cyclic order, the vertices and their function values are \((1,2):5\), \((1,1):3\), \((2,1):4\), \((2,-1):0\), \((1,-1):-1\), \((1,-2):-3\), \((-1,-2):-5\), \((-1,-1):-3\), \((-2,-1):-4\), \((-2,1):0\), \((-1,1):1\), and \((-1,2):3\). For example, \(f(-1,-2)=-1+2(-2)=-5\), and \(f(1,2)=1+2(2)=5\).
The smallest and largest values in the complete list are \(-5\) and \(5\). Therefore the absolute minimum is \(-5\) at \((-1,-2)\), and the absolute maximum is \(5\) at \((1,2)\). Direct substitution gives those same values. The vertices \((1,1)\), \((-1,1)\), \((-1,-1)\), and \((1,-1)\) include inward-facing corners; their edges are part of the boundary even though they do not lie on the cross’s outermost rectangle.
Worked Example: An Extremum on an Inward-Facing Edge
Worked Example: Do Not Omit the Notch
Use the L-shaped region from the first example, but now let \(f(x,y)=(x-2)^2+(y-1)^2\). Find the absolute extrema.
The gradient is \(\nabla f=(2(x-2),2(y-1))\), which vanishes only at \((2,1)\). That point lies on the inward-facing horizontal boundary, not in the interior, so there are no interior critical points.
On the bottom edge \(y=0\), \(f(x,0)=(x-2)^2+1\). The stationary point \(x=2\) gives \(1\); the endpoints give \(f(0,0)=5\) and \(f(3,0)=2\).
On the right edge \(x=3\), \(f(3,y)=1+(y-1)^2\). Its minimum occurs at the endpoint \(y=1\), with value \(1\); the other endpoint gives \(f(3,0)=2\).
On the inward-facing horizontal edge \(y=1,\ 1\le x\le3\), \(f(x,1)=(x-2)^2\). The stationary point \(x=2\) gives \(0\), and the endpoints each give \(1\).
On the inward-facing vertical edge \(x=1,\ 1\le y\le3\), \(f(1,y)=1+(y-1)^2\). Its smallest value is \(1\) at \(y=1\), and its other endpoint gives \(f(1,3)=5\).
On the top edge \(y=3,\ 0\le x\le1\), \(f(x,3)=(x-2)^2+4\). This decreases throughout the segment, so its endpoint values are \(f(0,3)=8\) and \(f(1,3)=5\).
On the left edge \(x=0,\ 0\le y\le3\), \(f(0,y)=4+(y-1)^2\). The stationary point \(y=1\) gives \(4\), and the endpoint values are \(f(0,0)=5\) and \(f(0,3)=8\).
The least candidate value is \(0\), and substitution gives \(f(2,1)=0\). The greatest is \(8\), and substitution gives \(f(0,3)=4+4=8\). Therefore the absolute minimum is \(0\) at \((2,1)\), on the inward-facing edge, and the absolute maximum is \(8\) at \((0,3)\).
A Common Mistake: Checking Only the Outer Outline
In the last example, suppose the inward-facing edges are wrongly omitted. The remaining outer edges are the bottom, right, top, and left edges. Their candidate values have minimum \(1\), not \(0\): the bottom and right edges reach \(1\), while the top and left edges have larger minima. One might therefore incorrectly report \(1\) as the absolute minimum.
The error is that \((2,1)\) lies on the boundary of the region, even though it faces the missing upper-right portion of the plane. The correct restriction on that horizontal boundary piece is \(f(x,1)=(x-2)^2\), which gives \(0\) at \(x=2\). Including the inward-facing piece corrects the candidate list and the conclusion.
A Reliable Procedure
Mark its interior, outer boundary, and every inward-facing boundary piece.
Solve \(f_x=0\) and \(f_y=0\) for points that actually lie in the interior.
Parametrize or describe the piece, differentiate the one-variable restriction, and keep only stationary points on that piece.
Evaluate every segment or arc endpoint, including inward corners and points where the boundary pieces meet.
The smallest and largest values in the complete candidate list are the absolute minimum and maximum.
The central discipline is completeness. Nonconvexity does not change the candidate principle, but it makes it easier to overlook part of the boundary. Writing down the pieces before calculating helps prevent that omission.
Check Your Understanding
Use these questions to test whether your candidate search includes the entire region.
- Why must inward-facing edges be included in an absolute-extrema search?
- When does an interior point become a candidate for an extremum of a differentiable function?
- For a boundary piece parametrized over a closed interval, which parameter values must be checked?
- Why can a stationary point of a boundary restriction be discarded if it lies outside the parameter interval?
- In the final worked example, which omitted piece would cause the incorrect minimum value \(1\), and what value does the function attain there?