# 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?

• The keyword here is "quadratic programming". I am afraid there is no analytical solution in general. For obtaining numerical solutions, take a look to (en.wikipedia.org/wiki/Quadratic_programming). – Jean Marie Sep 22 '17 at 10:25
• Thanks, yes I know there is no analytical solution in general. Though, in the case of the unit sphere constraint, it can be shown that the analytical solution is the max eigenvalue of $P$. So, I was wondering if the analytical solution can be found also in the case of the shifted sphere. – pulosky Sep 22 '17 at 10:27
• @Rodrigo de Azevedo You are right. – Jean Marie Sep 22 '17 at 11:29

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)