Let $Q \in \mathbb{R}^{n \times n}$ be positive definite. I am trying to solve $$\min f(x) = ||x||^2$$ $$\text{s.t } \hspace{0.3 cm} h(x) = x^TQx-1 = 0$$ The constraint set is closed and bounded, so there is indeed a minimum.
We have $\nabla f(x) = 2x$ and $\nabla h(x) = 2Qx$, so the Lagrange multiplier system is
$$2x + \lambda 2Qx=0$$ $$x^TQx = 1$$
The problem is, I cannot seem to get an explicit solution to this system. The only thing I can come up with is an algorithm.
The first equation is equivalent to $$Qx = - \dfrac {1}{\lambda}x.$$
($\lambda$ can't be zero since that would imply $x = 0$, which cannot happen since $0$ is not in the constraint set)
So $x$ has to be an eigenvector of $Q$. Since $Q$ is symmetric, it has $n$ distinct eigenvalues $\mu_i$, so the geometric multiplicity of each eigenvalue is $1$, so all the eigenspaces are of the form $\text{span} \{v_i \}.$
Thus $x = c_i v_i$ for some $i$, so then for each $i$ I would plug in $cv_i$ into $x^TQx = 1$, which yields $$c_i = \pm \sqrt{\dfrac {1}{v_i^TQV_i}}.$$
Finally, I would plug in $c_iv_i$ into the objective function $f$ for every $i$, and see which one gives me the lowest value.
My question is: is my algorithm correct, and is there a better way to solve this problem?
Thank you.
You have an error here. $Q$ does not necessarily have distinct eigenvalues (take $Q$ to be the identity matrix, for example). But there is nevertheless an orthonormal basis of eigenvectors. If $\mu_1$ is the largest eigenvalue of $Q$ with corresponding eigenvector $v$ chosen so that $h(v)=v^\top Qv = \mu\|v\|^2=1$, then this $v$ will give you the minimum value of $f(x)$.
If we choose $\{v_i\}$ to be an orthonormal basis of eigenvectors and write $x=\sum y_iv_i$, then $Q(x) = \sum \mu_i y_i^2$. Thus, if $\mu_1\ge\mu_j$ for all $j$, we have $$Q(x)=\sum \mu_i y_i^2 \le \mu_1 \|y\|^2 = \mu_1 \|x\|^2.$$ We conclude that if $Q(x)=1$, then $\|x\|^2\ge 1/\mu_1$, with equality holding precisely when $x=\pm \dfrac1{\sqrt{\mu_1}}v_1$.