How to show that the following equality holds for infimum?

Question

In one of the book I read that the following equality holds

$$\inf_{\|u\|_2\leq 1} a^TP_iu=-\|a^TP_i\|_2.$$ How can we prove this equality? Any help in this regard will be much appreciated. Thanks in advance.

Answer 1

This is because of the definition of the dual norm. Let $\|\cdot\|$ be a norm on $\mathbb{R}^n$. Then its dual norm is defined as

$$ \|x\|_{*} = \sup_{\|u\|\leq 1}\langle x, u\rangle. $$

The dual norm is also a norm on $\mathbb{R}^n$. If $\|\cdot\|$ is the Euclidean norm, its dual coincides with it, that is, for all $x\in\mathbb{R}^n$

$$ \|x\|_2 = \|x\|_{2,*} = \sup_{\|u\|_2\leq 1}x^\top u = -\inf_{\|u\|_2\leq 1} -x^\top u. $$

In your case,

\begin{align} \inf_{\|u\|_2 \leq 1} a^\top P_i u {}={}& -\sup_{\|u\|_2 \leq 1} -(P_i^\top a)^\top u \\ {}={}& -\|-P_i^\top a\|_2 \\ {}={}& - \|P_i^\top a\|_2. \end{align}

I'm not sure why you have $\|-a^\top P_i\|_2$, but I assumed here that $a,u\in\mathbb{R}^n$, $P_i\in\mathbb{R}^{n\times n}$.

Answer 2

Here is a solution that does not necessitate to use the dual norm.

First of all, let us slightly simplify the issue ; in your expression :

$$\inf_{\|u\|_2\leq 1} a^TP_iu=-\|a^TP_i\|_2,$$

let us set $V=P_i^Ta$. We have thus to prove that :

$$\inf_{\|u\|_2\leq 1} \underbrace{V^Tu}_{\langle V,u \rangle}=-\|V\|_2.$$

Cauchy-Schwarz inequality says that

$$|\langle V,u \rangle| \leq \|V \|_2 \|u \|_2 \ \text{with equality iff} \ V=\lambda u$$

Or equivalently :

$$-\|V \|_2 \|u \|_2 \color{red}{\leq} \langle V,u \rangle \leq \|V \|_2 \|u \|_2 \ \text{with equality iff} \ V=\lambda u$$

(we will use only the left inequality).

Let us now consider $u=-\dfrac{V}{\|V\|_2}$ ; its norm is $1$ and it is proportional to $V$, thus the minimum is reached, and we obtain the looked for result :

$$-\|V \|_2 \times 1 \color{red}{=} \inf_{\|u\|_2\leq 1} \langle V,u \rangle.$$