Maximization of $\infty$-norm with $2$-norm constraint

Question

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}

Answer 1

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.

Answer 2

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