Quadratic Optimization on the Unit Sphere

Why a Quadratic Form on the Sphere Is an Eigenvalue Problem

A symmetric matrix assigns a scalar \(x^T A x\) to each vector \(x\). If vectors can have any length, this quantity can grow in magnitude just by scaling \(x\). Restricting \(x\) to the unit sphere removes that scaling freedom and gives a finite optimization problem. The resulting problem has a direct interpretation: its smallest and largest possible values are the smallest and largest eigenvalues of \(A\).

This connection is useful whenever a direction matters more than a vector’s length. It also explains why eigenvectors appear as the directions where a quadratic form is stationary under a unit-length constraint.

Definition: Let \(A\) be a real symmetric \(p\times p\) matrix, and let \(x\in\mathbb{R}^p\). The quadratic form is \(q(x)=x^T A x\). The unit sphere is \(S^{p-1}=\{x\in\mathbb{R}^p:x^T x=1\}\). The problem of optimizing \(q(x)\) over \(S^{p-1}\) is called quadratic optimization on the unit sphere.

Because \(A\) is symmetric, its eigenvalues are real and it has an orthonormal basis of eigenvectors. Write them as \(\lambda_1\leq\lambda_2\leq\cdots\leq\lambda_p\), with corresponding orthonormal eigenvectors \(u_1,\ldots,u_p\). This is the real spectral theorem. The optimization argument below uses this basis to determine both the stationary points and the global extrema.

The Stationary-Point Condition

Write the constraint as \(g(x)=x^T x-1=0\). Its gradient is \(\nabla g(x)=2x\), which is nonzero at every point on the unit sphere. Thus the equality-constraint Lagrange multiplier condition applies at any constrained stationary point. Since \(A\) is symmetric, the gradient of \(q\) is \(2Ax\).

Theorem: A vector \(x\) on \(S^{p-1}\) is a stationary point of \(x^T A x\) subject to \(x^T x=1\) if and only if \(Ax=\lambda x\) for some scalar \(\lambda\). Thus the stationary points are exactly the unit eigenvectors of \(A\), and at each such point the objective value equals the corresponding eigenvalue.

To obtain the condition, form the Lagrangian \(\mathcal{L}(x,\lambda)=x^T A x-\lambda(x^T x-1)\). Its gradient with respect to \(x\) is \(2Ax-2\lambda x\). Setting this gradient equal to zero gives \(Ax=\lambda x\). Conversely, if a unit vector satisfies \(Ax=\lambda x\), it satisfies the Lagrange condition and is a constrained stationary point. Multiplying the equation on the left by \(x^T\) gives \(x^T A x=\lambda x^T x=\lambda\), as claimed. \(\square\)

The same condition can be read geometrically. A feasible infinitesimal displacement \(h\) at \(x\) must be tangent to the sphere, so \(x^T h=0\). The first-order change in the objective in that direction is \(2h^T Ax\). It is zero for every tangent \(h\) precisely when \(Ax\) is parallel to \(x\), which is the eigenvector condition.

Worked Example: A Diagonal Quadratic Form

Let \(A=\begin{pmatrix}-2&0\\0&5\end{pmatrix}\). Find the stationary points and the minimum and maximum of \(q(x)=x^T A x\) on the unit circle.

The stationary condition is \(Ax=\lambda x\). The coordinate vectors \(e_1=(1,0)^T\) and \(e_2=(0,1)^T\) are unit eigenvectors, with eigenvalues \(-2\) and \(5\), respectively. The unit eigenvectors are \(e_1,-e_1,e_2,-e_2\), so these are all the stationary points. Their objective values are \(q(e_1)=q(-e_1)=-2\) and \(q(e_2)=q(-e_2)=5\).

Directly, if \(x=(x_1,x_2)^T\) and \(x_1^2+x_2^2=1\), then \(q(x)=-2x_1^2+5x_2^2=-2+7x_2^2\). Since \(0\leq x_2^2\leq1\), the minimum is \(-2\), attained at \(\pm e_1\), and the maximum is \(5\), attained at \(\pm e_2\). This calculation agrees with the eigenvalue characterization.

Global Extrema from the Eigenvalues

Every unit vector can be expanded in the orthonormal eigenbasis as \(x=\sum_{i=1}^p c_i u_i\), where \(\sum_{i=1}^p c_i^2=1\). Because \(Au_i=\lambda_i u_i\) and the eigenvectors are orthonormal,

x^T A x =\left(\sum_{i=1}^p c_i u_i\right)^T \left(\sum_{i=1}^p c_i\lambda_i u_i\right) =\sum_{i=1}^p \lambda_i c_i^2.

The coefficients \(c_i^2\) are nonnegative and sum to one. Therefore the objective is a weighted average of the eigenvalues. This gives the bounds and also shows exactly when equality is possible.

Theorem: For a real symmetric matrix \(A\) with smallest and largest eigenvalues \(\lambda_{\min}\) and \(\lambda_{\max}\), \(\min_{x^T x=1}x^T A x=\lambda_{\min}\) and \(\max_{x^T x=1}x^T A x=\lambda_{\max}\). The minimum is attained exactly by the unit vectors in the eigenspace for \(\lambda_{\min}\); the maximum is attained exactly by the unit vectors in the eigenspace for \(\lambda_{\max}\).

Proof. In an orthonormal eigenbasis, each eigenvalue satisfies \(\lambda_{\min}\leq\lambda_i\leq\lambda_{\max}\). For a unit vector with coordinates \(c_i\),

\lambda_{\min} =\lambda_{\min}\sum_{i=1}^p c_i^2 \leq \sum_{i=1}^p\lambda_i c_i^2 =x^T A x \leq \lambda_{\max}\sum_{i=1}^p c_i^2 =\lambda_{\max}.

A unit eigenvector for \(\lambda_{\min}\) attains the lower bound, and a unit eigenvector for \(\lambda_{\max}\) attains the upper bound. For equality in the lower bound, each term \((\lambda_i-\lambda_{\min})c_i^2\) must be zero. Thus \(c_i\) can be nonzero only for eigenvalues equal to \(\lambda_{\min}\), so \(x\) lies in that eigenspace. The same argument applied to \((\lambda_{\max}-\lambda_i)c_i^2\) characterizes equality in the upper bound. The sphere is compact and the quadratic form is continuous, so these bounds are indeed the global minimum and maximum. \(\square\)

Worked Example: A Nondiagonal Matrix

Let \(A=\begin{pmatrix}2&1\\1&2\end{pmatrix}\). Find the smallest and largest values of \(x^T A x\) on the unit circle and give the vectors attaining them.

The characteristic equation is \(\det(A-\lambda I)=(2-\lambda)^2-1=0\), so the eigenvalues are \(\lambda=1\) and \(\lambda=3\). For \(\lambda=1\), the equation \((A-I)x=0\) gives \(x_1=-x_2\). A normalized eigenvector is \(u_{\min}=(1,-1)^T/\sqrt{2}\). For \(\lambda=3\), the equation \((A-3I)x=0\) gives \(x_1=x_2\), with normalized eigenvector \(u_{\max}=(1,1)^T/\sqrt{2}\).

The global minimum is therefore \(1\), attained at \(u_{\min}\) and \(-u_{\min}\); the global maximum is \(3\), attained at \(u_{\max}\) and \(-u_{\max}\). For a direct check, write \(x=(a,b)^T\) with \(a^2+b^2=1\). Then \(x^T A x=2a^2+2ab+2b^2=2+2ab\). Since \(2ab\) ranges from \(-1\) to \(1\), the same extrema follow. The endpoints occur at \(a=-b\) and \(a=b\), respectively.

Stationary Points Need Not Be Global Extrema

The stationary-point condition identifies all unit eigenvectors, not only those associated with the smallest or largest eigenvalue. An eigenvector for an intermediate eigenvalue can be a saddle point on the sphere. To see the local behavior, let \(v\) be a unit eigenvector with eigenvalue \(\lambda\), and let \(w\) be a unit eigenvector orthogonal to \(v\), with eigenvalue \(\mu\). The curve \(x(t)=\cos(t)v+\sin(t)w\) stays on the unit sphere, and orthogonality gives

q(x(t))=\lambda\cos^2(t)+\mu\sin^2(t) =\lambda+(\mu-\lambda)\sin^2(t).

If there are eigenvalues both below and above \(\lambda\), choose \(w\) first from an eigenspace below it and then from one above it. For every sufficiently small nonzero \(t\), the first choice decreases the objective and the second increases it. Hence \(v\) is a saddle point. If \(\lambda=\lambda_{\min}\), the eigenvalue bound ensures that \(v\) is a global minimum; if \(\lambda=\lambda_{\max}\), it is a global maximum. When all eigenvalues are equal, \(A=\lambda I\) and the objective is constant on the sphere.

Worked Example: A Stationary Saddle Point

Take \(A=\operatorname{diag}(-2,1,4)\), and consider \(v=e_2=(0,1,0)^T\). Since \(Av=e_2\), this is a stationary point with objective value \(1\). It is not a minimum or maximum because the other eigenvalues lie on both sides of \(1\).

In the direction \(e_1\), the feasible curve \(x_1(t)=\cos(t)e_2+\sin(t)e_1\) has \(q(x_1(t))=\cos^2(t)-2\sin^2(t)=1-3\sin^2(t)\), which is less than \(1\) whenever \(t\) is small and nonzero.

In the direction \(e_3\), the feasible curve \(x_3(t)=\cos(t)e_2+\sin(t)e_3\) has \(q(x_3(t))=\cos^2(t)+4\sin^2(t)=1+3\sin^2(t)\), which is greater than \(1\) whenever \(t\) is small and nonzero. The objective therefore rises in one feasible direction and falls in another: \(e_2\) is a saddle point.

Repeated Eigenvalues and a Common Pitfall

If the smallest or largest eigenvalue is repeated, the corresponding optimizer is not limited to a pair of signed eigenvectors. Every unit vector in the associated eigenspace attains the same extreme value. For example, if \(A=\operatorname{diag}(2,2,5)\), every unit vector of the form \((a,b,0)^T\), with \(a^2+b^2=1\), attains the minimum \(2\). Every unit vector in the eigenspace for \(5\), namely \(\pm e_3\), attains the maximum.

Common mistake: A student may find one eigenvector and conclude that its eigenvalue is the maximum because it is a stationary value. This is incorrect: stationarity alone does not distinguish a maximum from a minimum or a saddle. Compare the eigenvalue with the full spectrum. The largest eigenvalue gives the global maximum, the smallest gives the global minimum, and an eigenvalue strictly between them gives saddle stationary points.

Key takeaway: For a real symmetric matrix, constrained stationarity on the unit sphere is the eigenvector equation \(Ax=\lambda x\). The eigenvalue is the objective value at that point; the smallest and largest eigenvalues give the global minimum and maximum, with all optimizers lying in their respective eigenspaces.

Check Your Understanding

Use the stationary condition and eigenvalue characterization to answer the following.

For \(A=\operatorname{diag}(0,3)\), state the minimum and maximum values on the unit circle and identify all vectors attaining them.
Why is the Lagrange multiplier condition regular at every point of the unit sphere?
If a symmetric matrix has eigenvalues \(-1,2,6\), what is the objective value at a unit eigenvector for eigenvalue \(2\), and why is that point a saddle?
When the smallest eigenvalue has multiplicity greater than one, what set of unit vectors attains the minimum?
Explain why a stationary point of the constrained problem need not be a global extremum.