I'm solving constrained optimization exercises for preparing my final exam. I got stuck at this question.
$$ \begin{array}{ll}
\text{min} & \mathbf{x}^T\mathbf{A}\mathbf{x} \\
\text{s.t.} & \|\mathbf{x}\|_2=1
\end{array} $$
I'm asked to show that, if the minimum point of the function is $\mathbf{x}^*$ in the domain, then magnitude of the smallest eigenvalue of $\mathbf{A}$ is ${\mathbf{x}^*}^T\mathbf{A}\mathbf{x}^*$.
I tried these:
$$ \begin{array}{lcll}
f(\mathbf{x}) & = & \mathbf{x}^T\mathbf{A}\mathbf{x} & \qquad \text{(objective function)} \\
h(\mathbf{x}) & = & \mathbf{x}^T\mathbf{x}-1 = 0 & \qquad \text{(equality constrain)}
\end{array} $$
The Lagrangian is
$$ \mathcal{L}(\mathbf{x},v) = f(\mathbf{x}) + vh(\mathbf{x}) = \mathbf{x}^T\mathbf{A}\mathbf{x} + v\mathbf{x}^T\mathbf{x} – v, $$
where $v$ is the Lagrange multiplier.
Next, I tried finding infinimum of $\mathcal{L}(\mathbf{x},v)$.
$$ \mathbf{0} = \dfrac{\partial}{\partial \mathbf{x}} \mathcal{L}(\mathbf{x},v) = \mathbf{x}^T(\mathbf{A}+\mathbf{A}^T) + 2v\mathbf{x}^T \\
(\mathbf{A} + \mathbf{A}^T)\mathbf{x}^* + 2v^*\mathbf{x}^* = \left[(\mathbf{A} + \mathbf{A}^T) + 2v^*\mathbf{I}\right]\mathbf{x}^* = \mathbf{0} \\
\implies v^*\mathbf{I} = -\dfrac{1}{2}(\mathbf{A} + \mathbf{A}^T) \qquad \text{(doesn't seem to be correct)} $$
I'm not able to go on any further. How do I find $\mathbf{x}^*$ after this point?
Best Answer
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.