Is $f(\mathbf{X}) = \sup_{\|\mathbf{y}\|\leq 1 } Tr(\mathbf{X \mathbf{y}\mathbf{y}}^T)$ an affine function?

Question

Suppose $f(\mathbf{X}) = \sup_{\|\mathbf{y}\|\leq 1 } Tr(\mathbf{X \mathbf{y}\mathbf{y}}^T)$ is the trace of a resulting matrix where $\mathbf{X} \in \mathbb{R^{n\times n}}$. It is easily can be shown that $Tr(\cdot)$ is a linear function for each $\mathbf{y}$. Can we deduce the function $f(\mathbf{X})$ is an affine function?

Answer 1

No, the supremum of a set of linear functions is very rarely affine. It's easy to find counterexamples in the case $n=2$.

Answer 2

I would like to answer this question using a general mathy (!) proof.

Suppose:$f(\mathbf{X}) = \sup_{\|\mathbf{y}\|\leq 1 } Tr(\mathbf{X \mathbf{y}\mathbf{y}}^T)$. For $f(\mathbf{X})$ to be an affine/a linear function, it should satisfy $f(a\mathbf{X}_{1}+b\mathbf{X}_{2}) = af(\mathbf{X}_{1})+bf(\mathbf{X}_{2})$ where $a,b \in \mathbb{R}$. Then, we have

\begin{align} f(a\mathbf{X}_{1}+b\mathbf{X}_{2}) &= \sup_{\|\mathbf{y}\|\leq 1 } Tr((a\mathbf{X}_{1}+b\mathbf{X}_{2})\mathbf{\mathbf{y}\mathbf{y}}^T)\\ &= \sup_{\|\mathbf{y}\|\leq 1} Tr(a\mathbf{X}_{1}\mathbf{\mathbf{y}\mathbf{y}}^T+b\mathbf{X}_{2}\mathbf{\mathbf{y}\mathbf{y}}^T) \\ &=\sup_{\|\mathbf{y}\|\leq 1 } \{a\; Tr(\mathbf{X}_{1}\mathbf{\mathbf{y}\mathbf{y}}^T)+b \; Tr(\mathbf{X}_{2}\mathbf{\mathbf{y}\mathbf{y}}^T)\} \\ &\leq\sup_{\|\mathbf{y}\|\leq 1} a\; Tr(\mathbf{X}_{1}\mathbf{\mathbf{y}\mathbf{y}}^T)+\sup_{\|\mathbf{y}\|\leq 1} b \; Tr(\mathbf{X}_{2}\mathbf{\mathbf{y}\mathbf{y}}^T) \\ &= |a|\sup_{\|\mathbf{y}\|\leq 1} Tr(\mathbf{X}_{1}\mathbf{\mathbf{y}\mathbf{y}}^T)+|b|\sup_{\|\mathbf{y}\|\leq 1} Tr(\mathbf{X}_{2}\mathbf{\mathbf{y}\mathbf{y}}^T), \end{align}

Hence:

$$f(a\mathbf{X}_{1}+b\mathbf{X}_{2}) = a\sup_{\|\mathbf{y}\|\leq 1} Tr(\mathbf{X}_{1}\mathbf{\mathbf{y}\mathbf{y}}^T)+b\sup_{\|\mathbf{y}\|\leq 1} Tr(\mathbf{X}_{2}\mathbf{\mathbf{y}\mathbf{y}}^T)$$

is a special case of above inequality and hence it is not generally an affine function.

---

Notice: $$\sup_{x} \{f(x)+g(x)\} \leq \sup_{x} f(x) + \sup_{x} g(x)$$ and $$\sup_{x} af(x) = a \sup_x {f(x)} \quad \forall a\in \mathbb{R}_{+}.$$