Dual norm definition: adding new constraints

Question

For some $c >0$ and $z \in \mathbb{R}^n$, the optimal value of

\begin{align} \begin{array}{cl} \sup_{x \in \mathbb{R}^n}& z^\top x \\\text{s.t.}& \lVert x \rVert \leq c \end{array} \end{align}

is equal to the dual norm $c \cdot \lVert z \rVert_{*}$.

I have a modification to this problem:

\begin{align} \begin{array}{cl} \sup_{x \in \mathbb{R}^n}& z^\top x \\\text{s.t.}& \lVert x \rVert \leq c \\ & \lVert x - t \rVert \leq c' \end{array} \end{align}

for some constant vector $t \in \mathbb{R}^n$ and a scalar $c' > 0$. I was wondering if this can be represented via dual norms as well. Is there a way I can get rid of the $\sup$, or does this problem not have a closed-form representation?

Answer 1

In case someone has a similar problem, I wanted to add an answer.

Let $\mathcal{S}_1 := \{x : \lVert x \rVert \leq c \}$ and $\mathcal{S}_2 : = \{x : \lVert x -t \rVert \leq c' \} $. So our problem is $$\sup_{x \in \mathcal{S}_1 \cap \mathcal{S}_2} z^\top x.$$ Any book covering Robust Optimization shows that such a problem is equivalent to $$ \inf_{z^1, z^2} \{\delta^{*} (z^1 \mid \mathcal{S}_1) + \delta^{*} (z^2 \mid \mathcal{S}_2) \ : \ z^1 + z^2 = z\},$$ where $\delta^{*}(\cdot | \mathcal{S})$ denotes the support function of $\mathcal{S}$, which is the convex conjugate of the indicator function taking value $1$ only for elements of $\mathcal{S}$. We can write $\delta^{*}(z \mid \mathcal{S}) = \sup_{x \in \mathcal{S}} z^\top x$ for any $z$ and $\mathcal{S}$ of suitable dimensions.

Now, notice that $\delta^{*} (z^1 \mid \mathcal{S}_1) = \sup_{x: \lVert x\rVert\leq c} x^\top z^1 = c\cdot\lVert z^1 \Vert_{*} $ by the definition of the dual norm $\lVert \cdot \rVert_{*}$.

Moreover, $\delta^{*} (z^2 \mid \mathcal{S}_2) = \sup_{x: \lVert x-t \rVert\leq c'} x^\top z^2 = t^\top z^2 + \sup_{x: \lVert x \rVert\leq c'} x^\top z^2 = t^\top z^2 + c' \cdot \lVert z^2\rVert_{*}$.

The problem is thus equivalent to $$ \inf_{z^1, z^2} \{t^\top z^2 + c\cdot\lVert z^1 \Vert_{*} + c' \cdot \lVert z^2\rVert_{*} \ : \ z^1 + z^2 = z\} $$ and substituting variables gives $$ \inf_{z^2} \{t^\top z' + c\cdot\lVert z - z' \Vert_{*} + c' \cdot \lVert z'\rVert_{*}\}.$$