How can I prove this theorem regarding the sub-gradient of p-norm using Holder Inequality? 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$
 A: 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).
A: 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}
$$
