0
$\begingroup$

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}$

| cite | improve this question | |
$\endgroup$
  • 1
    $\begingroup$ A constant function $f\equiv M$ or $f\equiv -M$ will do the job? $\endgroup$ – jf328 Aug 10 '15 at 8:06
  • $\begingroup$ This would be more straightforward if you knew the entries of w were nonnegative. Is that information available? $\endgroup$ – hardmath Aug 10 '15 at 11:58
  • $\begingroup$ I have edited the question. The values of $\mathbf{w}$ are unknown, but all the values of $\mathbf{x}_i$ are known. $\endgroup$ – user570593 Aug 10 '15 at 12:34
  • $\begingroup$ 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$? $\endgroup$ – Wolfgang Bangerth Aug 10 '15 at 13:56
  • $\begingroup$ $\mathbf{w}\in \mathbb{R}^3$ is correct. $\max$ operation takes the elementwise maximum as shown in the example. $\endgroup$ – user570593 Aug 10 '15 at 14:15
2
$\begingroup$

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}$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – user570593 Aug 11 '15 at 12:32
  • $\begingroup$ 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. $\endgroup$ – hardmath Aug 11 '15 at 12:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.