what is the upper bound of $\max \mathbf{w}^T\mathbf{x}_i$

Question

I need to find an equation for the upper bound of $\max \mathbf{w}^T\mathbf{x}_i, \; i=1, \dots N$.

where $\mathbf{w}$ and $\mathbf{x}_i$ are two vectors.

I need to find a function $f$ which holds the following inequality.

$\max \mathbf{w}^T\mathbf{x}_i \leq \mathbf{w}^T \mathbf{z}$

where $\mathbf{z}$ is a function which operates on $\mathbf{x}_i, i=1, \dots, N$

e.g

Let $\mathbf{x}_1 = \begin{pmatrix}x_{11}\\x_{12}\\x_{13}\end{pmatrix}, \; \dots, \mathbf{x}_N = \begin{pmatrix}x_{N1}\\x_{N2}\\x_{N3}\end{pmatrix}$

$\mathbf{z} = \begin{pmatrix}f(x_{11}, \dots, x_{N1})\\f(x_{12}, \dots, x_{N2})\\f(x_{13}, \dots, x_{N3})\end{pmatrix}$

for example f can be a $\max$ or $\min$ function.

Answer 1

Use Cauchy-Schwarz: $w^T x_i \leq ||w|| \cdot ||x_i||$

First, take the max over the right-hand side: $w^Tx_i \leq ||w|| \max_i ||x_i||$. Since this holds for all $i$ on the left-hand side, take $\max_i$ on that side, as well. So:

$$ \max_i w^T x_i \leq ||w|| \max_i ||x_i|| $$

Then let $z = f(x_1, \ldots, x_N) = \frac{\max{||x_i||}}{||w||} w$.