How to derive the supremum of a set over a unit ball

Question

Why is

sup$\{ u^T P^T x ~|~ \| u \|_2 \leq 1 \} = \| P^Tx \|_2$

where $P$ is a real $n\times n$ matrix and and $u$ and $x$ are $n\times 1$ vectors?

P.S. I have taken this equation from Stephen Boyd's optimization textbook which was a part of the proof of a theorem and left unproven.

Answer 1

If $\|u\|_2 \leq 1$, then by Cauchy-Schwartz$$ \langle u, P^Tx \rangle \leq \| u \|_2 \| P^T x \|_2 \leq \|P^Tx\|_2.$$ Therefore $\|P^Tx\|_2$ is an upper bound.

If $P^Tx =0$, then both sides are $0$, and we are done.

Otherwise let $u = \frac 1{\|P^Tx\|_2}P^Tx$, then $$ u^TP^Tx = \frac 1{\|P^Tx\|_2}x^TPP^Tx = \frac 1{\|P^Tx\|_2}\|P^Tx\|_2^2 = \|P^Tx\|_2, $$ therefore the upper bound is achieved, meaning that it is the least upper bound.

Answer 2

Recall the defintion of the dual $\|.\|_*$ of a norm $\|.\|$, namely

$$\|z\|_* := \sup\{\langle u, z\rangle | \|z\| \le 1\}.$$

and recognize $\sup\{\langle u, P^Tx\rangle | \|u\|_2 \le 1\} =: \|P^Tx\|_{2^*} = \|P^Tx\|_2$, since the euclidean 2-norm is self-dual.