$\sup\limits_{\|w\|_p \leq 1} w^Ta = \|a\|_q$?

Question

Is $\sup\limits_{\|w\|_p \leq 1} w^Ta = \|a\|_q$ ? Can anyone tell me how to prove it use the Lagrangian multiplier method?

$\frac1q +\frac1p = 1 ,~p,q>1$.

Answer 1

To use Lagrange, notice that the cost is linear hence $\sup_{\|w\|_p \leq 1} w^Ta = \sup_{\|w\|_p = 1} w^Ta $, and since the feasible set is compact, we know that a solution exists.

To reduce the noise dues to roots, use the equivalent formulation: $\sup_{\|w\|_p = 1} w^Ta = \sup_{\|w\|_p^p = 1} w^Ta $.

To further reduce the noise, notice that $\sup_{\|w\|_p^p = 1} w^Ta = \sup_{\|w\|_p^p = 1} w^T|a|$, where $|a|=(|a_1|,...,|a_n|)$.

Hence we can assume that $a_k \ge 0$ (so we can take roots below without fussing).

Now notice that at a solution, $a_k$ and $w_k$ must have the same sign, and at a solution, Lagrange gives $a_k = \lambda p w_k^{p-1}$, and hence $\sum_k w_k a_k = (\lambda p) \sum_k w_k^p = \lambda p$.

In addition, since $w_k^p =( {a_k \over \lambda p})^q$, we see that $\|w\|_p^p=1=\sum_k w_k^p = {1 \over (\lambda p)^q} \sum_k a_k^q = {1 \over (\lambda p)^q} \|a\|_q^q $, and hence $\lambda p = \|a\|_q$.