Lemma del punto interno (teoria poliedrale)
Salve a tutti!
Sto studiando per un esame di ottimizzazione da queste slides gratuite e liberamente fruibili (che tra l'altro consiglio vivamente) http://bayanbox.ir/view/767137756097942 ... Krumke.pdf e mi è sorto un "dubbio esistenziale" al lemma 3.18 di suddette slide che, per comodità, riporto per intero (fra parentesi metto varie parafrasi ed interpretazioni personali di tale teorema):
Lemma 3.18 Sia [tex]P = P\left(A,b\right)[/tex] un poliedro. Allora l'insieme dei punti interni di [tex]P[/tex] (cioé quei punti [tex]x[/tex] tali per cui [tex]Ax < b[/tex]) è non vuoto.
Dimostrazione
Sia [tex]M=\left\{1,\ldots,m\right\}[/tex] l'insieme delle righe di [tex]A[/tex], sia [tex]I = \mathit{eq}\left(P\right) = \left\{i \in M \mid \forall x \in P \left( A_{i,\cdot}\,x = b_{i} \right) \right\}[/tex] e sia [tex]J = M \backslash I[/tex]. Se [tex]I = M[/tex] allora [tex]P[/tex] è un sottospazio affine e non possiede alcuna faccia propria: ogni punto di [tex]P[/tex] è un punto interno.
Se [tex]I \subset M[/tex] allora, per ogni [tex]j \in J[/tex], è possibile trovare [tex]x^j \in P[/tex] tale per cui [tex]Ax^j \leq b[/tex] e [tex]A_{j,\cdot}x^j < b_j[/tex]. Siccome [tex]P[/tex] è un insieme convesso il punto [tex]y = \frac{1}{\left|J\right|} \sum_{j \in J} x^j[/tex] è contenuto in P e si ha [tex]A_{j,\cdot}y < b_j[/tex] e [tex]\forall i \in I \left( A_{i,\cdot}y = b_i \right)[/tex] e quindi [tex]\mathit{eq}\left(\left\{y\right\}\right) = \mathit{eq}\left(P\right)[/tex] (i punti degli insiemi [tex]\left\{y\right\}[/tex] e [tex]P[/tex] soddisfano per uguaglianza le stesse disequazioni) e si è quindi trovati un punto interno a [tex]P[/tex] [tex]\blacksquare[/tex]
Il mio dubbio è il seguente: invece di definirsi questo punto [tex]y = \frac{1}{\left|J\right|} \sum_{j \in J} x^j[/tex] non si potevano usare direttamente i punti [tex]x^j[/tex] visto che, per definizione di [tex]\mathit{eq}\left(\cdot\right)[/tex], tutti le disequazioni nelle righe di [tex]I[/tex] vengono soddisfatte per uguaglianza? C'è un motivo per cui si definisce questo nuovo punto data dalla combinazione convessa dei vari [tex]x^j[/tex] oppure è una cosa effettivamente tralasciabile? (L'unica spiegazione che mi è venuta in mente proprio mentre sto scrivendo questo post è che magari questa cosa è stata fatta proprio per far vedere che è sempre possibile trovare un punto interno non considerato precedentemente interno al poliedro e che quindi l'insieme [tex]P[/tex] è un insieme continuo)
Grazie in anticipo per le risposte.
Sto studiando per un esame di ottimizzazione da queste slides gratuite e liberamente fruibili (che tra l'altro consiglio vivamente) http://bayanbox.ir/view/767137756097942 ... Krumke.pdf e mi è sorto un "dubbio esistenziale" al lemma 3.18 di suddette slide che, per comodità, riporto per intero (fra parentesi metto varie parafrasi ed interpretazioni personali di tale teorema):
Lemma 3.18 Sia [tex]P = P\left(A,b\right)[/tex] un poliedro. Allora l'insieme dei punti interni di [tex]P[/tex] (cioé quei punti [tex]x[/tex] tali per cui [tex]Ax < b[/tex]) è non vuoto.
Dimostrazione
Sia [tex]M=\left\{1,\ldots,m\right\}[/tex] l'insieme delle righe di [tex]A[/tex], sia [tex]I = \mathit{eq}\left(P\right) = \left\{i \in M \mid \forall x \in P \left( A_{i,\cdot}\,x = b_{i} \right) \right\}[/tex] e sia [tex]J = M \backslash I[/tex]. Se [tex]I = M[/tex] allora [tex]P[/tex] è un sottospazio affine e non possiede alcuna faccia propria: ogni punto di [tex]P[/tex] è un punto interno.
Se [tex]I \subset M[/tex] allora, per ogni [tex]j \in J[/tex], è possibile trovare [tex]x^j \in P[/tex] tale per cui [tex]Ax^j \leq b[/tex] e [tex]A_{j,\cdot}x^j < b_j[/tex]. Siccome [tex]P[/tex] è un insieme convesso il punto [tex]y = \frac{1}{\left|J\right|} \sum_{j \in J} x^j[/tex] è contenuto in P e si ha [tex]A_{j,\cdot}y < b_j[/tex] e [tex]\forall i \in I \left( A_{i,\cdot}y = b_i \right)[/tex] e quindi [tex]\mathit{eq}\left(\left\{y\right\}\right) = \mathit{eq}\left(P\right)[/tex] (i punti degli insiemi [tex]\left\{y\right\}[/tex] e [tex]P[/tex] soddisfano per uguaglianza le stesse disequazioni) e si è quindi trovati un punto interno a [tex]P[/tex] [tex]\blacksquare[/tex]
Il mio dubbio è il seguente: invece di definirsi questo punto [tex]y = \frac{1}{\left|J\right|} \sum_{j \in J} x^j[/tex] non si potevano usare direttamente i punti [tex]x^j[/tex] visto che, per definizione di [tex]\mathit{eq}\left(\cdot\right)[/tex], tutti le disequazioni nelle righe di [tex]I[/tex] vengono soddisfatte per uguaglianza? C'è un motivo per cui si definisce questo nuovo punto data dalla combinazione convessa dei vari [tex]x^j[/tex] oppure è una cosa effettivamente tralasciabile? (L'unica spiegazione che mi è venuta in mente proprio mentre sto scrivendo questo post è che magari questa cosa è stata fatta proprio per far vedere che è sempre possibile trovare un punto interno non considerato precedentemente interno al poliedro e che quindi l'insieme [tex]P[/tex] è un insieme continuo)
Grazie in anticipo per le risposte.
Risposte
$P:=\{(x,y)\in\mathbb R^2 : x\geq 0, y\geq 0, x+y\leq 1\}$. $x^1=(1,0)$, $x^2=(0,1)$, $x^3=(0,0)$: sono fatti come chiede la dimostrazione, ma nessuno dei tre è un punto interno a $P$.
"coffee":
$P:=\{(x,y)\in\mathbb R^2 : x\geq 0, y\geq 0, x+y\leq 1\}$. $x^1=(1,0)$, $x^2=(0,1)$, $x^3=(0,0)$: sono fatti come chiede la dimostrazione, ma nessuno dei tre è un punto interno a $P$.
Grazie mille.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo