0
$\begingroup$

Let $u$ and $v$ be column vectors of size $n \gg 1$ (not both zero), and consider the matrix $A:=uu^T+vv^T$

Question

What is an analytic formula for $\arg\max_{\|z\|_\infty \le 1}z^TAz=\arg\max_{\|z\|_\infty \le 1}(z^Tu)^2 + (z^Tv)^2$ ?

Observations

  • In the constraint, if we replace $\|\cdot\|_\infty$ with $\|\cdot\|_2$, then the question corresponds to finding the leading eigenvector of $A$ and was asked an answered in this thread Analytic formula for leading eigenvector of $uu^T + vv^T$?.
  • In the special case where $u=0$, the problem reduces to $\arg\max_{\|z\|_\infty \le }|z^Tv|^2$, which is solved by taking $z_j= \operatorname{sign}(v_j)$ for all $j$.
Improve this question
$\endgroup$
1
$\begingroup$

For general matrices $A$, I believe that the problem is not solvable and have heard people say that it is NP with $N$ equal to the number of positive eigenvalues of $A$. That's because you are trying to find the maximum of a convex function on the unit hypercube, which has $2^N$ corner points.

But for your particular case, the problem is easy to solve. Since $A$ has only two non-trivial (and positive!) eigenvalues, you can restrict yourself to the plane spanned by $u$ and $v$ -- i.e., the solution must lie in the intersection of the plane $z=\alpha u + \beta v$ and the optimization is over the variables $\alpha,\beta$. Furthermore, $\|z\|_\infty\le 1$ implies that you optimize over the intersection of that plane and the unit cube, which is a two-dimensional polygon that is easily described. Finally, because the objective function is convex, the solution to your problem needs to be in one of the vertices of that polygon.

As a consequence, all you need to do is enumerate the vertices of the polygon and test the objective function there.

Improve this answer
$\endgroup$
  • $\begingroup$ Thanks. And you think there is an efficient generate these vertices ? The sucess of this method relies on this. $\endgroup$ – dohmatob Oct 21 '19 at 17:13
  • $\begingroup$ BTW, why's the problem related to eigenvalues of $A$ ? $\endgroup$ – dohmatob Oct 21 '19 at 21:24
  • $\begingroup$ If $A$ is size $n\times n$, then given its form it has $n-2$ zero eigenvalues. All components of $z$ in the directions of these $n-2$ eigenvalues have no contribution to the objective function, so these are "dead variables". The only contributions come from components in direction $u$ and $v$. $\endgroup$ – Wolfgang Bangerth Oct 22 '19 at 0:10
  • $\begingroup$ As for your first question, you need to think about the geometry of the intersection of a 2-dimensional plane that goes through the origin with an $n$ dimensional cube $[-1,1]^n$. That can't be a very complicated object to describe. $\endgroup$ – Wolfgang Bangerth Oct 22 '19 at 0:12
  • $\begingroup$ Simple object to describe or not, this is still a vertex-enumeration problem. It turns out this is a standard problem in computational geometry and can be solved in $\mathcal O(2nv)=\mathcal O(nv)$ time and $\mathcal O(2n)=\mathcal O(n)$ space, where $v$ is the number of vertices in the intersection. Thanks anyways. $\endgroup$ – dohmatob Oct 22 '19 at 8:28

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.