# How to compute the basis

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.