Combinazione conica

Combinazione conica §

Praticamente una combinazione lineare con coefficienti non negativi. La combinazione conica di un insieme di vettori viene indicata come:

$$Q=cone(v_1,v_2,\dots ,v_n)$$

Alcunche proprietà:

1. è un insieme non vuoto, infatti $0\in Q$
2. è un insieme convesso: facciamo vedere che $\lambda x_1+(1-\lambda )x_2\in Q$ $\forall x_1,x_2\in Q$ $\lambda \in [0,1]$. Siccome $x_1,x_2\in Q$ possono essere scritto come combinazione conica dei vettori generatori $v$:

$$x_1={\alpha }^{T}v{x}_2={\beta }^{T}v\alpha ,\beta \ge 0$$

Per far vedere che anche combinazioni convesse sono in $Q$, basta far vedere che può essere scritto come combinazione conica dei vettori generatori. Usiamo la notazione classica dei prodotti scalari: $v^{t}u=⟨v,u⟩$

$$\lambda ⟨\alpha ,v⟩+(1-\lambda )⟨\beta ,v⟩$$ $$⟨\lambda \alpha ,v⟩+⟨(1-\lambda )\beta ,v⟩=⟨\lambda \alpha +(1-\lambda )\beta ,v⟩$$

ovviamente $\lambda \alpha +(1-\lambda )\beta \ge 0$. $QED$

Teorema §

La definizione di combinazione conica può essere interpretata come un poliedro, con $\lambda$ come variabili. Vale la rappresentazione:

$$cone(v_1,\dots ,v_n)=\{x\in {\mathbb{R}}^n|Ax\le 0\}$$

per una certa matrice $A$.

Dim §

è abbastanza naturale, si procede con l’Eliminazione di Fourier-Motzkin e si arriva ad un sistema di disequazioni omogeneo in $\lambda$. Le $x$ (che fanno il ruole delle $b$ costanti) si cancellano, dovendo trasformare le equazioni in due disequazioni con segno opposto:

$${\lambda }^{T}v=x\{\begin{array}{l}{\lambda }^T\le x\\ -{\lambda }^{T}x\le -x\end{array}$$