Maximize $b^Tx$ subject to $x \in C(a) := \{x \in \mathbb R^p | \|a+x\|_2 \le r,\;\|x\|_\infty \le \epsilon\}$

Question

Let $r,\epsilon > 0$ and $a, b \in \mathbb R^p$ with $\|a\|_2 \le r$. Define the set $C(a) := \{x \in \mathbb R^p | \|x+a\|_2 \le r,\;\|x\|_\infty \le \epsilon\}$. Note that $C(a)$ is non-empty (it contains the origin $x=0$, at least).

Question

• (A) What is an analytic solution to the problem $\sup_{x \in C(a)} b^Tx$ ?
• (B) Same question with $\|a\|_2 = r$ and $C(a) := \{x \in \mathbb R^p | \|x+a\|_2 = r,\;\|x\|_\infty \le \epsilon\}$

Answer 1

The general answer will be very complicated. But here is a special case. You can see $C(a)$ as the intersection of two balls: $X=B_{\|\cdot\|_2}(-a, r)$ and $Y=B_{\|\cdot\|_\infty}(0, \epsilon)$. If $Y\subseteq X$ then we can forget about $X$. For every $1\leq i\leq d$ let $s_i\in\{-1,0,1\}$ denote the sign of $a_i$. Then $x=(s_1\epsilon,s_2\epsilon,...,s_d\epsilon)$ is optimal.