I.6.6.1: Quadratic Form on a Sphere

We now discuss an actual example. Consider the problem of minimizing the function $$f(z)=\frac{(z-b)'A(z-b)+c}{z'z},$$ over $z\not= 0$, where we make no assumptions on the matrix $A$, the vector $b$, and the scalar $c$. Instead of going the usual route of differentiating and solving the stationary equations, we use the decomposition approach.

Define $$g(x,\lambda)=\frac{(\lambda x-b)'A(\lambda x-b)+c}{\lambda^{2}x'x},$$ or, letting $\theta=\lambda^{-1}$, $$g(x,\theta)=\frac{\theta^{2}(b'Ab+c)-2\theta b'Ax+x'Ax}{x'x},$$ Then $$\inf_{z\not= 0} f(z)=\inf_{x'x=1}\inf_{\theta\geq 0} g(x,\theta),$$ but also $$\inf_{z\not= 0} f(z)=\inf_{x'x=1}\inf_{\theta} g(x,\theta).$$ If $x'x=1$ then $$\inf_{\theta}g(x,\theta)=\inf_{\theta}\theta^{2}(b'Ab+c)-2\theta b'Ax+x'Ax.$$ We distinguish three cases.

• If $b'Ab+c>0$ the minimum is attained at $$\hat\theta=\frac{b'Ax}{b'Ab+c}$$ and the minimum is equal to $x'\overline Ax$, where $$\overline A=A-\frac{Abb'A}{b'Ab+c}.$$ It follows that in this case $\min_{z} f(z)$ is the smallest eigenvalue of $\overline A$, written as $\kappa(\overline A)$. If $\overline{x}$ is the corresponding unit-length eigenvector, then the minimizer of $f(z)$ is $$\hat z=\frac{b'Ab+c}{b'A'\overline x}\ \overline x.$$

• If $b'Ab+c<0$ the minimum is not attained and $\inf_{\theta} g(x,\theta)=-\infty$ for each $x$. Thus $\inf_{z} f(z)=-\infty$ as well.

• If $b'Ab+c=0$ then we must distinguish two sub-cases. If $b'Ax=0$ then $\min_{\theta }g(x,\theta)=x'Ax$. If $b'Ax\not=0$ then $\inf_{\theta} g(x,\theta)=-\infty$ again. Thus if $b'Ab+c=0$ we have $\inf_{z} f(z)=-\infty$, unless both $c=0$ and $Ab=0$, in which sub-case we have $\min_{z} f(z)$ equal to $\kappa(A)$, the smallest eigenvalue of $A$ and the minimizer equal to any corresponding eigenvector.

Of course if $Ab=0$ we have $\overline A=A$. Thus $$\inf_{z} f(z)=\begin{cases} \kappa(\overline A)&\text{ if }(b'Ab+c>0)\text{ or }(Ab=0\text{ and }c=0),\\ -\infty&\text{otherwise}. \end{cases}$$

Now start with the alternative decomposition $$\min_{z\not= 0}f(z)=\min_{x'x=1}\min_{\theta\geq 0}\theta^{2}(b'Ab+c)-2\theta b'Ax+x'Ax.$$ We want to show that although the intermediate calculations are different, the result is the same.

• If $b'Ab+c>0$ and $b'Ax\geq 0$ then $\min_{\theta }g(x,\theta)=x'\overline Ax$, as before. But if If $b'Ab+c>0$ and $b'Ax<0$ the minimum is attained at $\hat\theta=0$, and $\min_{\theta }g(x,\theta)=x'Ax$. Because $\kappa(\overline A)$ is less than or equal to $\kappa(A)$, we still have $\min_{z} f(z)$ equal to the smallest eigenvalue of $\overline A$.

• If $b'Ab+c<0$ we stiil have $\inf_{z} f(z)=-\infty$.

• If $b'Ab+c=0$ we distinguish three sub-cases. If $b'Ax=0$ then $\min_{\theta }g(x,\theta)=x'Ax$, as before. If $b'Ax\>0$ then $\inf_{\theta} g(x,\theta)=-\infty$. And if $b'Ax<0$ the minimum is attained at $\hat\theta=0$ and equal to $x'Ax$. Again we have $\inf_{z} f(z)=-\infty$, unless both $c=0$ and $Ab=0$, when $\min_{z} f(z)$ is equal to $\kappa(A)$.

We have solved the problem by using the decompositions~\eqref{E:g2} and~\eqref{E:g3}. But we can also interchange the order of the infimums and use $$\inf_{z\not= 0} f(z)=\inf_{\theta\geq 0}\inf_{x'x=1}g(x,\theta),$$ or $$\inf_{z\not= 0} f(z)=\inf_{\theta}\inf_{x'x=1}g(x,\theta).$$

Let's look at the problem $\min_{x'x=1}g(x,\theta)$. For a minimum we must have $x=\theta(A-\mu I)^{-1}Ab,$ where the Lagrange multiplier $\mu$ is chosen such that $\theta^{2}b'A(A-\mu I)^{-2}Ab=1$. At the minimum $$\begin{multline*} \min_{x'x=1}g(x,\theta)=\\\theta^{2}[(b'Ab+c)-2b'A(A-\mu I)^{-1}Ab+b'A(A-\mu I)^{-1}A(A-\mu I)^{-1}Ab] \end{multline*}$$