Maximization of $\infty$-norm with $2$-norm constraint Suppose we have a matrix $\mathbf B \in \mathbb R^{n\times n}$.  Is there an analytical solution to the following problem?
\begin{equation}
\begin{aligned}
&\max_{\mathbf x \in \mathbb R^n} && \|\mathbf B\mathbf x\|_{\infty} \\
&\ \ \text{s.t.} && \|\mathbf x\|_2\leq 1
\end{aligned}
\end{equation}
 A: I had a follow-up thought... By definition, $||\mathbf B\mathbf x||_\infty = \max_i \{ |\mathbf b_i^\text{T} \mathbf x|\}$, where $\mathbf b_i^\text{T}$ is the $i$th row of the matrix $\mathbf B$.  Then, if $||\mathbf x||_2 \leq 1$, we have
\begin{equation}
\begin{aligned}
||\mathbf B\mathbf x||_\infty &= \max_i \{ |\mathbf b_i^\text{T} \mathbf x|\} \\
&\leq \max_i \{ ||\mathbf b_i ||_2 ||\mathbf x||_2 \} \\
&\leq \max_i \{ ||\mathbf b_i ||_2  \}.
\end{aligned}
\end{equation}
Thus, $\max_i \{ ||\mathbf b_i ||_2  \}$ is an upper bound on the optimal value of the problem.
Let $j \equiv \arg \max_i \{ ||\mathbf b_i ||_2  \}$, and let $\mathbf y \equiv \mathbf b_j/||\mathbf b_j||_2$.  Then, $\mathbf y$ is feasible for the optimization problem, because $||\mathbf y||_2 = 1$, and
\begin{equation}
\begin{aligned}
||\mathbf B\mathbf y||_\infty &= \max_i \{|\mathbf b_i^\text{T} \mathbf y|\} \\
&\geq |\mathbf b_j^{\text T}\mathbf y| \\
& = ||\mathbf b_j||_2 \\
&= \max_i \{ ||\mathbf b_i ||_2  \}.
\end{aligned}
\end{equation}
It follows that $||\mathbf B\mathbf y||_\infty = \max_i \{ ||\mathbf b_i ||_2  \}$.  Thus, $\max_i \{ ||\mathbf b_i ||_2  \}$ is the optimal value of the optimization problem, with $\mathbf y =\mathbf b_j/||\mathbf b_j||_2$ as the optimal solution.
A: The objective is a convex function, so the maximum will occur at some point $x^\star$ on the sphere $\|x\|_2 = 1$.   Let $m = \|B x^\star\|_\infty$, 
with $(B x^\star)_i = m$ for $i \in S_+$, $-m$ for $i \in S_-$, and $|(B x^\star)_i| < m$ for all other $i$. 
If $y \perp x^\star$, then we must have $(B y)_i = 0$ for $i \in S_+ \cup S_-$,
otherwise we could increase $\|B x\|_\infty$ by moving slightly from $x^\star$ in the direction $y$ or $-y$.  But this implies that row $i$ of $B$ is a scalar multiple of $(x^\star)^T$.  Thus the only candidates for $x^\star$ are the transposes of the normalized rows of $B$.  The maximum is
obtained for the row $R$ of $B$ that maximizes $\|R\|_\infty/\|R\|_2$. 
