Minimize $x^T A x$, subject to $\|x\|=1$. Show that ${x^*}^TAx^*$ is the smallest eigenvalue of $A$ in magnitude

Solution 1:

I will write the Lagrangian as objective -$v$ constrain (rather than +, but they are both correct) $$ (\mathbf{A} + \mathbf{A}^T)\mathbf{x}^* - 2v\mathbf{x}^* = \left[(\mathbf{A} + \mathbf{A}^T) - 2v\mathbf{I}\right]\mathbf{x}^* = \mathbf{0} $$ does not imply $$ v\mathbf{I} = \dfrac{1}{2}(\mathbf{A} + \mathbf{A}^T) \qquad $$

Rather it implies $$det((\mathbf{A} + \mathbf{A}^T) - 2v\mathbf{I})=0,$$ because it is a vector equation not scalar.

And this is the definition of characteristic function for eigenvalues. So that tells us the dual variable $v$ is an eigenvalue of $A$ when duality gap is zero or when the primal and dual pair exists.

Now to show that $\mathbf{x}^*\mathbf{A}^T\mathbf{x}^* $ is the smallest eigenvalue we need to assume that $A$ is positive definite. I think this must be given as otherwise the optimization problem is not convex and hence we won't be able to find a unique $\mathbf{x}^*$. Assuming unique solution and from $\mathbf x^*$ and $v$ being the eigenvector and eigenvalue note that we have $$A\mathbf{x}^*=v\mathbf x^*$$ then$$\mathbf{x}^{*T} A\mathbf{x}^*=v\mathbf x^* \mathbf x^{*T}$$ and since $\mathbf x^* \mathbf x^{*T}=1$ $$\mathbf{x}^{*T} A\mathbf{x}^*=v$$ and since we minimized $$\mathbf{x}^T A\mathbf{x}$$ we have that $\mathbf{x}^{*T} A\mathbf{x}^*$ indeed is the minimum eigenvalue.

Solution 2:

The first equation where you set the derivative to zero, is in fact describing an eigenvalue and the corresponding eigenvector of $\frac{1}{2}(A+A^T)$. So the stationary points of the Lagrangian are eigenvectors.

One correction: In your second to last equation you should have $\cdots+2v^*I$ rather than $v^*$ (note that $v^*$ is a scalar not a matrix). However, you don't need this equation at all. The first one suffices.

Also I think the solution to the minimization is the smallest eigenvalue of $\frac{1}{2}(A+A^T)$ rather than that of $A$. If $A$ is symmetric then both of these values coincide.