Help with Optimization Problem: Matrix Calculus

Question

Can someone please help me with this problem? I am clueless :(

$$ \left\{ \begin{array}{rclrcl} \min f(u) &=& u^tAu\\ \text{s.$\,$t.} \sum_{j=1}^n u_j &=& 0,& \sum_{j=1}^n u_j^2 &=&1\end{array} \right. $$

Answer 1

Without loss of generality, we can assume that $A$ is symmetric since $f$ is a homogeneous quadratic form (if $A$ is not symmetric, note that $f(u)=\frac 12u^t\cdot (A+A^t)\cdot u$).

Therefore $\nabla f=2 A\cdot u$.

Let $V$ denote the variety $u_1+\dots+u_n=u_1^2+\dots+u_n^2-1=0$. Note that $V$ is smooth and compact, hence the minimum of $f$ is reached at a smooth critical point of $f$ on $V$.

Next, we introduce two Lagrange multipliers $\lambda,\mu$: $u$ is a critical point of $f$ on $V$ iff there exists $\lambda,\mu\in\mathbb R$ such that $A\cdot u=\lambda\cdot\begin{bmatrix}1\\\vdots\\1\end{bmatrix} + \mu\cdot\begin{bmatrix}u_1\\\vdots\\u_n\end{bmatrix}$.

Consequently, for any critical point $u$, $(A-\mu\cdot {\rm Id})\cdot u$ lies in the vector space spanned by $\begin{bmatrix}1\\\vdots\\1\end{bmatrix}$. So $\mu$ would be an Eigenvalue of the restriction of the operator $A$ to the orthogonal complement of this vector space.

This gives a way to compute all the critical points. Then to find the minimum, it is sufficient to compare the critical values (there are only finitely-many such values).

Answer 2

Let $v_i=u_{i+1}-v_i$ for $i<n$, let $v_n=\Sigma u_i$, then in the new coordinates the condition becomes $v_n=0$ and $v$ lies on a sphere in that hyperplane. This converts the problem into finding the spectrum of $A$ composed with the projection on that hyperplane.