How can I prove this theorem regarding the sub-gradient of p-norm using Holder Inequality?

Question

Given, $f(x)=||x||_p = \max_{||z||_q \leq 1} z^T x$ and Holder inequality that $x^Ty\leq ||x||_p||y||_q$

How can I prove

$\partial f(x) = \operatorname{argmax}_{||z||_q \leq 1} z^T x$

Answer 1

You want to show $$\partial f(x) = \{z \mid \|z\|_q \le 1 \text{ and } z^\top x = \|x\|_p\}.$$

Let $z \in \partial f(x)$ be given. Then, $$f(y) \ge f(x) + z^\top (y - x)$$ holds for all $y$. Taking $y = 0$ and $y = 2 \, x$ we find $$\|x\|_p = z^\top x.$$ Hence, the above inequality implies $$\|y\|_p \ge z^\top y$$ for all $y$ and this gives $\|z\|_q \le 1$.

The other inclusion "$\supset$" is straightforward to show.

By the way, the same argument works in any normed space (instead of $\|\cdot\|_q$ you have to use the dual norm).

Answer 2

This is the kind of problem you pull out the Danskin-Bertsekas theorem for subdifferentials for.

Theorem. Let $\phi: \mathbb{R}^m \times \mathbb{R}^n \rightarrow (-\infty, +\infty]$ be a function and $X$ be a nonempty compact subset of $\mathbb{R}^n$. Assume further that for every $x \in X$, $\phi(., x) : \mathbb{R}^m \rightarrow (-\infty, +\infty]$ is a closed proper convex function. Consider the function $f: \mathbb{R}^n \rightarrow (-\infty, +\infty]$ defined by $$ f(z) := \underset{x \in X}{\text{sup }}\phi(z, x). $$ If $f$ is finite somewhere, then it is a closed proper convex function. Furthermore, if $intdom\;f \ne \emptyset$ and $\phi$ is continuous on $intdom\;f \times X$, then for every $z \in intdom\;f $ the subdifferential of $f$ at $z$ is given by \begin{eqnarray} \partial f(z) = \text{conv}\{\partial \phi(z, {x}) \mid {x} \in \widehat{X}(z)\}, \end{eqnarray} where $\widehat{X}(z) := \{x \in X \mid \phi(z, x) = f(z)\}.$

Now, for your specific problem, take $m=n$, $\phi(z, x) \equiv z^Tx$, and $X = \ell_q \text{ unit-ball}$ on $\mathbb R^n$, where $p$ is the harmonic-conjugate of $q$ (i.e $1/p + 1/q = 1$), so that $\|z\|_p = \max_{x \in X}\phi(z, x)$. One computes

• $\partial_z \phi(z, x) = x$ forall $x,z \in \mathbb R^n$.
• $\widehat{X}(z) = \{x \in X \mid \phi(z,x) = f(z)\} = \{x \in X \mid z^Tx = \|x\|_p\}$. Note that $\widehat{X}(z)$ is convex.

Thus, for every $z \in \mathbb R^n$, one has $$ \begin{split} \partial \|z\|_q &= \partial f(z) = \text{conv}\{\partial_z \phi(z, {x}) \mid{x} \in \widehat{X}(z)\} = \text{conv}\{x \mid x \in \widehat{X}(z)\}\\ & = \text{conv}(\widehat{X}(z)) = \widehat{X}(z) = \{x \in X \mid z^Tx = \|z\|_q\}. \end{split} $$