Given $n$ sets of linear constraints $\Theta_1, \cdots, \Theta_n$ which are over $\vec{x}_1, \cdots, \vec{x}_n$ respectively where $\vec{x}_i$ and $\vec{x}_j$ are pairwise disjoint, and $W= \begin{bmatrix} w_1[\vec{x}_1]\\ \vdots\\ w_n[\vec{x}_n]\\ \end{bmatrix}$ where $w_i$ is an $m$-dim row vector each entry of which is a linear function over $\vec{x}_i$. Given $d\in \mathbb{R}^m$, we define $\max Wd= \begin{bmatrix} \max_{\vec{x}_1 \in \Theta_1} w_1[\vec{x}_1] \cdot d\\ \vdots\\ \max_{\vec{x}_n \in \Theta_n} w_n[\vec{x}_n] \cdot d\\ \end{bmatrix}$

Clearly $A=\{\max Wd\mid d\in \mathbb{R}^m\}$ is not a linear space (see example below).

The question is to compute a basis of the linear space spanned by $A$?

Eample: Let $W=[ x\ y]$ and $\Theta_1=\{0\leq x\leq 1, 0\leq y\leq 1, x+y=1\}$. (In this case $n=1$ and $m=2$). Then

  • for $d=[1\ 0]^T$, we have $\max Wd= [1]$;
  • for $d=[ 0\ 1]^T$, we have $\max Wd= [1]$;
  • for $d=[1\ 1]^T$, we have $\max Wd= [1]$.

In this case $A=\mathbb{R}$.

The motivation of the problem is from geometry and an interesting feature here is that the optimization is involved which makes the problem unusual.


Your Answer

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

Browse other questions tagged or ask your own question.