II.5.3.3: Quadratic on a Sphere

Suppose we want to minimize $$f(x)=x'Ax+2b'x+c$$ over $x$ satisfying $x'Dx=1$, with $D$ positive definite. In addition, we require $x\in\mathcal{K}$, with $\mathcal{K}$ a convex cone. This problem is important in several optimal scaling problems. It can be solved by using the modified eigenvalue methods of section III.1.9.7, or by the decomposition method of I.6.5.1, but here we give a simple majorization method.

Find $\lambda$ such that $D^{-\frac12}AD^{-\frac12}\lesssim \lambda I.$ Then $$x'Ax\leq y'Ay+2(x-y)'Ay+\lambda(x-y)'D(x-y)$$ and thus $$g(x,y):=c+y'Ay+2(x-y)'Ay+2b'x+\lambda(x-y)'D(x-y)$$ majorizes $f$.

Minimizing $g$ over $x'Dx=1$ and $x\in\mathcal{K}$ amounts to minimizing $$h(x):=(x-z)'D(x-z)$$ with $$z:=-D^{-1}((A-\lambda D)y+b)$$ over $x\in\mathcal{K}$ and then normalizing the solution such that $x'Dx=1$.

The function quadSphere solves the problem from this section. Note that the cone can be the whole space, in which case we minimize the quadratic on the ellipsoid $x'Dx=1$, and we can have $b=0$, in which case we compute the generalized eigenvector corresponding with the smallest generalized eigenvalue of the pair $(A,D).$ Also note that $A$ can be indefinite.