3
$\begingroup$

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?

$\endgroup$
3
  • 1
    $\begingroup$ I think you can express it as a conic problem using the cone for the given norm, repeat the derivation of dual for conic problems docs.mosek.com/modeling-cookbook/duality.html and get the dual problem in terms of dual cones, which are cones for the dual norm. You will get some optimization problem with dual norms but not something explicit. $\endgroup$ Aug 1, 2023 at 11:09
  • $\begingroup$ @MichalAdamaszek oh, I also just ended up in Robust Optimization literature and I realized that if I can model this intersection as a single cone then I can use support functions. Would you recommend trying to model the intersection of these norms as a single cone, or treat them as separate cones? $\endgroup$ Aug 1, 2023 at 14:43
  • $\begingroup$ Fixed it. I will post an edit tomorrow. $\endgroup$ Aug 1, 2023 at 20:53

1 Answer 1

1
$\begingroup$

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_{*}\}.$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.