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

Improve this question
$\endgroup$
11
  • 1
    $\begingroup$ A constant function $f\equiv M$ or $f\equiv -M$ will do the job? $\endgroup$
    – jf328
    Aug 10, 2015 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, 2015 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, 2015 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, 2015 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, 2015 at 14:15

1 Answer 1

Reset to default
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}$.

Improve this answer
$\endgroup$
2
  • $\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, 2015 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, 2015 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.