Consider the following problem:
Problem: Given $n\times n$-Hermitian matrices $A_1,\dots,A_r$, find $e_1,\dots,e_r\in\{-1,1\}$ such that $\|e_1A_1+\dots+e_rA_r\|_\infty$ is maximized. Here the norm is the usual operator norm $\|A\|_\infty=\max\{\|Ax\|_2:\|x\|_2=1\}.$
I would like to know the computational complexity of this problem. Can this problem be solved in polynomial time? Is it NP-complete?
At the very least, can the following problem be solved in polynomial time with probability at least $1/2$: Suppose that $n,r$ are natural numbers. We are given an oracle that returns a tuple $(A_1,\dots,A_r)$ of independent random (GUE) $n\times n$-Hermitian matrices or a tuple of independent random $(A_1,\dots,A_r)$ (GOE) $n\times n$-symmetric matrices. One can access the oracle an unlimited number of times. Then the goal is to find a tuple $(A_1,\dots,A_r)$ produced by the oracle along with $\{e_1,\dots,e_r\}\in\{-1,1\}$ such that $$\|e_1A_1+\dots+e_rA_r\|_\infty=\max\{\|g_1A_1+\dots+g_rA_r\|_\infty:\{g_1,\dots,g_r\}\in\{-1,1\}\}.$$ One has an unlimited number of attempts at submitting a solution to this problem, and at least one of those submitted solutions needs to be the actual solution. I have designed this problem so that it is as easy as possible to get a solution in polynomial time, but where the problem is still non-trivial.
Motivation
I am generally interested in questions about maximizing the spectral radius. Let $\simeq$ be the equivalence relation on the collection of all complex matrices where $A\simeq B$ precisely when there is some $\lambda$ with $|\lambda|=1$ and $A=\lambda B$. Suppose that we are given a collection of equivalence classes with respect to $\simeq$ of $n\times n$-complex matrices $[A_1],\dots,[A_r]$. The goal is to find $\lambda_1,\dots,\lambda_r$ so that the matrices $\lambda_1 A_1,\dots,\lambda_r A_r$ are as similar to each other as reasonably possible. There are several objective functions that allow us to choose $\lambda_1,\dots,\lambda_r$. One such objective function will be to maximize the spectral radius $\rho(\lambda_1A_1+\dots+\lambda_rA_r)$. An advantage of using the spectral radius is that $\rho(R)=\rho(\lambda CRC^{-1})$ whenever $|\lambda|=1$. I am interested in maximizing the spectral radius because in my case, the equivalence classes $[A_1],\dots,[A_r]$ were obtained by maximizing a spectral radius, so by maximizing $\rho(\lambda_1A_1+\dots+\lambda_rA_r)$, we finish the process of maximizing the spectral radius.
Given real matrices $A_1,\dots,A_r$, it is sometimes the case that if we compute $|\lambda_1|=\dots=|\lambda_r|=1$ such that $\rho(\lambda_1A_1+\dots+\lambda_rA_r)$ is locally maximized, then there is some $\lambda$ along with $e_1,\dots,e_r\in\{-1,1\}$ where $\lambda_j=\lambda\cdot e_j$ for $1\leq j\leq r$.
Given Hermitian matrices $A_1,\dots,A_r$, define a mapping $M:S_1^r\rightarrow[0,\infty)$ by letting $M(\lambda_1,\dots,\lambda_r)=\rho(\lambda_1A_1+\dots+\lambda_rA_r)$. Then whenever I found a local maximum $(\lambda_1,\dots,\lambda_r)$ for $M$, there was always a $\lambda$ along with $e_1,\dots,e_r\in\{-1,1\}$ with $\lambda_j=\lambda\cdot e_j$ for $1\leq j\leq r$. Therefore, the function $M$ is well behaved.
In this case, we have $\rho(\lambda_1A_1+\dots+\lambda_rA_r)=\|e_1A_1+\dots+e_rA_r\|_\infty$. The spectral radius behaves better than the spectral norm with regard to maximization; if we define $L:S_1^r\rightarrow\mathbb{R}$ by letting $L(\lambda_1,\dots,\lambda_r)=\|\lambda_1A_1+\dots+\lambda_rA_r\|_\infty$ and we locally maximize $L$, then the local maximum will not be of the form $(\lambda e_1,\dots,\lambda e_r)$ for $e_1,\dots,e_r\in\{0,1\}$.
Since the function $M$ is well-behaved one sense, I am wondering if it is well-behaved in another sense. I am wondering if it is easy to globally maximize $M$. Each point of the form $(e_1,\dots,e_r)$ where $e_1,\dots,e_r\in\{-1,1\}$ is a critical point of both the functions $L,M$, and it is likely that a randomly selected point of the form $(e_1,\dots,e_r)$ where $e_1,\dots,e_r\in\{-1,1\}$ is a local maximum for the function $M$. Since $M$ appears to have many local maxima, $M$ seems to be poorly behaved in another sense, but I am wondering if $M$ is well or poorly behaved with regard to our ability to compute the local maxima of $M$ and in particular the local maxima of the form $(e_1,\dots,e_r)$ where $e_1,\dots,e_r\in\{-1,1\}$.
