Quadratic Functions on Polygonal Regions

Why Quadratics Suit Polygonal Regions

A quadratic function on a polygon has a useful structure: its derivatives are simple, and its restriction to any straight edge is a one-variable quadratic. This makes it possible to organize the search for absolute extrema into two parts: check stationary points in the interior, then optimize along each edge. For convex quadratics, there is an additional shortcut for finding the maximum: it is enough to compare the vertices.

The shortcut has limits. Convexity does not, in general, make a vertex a minimum, and a quadratic can have an interior stationary point that is a saddle rather than an extremum. The Hessian classification and the edge calculations explain which candidates must be checked and why.

Quadratic Form and Interior Classification

Write a point in the plane as \(\mathbf{x}=(x,y)^{\top}\). A quadratic function has the form

where \(\mathbf{H}\) is symmetric, \(\mathbf{b}\) is a constant vector, and \(c\) is a constant. The gradient and Hessian are

An interior stationary point \(\mathbf{x}_0\) satisfies \(\nabla q(\mathbf{x}_0)=\mathbf{0}\), or equivalently \(\mathbf{H}\mathbf{x}_0=-\mathbf{b}\). Because the Hessian is constant, its definiteness classifies the behavior at every stationary point.

For a two-variable quadratic, let \(\Delta=\det(\mathbf{H})\). If \(\Delta>0\), then \(a>0\) means \(\mathbf{H}\) is positive definite, while \(a<0\) means it is negative definite. If \(\Delta<0\), the matrix is indefinite. When \(\Delta=0\), it is semidefinite or zero, and its trace determines the sign unless the matrix is zero. A positive definite Hessian gives a strict local minimum at a stationary point; a negative definite Hessian gives a strict local maximum; an indefinite Hessian gives a saddle. A nonzero semidefinite Hessian gives a global, but possibly non-strict, minimum or maximum at a stationary point. If \(\mathbf{H}=\mathbf{0}\) and a stationary point exists, then \(\mathbf{b}=\mathbf{0}\) and the function is constant.

Restricting the Function to an Edge

Let an edge run from vertex \(\mathbf{P}\) to vertex \(\mathbf{Q}\). Its points can be written as \(\mathbf{x}(t)=\mathbf{P}+t(\mathbf{Q}-\mathbf{P})\), with \(0\leq t\leq 1\). Substitution into \(q\) gives a one-variable quadratic \(g(t)=At^2+Bt+C\). The edge candidates are the endpoints \(t=0,1\) and any root of \(g'(t)=2At+B=0\) that lies in \([0,1]\). If \(A=0\), the restriction is linear or constant, so its extrema occur at endpoints unless it is constant, in which case every point on that edge has the same value.

Vertices appear as endpoints of adjoining edges, so they need only be evaluated once. If an edge restriction is constant, its value is already represented at its endpoints. This candidate procedure applies whether the polygon is convex or nonconvex.

Worked Example: A Saddle Inside a Rectangle

Why a Convex Quadratic Has a Vertex Maximum

A quadratic is convex when its Hessian is positive semidefinite. The key fact is that its value at a weighted average of points is no greater than the corresponding weighted average of its values. This gives a direct proof of the vertex rule.

To prove the result, first consider points \(\mathbf{v}_1,\ldots,\mathbf{v}_n\) and nonnegative weights \(\lambda_i\) with \(\sum_i\lambda_i=1\). Let \(\mathbf{x}=\sum_i\lambda_i\mathbf{v}_i\). Expanding the quadratic and cancelling the linear and constant terms gives

Each term on the right is nonnegative because \(\mathbf{H}\) is positive semidefinite. Thus \(q(\mathbf{x})\leq\sum_i\lambda_iq(\mathbf{v}_i)\leq\max_i q(\mathbf{v}_i)\). Every point in a polygon lies in the convex hull of its vertices, including when the polygon is nonconvex. Therefore no point in the region has a value greater than the largest vertex value. Since the vertices belong to the region, that largest value is attained at a vertex.

Worked Example: A Convex Quadratic on a Triangle

Convexity Does Not Give a Vertex Minimum

The vertex theorem is specifically a maximum result. A convex function can have a minimum in the interior or on the interior of an edge. For example, \(q(x,y)=x^2+y^2\) is convex, but on the square \([-1,1]\times[-1,1]\) its minimum is \(0\) at \((0,0)\), while its vertices all have value \(2\). To find a minimum, use the full candidate procedure: inspect interior stationary points and optimize each edge. Do not replace those calculations with a vertex comparison unless a separate argument justifies it.

A Common Error: Ignoring an Edge Stationary Point

A frequent mistake is to check only polygon vertices when the quadratic is not known to be convex, or when the goal is to find a minimum. For example, on \(0\leq x\leq 3,\;y=0\), the restriction \(g(x)=x^2-2x\) has endpoint values \(g(0)=0\) and \(g(3)=3\). Concluding that the minimum is \(0\) from those endpoints is wrong: \(g'(x)=2x-2=0\) at \(x=1\), and \(g(1)=-1\). The correction is to include each edge's interior stationary points in the candidate set. The vertex-only maximum shortcut is valid for convex quadratics, but it does not remove edge candidates when finding a minimum.