Rappresentazione interna di poliedri

L’obbiettivo è il teorema di Wyel, rappresentare un poliedro in forma interna, ovvero come una combinazione particolare di un insieme finito di oggetti, rispetto alla definizione esterna tramite sistema di disequazioni Def.

Def cono §

Un insieme non vuoto $C\subseteq {\mathbb{R}}^n$ è detto cono se $\forall x\in C$ $\lambda x\in C$ per tutti $\lambda \ge 0$. Geometricamente, dato un punti diverso dall’origine, contiene tutta la semiretta in quella direzione.

Def cono convesso §

Un insieme $C\subseteq {\mathbb{R}}^n$ è detto cono convesso se presi qualunque due punti $x,y\in C$ la loro combinazione conica appartiene a $C$.

Oss §

Ovviamente questa definizione è equivalente a quella di insieme convesso e cono allo stesso tempo.

Teorema di Weyl §

Dati due insieme di punti in ${\mathbb{R}}^n$, $V=\{v1,...,v_k\}$ e $D=\{d_1,...,d_q\}$ l’insieme $conv(V)+cone(D)$ è un poliedro.

Dim §

L’idea è vedere il tutto come un insieme di disequazioni e vincoli, quindi un poliedro. Basta eliminare le variabili $\lambda$ e $\mu$ con una proiezione, ed ottenere così la rappresentazione esterna (implicita) del poliedro. Se $V=\varnothing$ abbiamo che $conv(V)=\varnothing$ e quindi anche $conv(V)+cone(D)$ è l’insieme vuoto, che è un poliedro. Se invece $V$ non è vuoto abbiamo che i punti $x$ di $conv(V)+cone(D)$ sono del tipo $x=w+z$ con $w\in conv(V)$ e $z\in cone(D)$. Ricordando la definizione di involucro convesso e quello di involucro conico abbiamo quindi che $x$ appartiene a $conv(V)+cone(D)$ se e solo se esistono $\lambda \in {\mathbb{R}}^k$ e $\mu \in {\mathbb{R}}^q$ tali che:

$$x=z+w=\sum _{i=1}^k{\lambda }_i{v}_i+\sum _{j=1}^q{\mu }_j{d}_j$$

dove per i coefficienti devono valere:

$$\sum _i{\lambda }_i=1,{\lambda }_i\ge 0\forall i$$ $${\mu }_j\ge 0\forall j$$

ricordando che ogni vincolo di uguaglianza può essere “spezzato” in due vincoli di disuguaglianza, otteniamo il tutto come un sistema di disequazioni. In altre parole, $conv(V)+cone(D)$ è la proiezione su ${\mathbb{R}}^n$ del poliedro $Q$ definito dal sistema precedente, ed è quindi un poliedro.

Vogliamo ora dimostrare il contrario, meno banale, ovvero che ogni poliedro si può scrivere in quella forma. Cominciamo con poliedri limitati.

Teorema §

Sia $P$ un poliedro non vuoto e limitato. Allora detto $V$ l’insieme dei suoi vertici, possiamo scrivere:

$$P=conv(V)=conv(V)+cone(0)$$

Dim §

Se $x\in P$ è un vertice, allora è banalmente vero. Supponiamo ora che $x\notin V$. Dato che non è un vertice, e $P$ è limitato, non contiene rette, quindi possiamo applicare Lemma, e trovare due punti $x_1,x_2\in P$ su una retta tali che in questi punti sono attivi tutti i vincoli di $x$ più almeno un altro, ed inoltre posso esprimere $x=\alpha x_1+(1-\alpha )x_2$ con $\alpha \in (0,1)$ (notiamo che $x_1\ne x_2\ne x$). Se $x_1$ e $x_2$ sono vertici, ho fatto, altrimenti reitero il processo, sono sicuro che in un numero finito di passi arrivo a dei vertici. $\square$

Abbiamo usato la limitatezza, che ci permette di trovare due punti dove la retta “sbatte”. Nel caso di poliedri non limitati, ma che comunque non contengono rette, in generale potrò trovare solo un punto di collisione. Vediamo come trattare questo caso tramite le direzioni di recessione.

Def direzione di recessione §

Sia dato un poliedro non vuoto $P$ e un suo punto $x$. Un vettore $d\in {\mathbb{R}}^n$ è detto direzione di recessione se $x+\lambda d$ appartiene a $P$ per ogni $\lambda$ non negegativo. In altre parole se la semiretta di origine $x$ e direzione $d$ è tutta contenuta in P.

Oss §

Le direzioni di recfessione (che, come vedremo subito, non dipendono dal punto $x$ rappresentano quindi le direzioni in cui ci si può “muovere all’infinito” rimanendo dentro l’insieme $P$.

Teorema §

Estendiamo il teorema precedente, ovvero la rappresentazione interna di poliedri non vuoti e finiti al caso non limitato, ma sempre senza rette: è possibile che una semiretta sia contenuta nel poliedro, questo fa cadere una parte della dimostrazione del teorema precedente.

Mostriamo il seguente fatto:

$$P=conv(v_1,\dots ,v_p)+rec(P)$$

Dim §

Siccome $P$ è non vuoto, prendiamo $x\in P$. Se è un vertice ho finito, supponiamo non lo sia. Sempre per il lemma precedente, posso considerare una retta dove tutti i vincoli attivi rimangono tali, e siccome per ipotesi $P$ non contiene rette, almeno da uno dei due versi la rette deve “sbattere”, ovvero attivare altri vincoli. Se trovo sempre due punti di collisione, reitero fino a giungere a dei vertici. Nel caso di un lato illimitato, posso espremire $x$ come:

$$x=x_1+\lambda d,\lambda \ge 0$$

dove $x_1$ è il punto di collisione:

$$x_1=x-\overline{\lambda }d$$

Quindi posso esprimere $x$ come un punto $x_1$ dove sono attivi tutti i vincoli di $x$ più almeno un altro ed una direzione di recessione, o come combinazione convessa di due punti $x_1$ e $x_2$ dove sono attivi più vincoli. Reitero fino ad avere solo vertici!. $\square$

Vogliamo far vedere come caratterizzare l’insieme delle direzioni di recessioni come una combinazione conica di un insieme finito di elementi $rec(P)=cone(d_1,\dots ,d_k)$.

Teo caratterizzazione algebrica delle dir. di recessione §

1. Tutte le direzioni di recessione di un poliedro $P=\{x|Ax\le b\}$ sono tutte e sole le soluzioni del sistema di disequazioni omogeno associato:

$$Ad\le 0$$

2. Le $d$ non dipendono dal punto scelto $x$.

Dim §

Supponiamo che la retta $x+\lambda d$ sia tutta contenuta in $P$ per ogni $\lambda \ge 0$. Allora vale:

$$A(x+\lambda d)=Ax+\lambda Ad\le b$$

Siccome per ipotesi $x\in P$, vale $Ax\le b$, il che implica banalmente $\lambda Ad\le 0$ $\forall \lambda$, quindi:

$$Ad\le 0$$

Viceversa, se vale la precedente cosa, segue che:

$$A(x+\lambda d)=Ax+\lambda Ad\le b$$

per i segni, quindi 1 è dimostrato. Il punto 2 segue banalmente, notando che $x$ scompare dalla caratterizzazione.

Oss §

L’insieme delle direzioni di recessioni $rec(P)$ è quindi un cono poliedrale. Facciamo vedere come un cono poliedrale si possa rappresentare come combinazione conica di un insieme finito di elementi.

Teorema §

Sia $C=\{x\in {\mathbb{R}}^n|Ax\le 0\}$ un cono poliedrale, allora vale la rappresentazione:

$$C=cone(d_1,\dots ,d_n)d_i\in C$$

si può esprimere come combinazione conica di un numero finito di suoi elementi, analogamente per i poliedri limitati e i veritici.

Dim §

Consideriamo la combinazione conica delle righe della matrice $A$:

$$cone(a_1,\dots a_n)=\{x\in {\mathbb{R}}^n|Dx\le 0\}$$

dove abbiamo usato il teorema che ci consente di rappresentare una combinazione conica come un cono poliedrale. Consideriamo le righe della nuova matrice $d_i$. Siccome $a_i\in cone(a_1,\dots ,a_n)$ deve valere:

$$d_j^T{a}_i=a_i^T{d}_j\le 0\forall j$$

quindi i vettori $d_i$ soddisfano il sistema $Ax\le 0$, sono contenuti in $C$, ovviamente anche la loro combinazione conica, quindi:

$$cone(d_i)\subseteq C$$

Mostriamo ora l’altro verso, per ottenere l’equivalenza degli insiemi. Sfruttiamo ancora il teorema di rappresentazione della combinazione convessa, stavolta dei vettori $d_i$:

$$cone(d_i)=\{x\in {\mathbb{R}}^n|Gx\le 0\}$$

per una certa matrice $G$. Siccome $d_i\in cone(d_i)$, deve valere:

$$g_j^T{d}_i=d_i^T{g}_j\le 0$$

quindi i vettori $g_j$ soddisfano il sistema $Dx\le 0$, che era proprio $cone(a_i)$. Ogni punto di $C$ soddisfa anche le disequazioni implicate da $A$ che sono proprio quelle di $G$, quindi:

$$C\subseteq cone(d_i)\square$$

Conclusione §

$$P=conv(v_1,\dots ,v_k)+rec(P)=conv(v_1,\dots ,v_k)+cone(d_1,\dots ,d_p)$$

$\square$