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

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} = f(\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.

All the values of $\mathbf{x}_i, \;, i=1, \dots, N$ are known. But $\mathbf{w}$ is unknown.

Is it possible to have $f$ as a function only on $\mathbf{x}_i$?

Example: $\mathbf{x}_1 = \begin{pmatrix}-10\\1\\3\end{pmatrix}, \; \mathbf{x}_2 = \begin{pmatrix}5\\-3\\-5\end{pmatrix} \implies \mathbf{z} = \max\mathbf{x}_i = \begin{pmatrix}5\\1\\3\end{pmatrix}$

• A constant function $f\equiv M$ or $f\equiv -M$ will do the job? – jf328 Aug 10 '15 at 8:06
• This would be more straightforward if you knew the entries of w were nonnegative. Is that information available? – hardmath Aug 10 '15 at 11:58
• I have edited the question. The values of $\mathbf{w}$ are unknown, but all the values of $\mathbf{x}_i$ are known. – user570593 Aug 10 '15 at 12:34
• It's not clear to me what the $max$ operation is taken over. The elements of the vector $\mathbf w\in {\mathbb R}^3$? The indices $i=1,\ldots,N$? – Wolfgang Bangerth Aug 10 '15 at 13:56
• $\mathbf{w}\in \mathbb{R}^3$ is correct. $\max$ operation takes the elementwise maximum as shown in the example. – user570593 Aug 10 '15 at 14:15

As the OP is aware, when $\mathbf{w}$ is nonnegative, an upper bound of the required type can be obtained by taking $\mathbf{z}$ to be the componentwise maximum of the various $\mathbf{x}_i$.

However a simple example shows that no choice of $\mathbf{z}$ is possible when $\mathbf{w}$ is allowed to have a negative entry. Consider the vectors:

$$\mathbf{x}_1 = (1,0,0)^T \; \text{ and } \; \mathbf{x}_2 = (-1,0,0)^T$$

Then whatever choice of $\mathbf{z} = (z_1,z_2,z_3)^T$ is made, there exists $\mathbf{w} = (w_1,w_2,w_3)^T$ for which the inequality $\max \mathbf{w}^T\mathbf{x}_i \leq \mathbf{w}^T \mathbf{z}$ fails.

Specifically, if $z_1 \le 0$, the choice $\mathbf{w} = (1,0,0)^T$ yields $\max \mathbf{w}^T \mathbf{x}_i = 1$, and $\mathbf{w}^T \mathbf{z} = z_1 \not \ge 1$.

On the other hand, if $z_1 \ge 0$, the choice $\mathbf{w} = (-1,0,0)^T$ yields $\max \mathbf{w}^T \mathbf{x}_i = 1$, and $\mathbf{w}^T \mathbf{z} = -z_1 \not \ge 1$.

Therefore no choice of $\mathbf{z}$ is satisfactory for all $\mathbf{w}$.

• Thanks for your answer. But I think if we split w into two parts, one contains non-negatives, and the other contains non-positives, may be we can get a solution. – user570593 Aug 11 '15 at 12:32
• As you have posed the problem, the choice of $\mathbf{z}$ cannot depend on $\mathbf{w}$ in any way. Indeed $\mathbf{z}$ is restricted to being a componentwise function $f$ of the entries of various $\mathbf{x}_i$, and the upper bound is required to hold for all $\mathbf{w}$. My example shows this is impossible. – hardmath Aug 11 '15 at 12:46