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?

  • $\begingroup$ 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. $\endgroup$ – Brian Borchers Dec 18 '20 at 18:38
  • $\begingroup$ 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. $\endgroup$ – wolfustc Dec 18 '20 at 19:10
  • $\begingroup$ 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$. $\endgroup$ – Brian Borchers Dec 18 '20 at 20:08

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

  • $\begingroup$ 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). $\endgroup$ – iarbel84 Dec 19 '20 at 9:35
  • $\begingroup$ 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. $\endgroup$ – wolfustc Dec 20 '20 at 19:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.