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?
Best Answer
Thank @Brian Borchers for your comments.
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