0

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$.
dohmatob
  • 175
  • 6

1 Answers1

1

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.

Wolfgang Bangerth
  • 55,373
  • 59
  • 119
  • Thanks. And you think there is an efficient generate these vertices ? The sucess of this method relies on this. – dohmatob Oct 21 '19 at 17:13
  • 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 00: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 00: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 08:28
  • In my particular problem, we must have $v \le 4$. Thus enumeration problem can be solved (using Avis-Fakuda https://en.wikipedia.org/wiki/Vertex_enumeration_problem) in $\mathcal O(n)$ time (and space) for enumerating the vertices, plus $\mathcal O(n)$ of evaluating the objective function per vertex. Total complexity is therefore $\mathcal O(n)$ time (and space). – dohmatob Oct 22 '19 at 08:38
  • There you go :-) – Wolfgang Bangerth Oct 22 '19 at 13:30