Lipschitz continuity of $\sqrt{f}$ for $f(x) = \sup_{\alpha \in T} \sum_{i=1}^d \left(\sum_{j=1}^D \alpha_j x_{ij}\right)^2$

Question

Write $x = (x_{ij})_{1\leq i\leq d,1\leq j \leq D} \in \mathbb{R}^{dD}$ and define the function $f ~\colon~ \mathbb{R}^{dD} \to \mathbb R$ by $$f(x) = \sup_{\alpha \in T} \sum_{i=1}^d \left(\sum_{j=1}^D \alpha_j x_{ij}\right)^2,$$ where $\alpha = (\alpha_1,\ldots,\alpha_D) \in \mathbb{R}^D$ and $T$ is a finite subset of $\mathbb{R}^D$ with $\|\alpha\| = 1$ for all $\alpha \in T$. It is mentioned (without proof) in the proof of Theorem 5.9 of this monograph that $\sqrt{f}$ is $1$-Lipschitz continuous. May I know how can I justify the claimed Lipschitz continuity?

Answer 1

Using matrix notation, we can write $$\sum_{i=1}^d \left(\sum_{j=1}^D \alpha_j x_{ij}\right)^2 = \|X\alpha\|_2^2,$$ and thus, $$\sqrt{f(X)} = \sqrt{\sup_{\alpha \in T}\|X\alpha\|_2^2} = \sup_{\alpha \in T}\|X\alpha\|_2.$$ Now, note that for any $\alpha \in T$ and any $X,Y \in \mathbb{R}^{dD}$, we have \begin{align*}\sqrt{f(X)} &= \sup_{\alpha \in T}\|X\alpha\|_2 \\ &= \sup_{\alpha \in T}\|Y\alpha+(X-Y)\alpha\|_2 \\ &\le \sup_{\alpha \in T}\|Y\alpha\|_2+\|(X-Y)\alpha\|_2 \\ &\le \sup_{\alpha \in T}\|Y\alpha\|_2+\|(X-Y)\|\|\alpha\|_2 \\ &= \sup_{\alpha \in T}\|Y\alpha\|_2+\|(X-Y)\|, \\ &= \|(X-Y)\| + \sup_{\alpha \in T}\|Y\alpha\|_2 \\ &= \|X-Y\| + \sqrt{f(Y)}. \end{align*} In a similar manner, we can show $\sqrt{f(Y)} \le \|X-Y\|+\sqrt{f(X)}$. Hence, $$\left|\sqrt{f(X)}-\sqrt{f(Y)}\right\| \le \|X-Y\|,$$ i.e. $\sqrt{f}$ is $1$-Lipschitz.