Maximization of quadratic form over unit Euclidean sphere not centered at the origin

Let $x \in \mathbb{R}^n$ and let $P$ be a $n \times n$ positive definite symmetrix matrix. It is known that the maximum of

$$\begin{array}{ll} \text{maximize} & x^T P \, x\\ \text{subject to} & x^T x \leq 1\end{array}$$

is $\lambda_{\text{max}}(P)$, the largest eigenvalue of $P$. Now consider the following problem

$$\begin{array}{ll} \text{maximize} & x^T P \, x\\ \text{subject to} & (x-a)^T (x-a) \leq 1\end{array}$$

where $a \in \mathbb{R}^n$ is known. What is the analytical solution?


Solution 1:

This is (a variant of) the trust-region problem, and the solution can be computed rather easily, although not an analytical solution

See, e.e., https://www8.cs.umu.se/kurser/5DA001/HT07/lectures/trust-handouts.pdf

I'm reparameterizing your problem slightly, you can easily change your model to be $\max x^TQx + c^Tx + b$ subject to $x^Tx\leq 1$. At optimality, you will be at the border of feasibility, and the constraint gradient will be pointing in the same direction as the objective gradient (draw this geometrically!), i.e., you have $2Qx + c = \lambda 2x$ for some unknown $\lambda$. Solve for $x$ to obtain $x = -(2Q-\lambda I)^{-1}c$. To find lambda, solve $x^Tx = 1$ which is an equation in $\lambda$ (possibly tricky, numerical methods required, line-search, bisection etc)