1
$\begingroup$

I have the following inner-product minimization problem:

$$ \min_{\Delta \in B_p^\epsilon} \quad\langle\Delta, w\rangle$$

where $B_p^\epsilon = \{\Delta \in \mathbb{R}^n : \| \Delta \|_p \le \epsilon\}$.

The paper I am currently reading, assumes this to be equivalent with the dual norm of $w$ scaled by $\epsilon$:

$$ \min_{\Delta \in B_p^\epsilon} \quad\langle\Delta, w\rangle = -\epsilon \| w \|_p^*$$

The dual norm is defined as $\sup \{ \langle x, w\rangle \mid \|x\|_p \le 1\}$. Intuitively the identity seems true, however I am failing to proof it.

I understand the case outlined in this post, where we have the minimization over vectors norm-bound to 1. There, the equivalence is easy to see. However, I can't formally figure out, how to translate this argument to a minimization over vectors with arbitrary norm-bounds.

I feel, I am really missing some easy argument. I tried to think about $$ \min_{\Delta \in B_p^\epsilon} \|\Delta\|_p \left\langle\frac{\Delta}{\|\Delta\|_p}, w \right\rangle$$ but thought the optimal solution is not required to have norm $\epsilon$ (even though the inner-product and the set are convex) and hence, the prefactors wouldn't necessarily match. I feel quite stuck in my reasoning and would really appreciate some help.

$\endgroup$
2

1 Answer 1

2
$\begingroup$

Since $\|ax\|_p=|a|\|x\|_p$, $B^{\epsilon}_p =\{x: \|x\|_p\leq\epsilon\}=\{x:\|\frac{x}{\epsilon}\|_p\leq 1\} = \{\epsilon u: \|u\|\leq 1\}= \epsilon B^{1}_p$, we can rewrite the problem

$$\min\limits_{\Delta\in B^{\epsilon}_p}\langle\Delta, w\rangle = \min\limits_{u\in B^{1}_p}\epsilon\langle u,w\rangle = -\epsilon\max\limits_{u\in B^1_p}\langle u,-w\rangle = -\epsilon \|w\|_*$$ using the fact that $\|w\|_*=\|-w\|_*$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .