Analytic formula for $\arg\max_{\|z\|_\infty \le 1}z^T A z$, where $A=uu^T+vv^T$

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$$.

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.
• BTW, why's the problem related to eigenvalues of $A$ ? – dohmatob Oct 21 '19 at 21:24
• 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$. – Wolfgang Bangerth Oct 22 '19 at 0:10
• 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. – Wolfgang Bangerth Oct 22 '19 at 0:12
• 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. – dohmatob Oct 22 '19 at 8:28