# Maximizing quadratic function over unit Euclidean ball

I am considering the following maximization problem

$$\begin{array}{ll} \text{maximize} & \| A x - b \|_2^2\\ \text{subject to} & \| x \|_2 \leq 1\end{array}$$

For easiness, let's assume $$A\in\mathbb R^{n\times p}$$ is a tall matrix ($$n>p$$), whose rank is $$p$$. Note that this is not least squares, as we are seeking the maximum instead of the minimum. Intuition is that the maximum must be achieved on the boundary, i.e., when $$\|x\|_2=1$$.

Is this a well studied problem? Any thought?

• This is a good exercise. Hint: Have you tried setting up the Lagrange multiplier (aka Karush-Kuhn-Tucker) conditions for the problem? You can show that the maximum is on the boundary and find the arg max by solving an eigenvalue problem. – Brian Borchers Dec 18 '20 at 18:38
• Thank you! If $b=0$, then the top right singular vector of $A$ is a quick solution. For $b\neq 0$, I use Lagrange multiplier ($\lambda$, for now let's switch to equality constraint for simplicity). And I get the following necessary conditions $A^\top A x + \lambda x = A^\top b$ with $\|x\|=1$. It's not obvious to me how I can transform it into an eigenvalue decomposition problem. – wolfustc Dec 18 '20 at 19:10
• If you keep the inequality, you can use complementary slackness to show that no maximum occurs in the interior. For nonzero values of $\lambda$, the eigenvalue decomposition of $A^{T}A$ can be used to solve for $x$. – Brian Borchers Dec 18 '20 at 20:08

Here is my reasoning following your comments. let's assume $$A$$ is a tall full-column-rank matrix. This is also the actual use case of my interest. That means $$(A^\top A)^{-1}$$ exists. In the following, I add superscript $$\ast$$ to denote optimum.

By complementary slackness,

$$\lambda^\ast (\|x^\ast\|^2-1) = 0$$ where $$\lambda^\ast \geq 0$$.

By stationarity,

$$(A^\top A - \lambda I) x^\ast = A^\top b$$

If $$x^\ast$$ is in the interior, then $$\lambda^\ast=0$$ and $$x^\ast=(A^\top A)^{-1}A^\top b$$. However we know that this is the least squares solution. It cannot be the maximum. Therefore $$\lambda^\ast>0$$. Then $$x^\ast=(A^\top A-\lambda^\ast I)^{-1}A^\top b$$. In other words, we need to seek a strictly positive $$\lambda^\ast$$ such that $$\|x^\ast\|=\|(A^\top A-\lambda^\ast I)^{-1}A^\top b\|=1$$. But my question is, does this $$\lambda^\ast > 0$$ always exist?

An update to my answer, I found this solved question, which is totally relevant. Maximization of quadratic form over unit Euclidean sphere not centered at the origin

• Nice work. Such $\lambda^*>0$ will exist if the original problem is bounded, i.e. the dual problem is feasible. Finding it might not be so simple (this is actually the dual optimization problem). – iarbel84 Dec 19 '20 at 9:35
• Yes, I also think it exists in general. But if we plot $\|(A^\top A -\lambda^\ast I)^{-1}A^\top b)\|$ against $\lambda^\ast$, there may be multiple $\lambda^\ast$ that can achieve unit norm. We will have to check which one is global maximum. – wolfustc Dec 20 '20 at 19:30