Lemma di Farkas¶

L'Enunciato¶

Dati una matrice $A$ di dimensioni $m \times n$ e un vettore $b \in \mathbb{R}^m$, esattamente uno dei seguenti due sistemi ha soluzione:

Sistema Primale: $Ax = b$ con $x \geq 0$
Sistema Alternativo: $A^T y \geq 0$ con $b^T y < 0$

Cosa Significa¶

Il Lemma di Farkas è un "teorema dell'alternativa". Ti dice che in certi scenari matematici, o succede questo o succede quello, ma mai entrambi e mai nessuno dei due. È come un interruttore: acceso o spento.

Geometricamente, è ancora più intuitivo. Immagina che le colonne della matrice $A$ siano dei vettori che partono dall'origine. Tutte le loro possibili combinazioni lineari positive ($x \geq 0$) formano un cono. Il sistema 1 chiede: "Il vettore $b$ si trova dentro questo cono?"

Se la risposta è SÌ, allora esiste una $x \geq 0$ tale che $Ax = b$. Se la risposta è NO, allora il Lemma di Farkas garantisce che esiste un piano (un iperpiano) che passa per l'origine e separa $b$ dal cono. Questo piano è definito dal vettore normale $y$ del sistema 2. Il sistema 2 dice essenzialmente: "Esiste una direzione $y$ che fa un angolo acuto (o retto) con tutti i vettori di $A$ ($A^T y \geq 0$), ma un angolo ottuso con $b$ ($b^T y < 0$)?"

Un Po' di Storia (e di Dramma)¶

Gyula Farkas non si svegliò una mattina del 1902 decidendo di fondare la Ricerca Operativa. In realtà, lui era un fisico, ossessionato dall'equilibrio.

Immaginate la scena: siamo all'inizio del XX secolo. La fisica classica è potente, ma c'è un problema irrisolto. Sappiamo come trattare le equazioni (uguaglianze), ma il mondo reale è pieno di disuguaglianze. Una corda può solo tirare, non spingere. Un tavolo può sostenere un oggetto, ma non incollarlo a sé. Questi sono vincoli unilaterali. Farkas stava cercando di generalizzare il principio dei lavori virtuali di Fourier e Lagrange per gestire questi "fastidiosi" vincoli di non-negatività.

Pubblicò il suo risultato, "Über die Theorie der einfachen Ungleichungen", e... il mondo accademico sostanzialmente lo ignorò. O meglio, lo vide come un tecnicismo di meccanica analitica.

Il vero colpo di scena arriva 50 anni dopo. Siamo nel dopoguerra. George Dantzig sta inventando il Metodo del Simpletto per risolvere problemi logistici militari. John von Neumann sta gettando le basi della Teoria dei Giochi. Improvvisamente, quel lemma oscuro di un fisico ungherese diventa la chiave di volta di tutto. Si scopre che il Lemma di Farkas è il cuore pulsante della Dualità. Senza Farkas, non sapremmo che ogni problema di ottimizzazione ha un "gemello speculare" (il duale). Senza Farkas, non avremmo i certificati di ottimalità che garantiscono che la soluzione trovata dal vostro solver è davvero la migliore possibile.

Da un'oscura nota a piè di pagina nella meccanica dell'800, il lemma è diventato il "martello" con cui la Ricerca Operativa rompe ogni problema di esistenza. È la rivincita postuma di Farkas: voleva solo capire come stavano in piedi gli oggetti, ha finito per spiegarci come ottimizzare il mondo.

Perché Funziona — La Geometria Sottostante¶

Il Potere della Separazione¶

Tutto si basa sull'idea intuitiva che se hai un oggetto convesso (come il nostro cono) e un punto fuori da esso, puoi sempre infilare un foglio di carta (un iperpiano) tra i due.

La grande intuizione geometrica è capire che l'impossibilità di soddisfare un insieme di vincoli lineari può sempre essere "certificata" da un contro-esempio (il vettore $y$).

Applicazione: La Dualità nella Programmazione Lineare¶

Questa è l'applicazione "killer" del Lemma di Farkas. È il pilastro su cui si regge il Teorema della Dualità Forte.

In Programmazione Lineare (PL), abbiamo un problema primale (minimizzare i costi) e un problema duale (massimizzare il profitto delle risorse). La dualità forte afferma che se uno ha una soluzione ottima, anche l'altro ce l'ha, e i valori delle funzioni obiettivo coincidono.

Come si usa Farkas qui?

Immagina di voler dimostrare che non esiste una soluzione migliore del tuo attuale ottimo $x^*$. Questo è un problema di "in-esistenza" di una soluzione ($c^T x < c^T x^*$, $Ax=b$, $x \geq 0$). Il Lemma di Farkas trasforma questo problema di "non esistenza" in un problema di "esistenza" per il sistema alternativo. E indovina un po'? Il sistema alternativo corrisponde esattamente ai vincoli del problema duale!

In parole povere: 1. Chiedersi se il primale può fare meglio equivale a cercare una soluzione a un certo sistema. 2. Se quel sistema non ha soluzione (cioè l'ottimo è raggiunto), Farkas ci dice che deve esistere una soluzione per il sistema alternativo. 3. Quella soluzione alternativa è proprio la soluzione ottima del problema Duale.

Senza Farkas, la dualità rimarrebbe una bella simmetria osservata, ma non un teorema rigorosamente dimostrato.

La Dimostrazione Completa¶

Dimostreremo il Lemma di Farkas in modo completamente autocontenuto, partendo dai principi base. La dimostrazione richiede prima di costruire il Teorema dell'Iperpiano Separatore, quindi lo costruiremo da zero.

Passo 1: Concetti Base di Geometria Convessa¶

Definizione (Insieme Convesso): Un insieme $S \subseteq \mathbb{R}^m$ è convesso se per ogni coppia di punti $x, y \in S$ e ogni $\lambda \in [0,1]$, si ha $\lambda x + (1-\lambda)y \in S$.

Intuizione: Il segmento che unisce due punti qualsiasi dell'insieme rimane completamente dentro l'insieme.

Definizione (Cono): Un insieme $C \subseteq \mathbb{R}^m$ è un cono se per ogni $x \in C$ e ogni $\alpha \geq 0$, si ha $\alpha x \in C$.

Intuizione: Se un punto è nel cono, anche tutti i suoi multipli positivi lo sono.

Definizione (Cono Convesso): Un insieme che è sia un cono che un insieme convesso.

Nel nostro caso, l'insieme $C = \{ Ax \mid x \geq 0 \}$ è un cono convesso perché: - Se $Ax_1 \in C$ e $Ax_2 \in C$ (con $x_1, x_2 \geq 0$), allora $\lambda(Ax_1) + (1-\lambda)(Ax_2) = A(\lambda x_1 + (1-\lambda)x_2) \in C$ per $\lambda \in [0,1]$ (convessità) - Se $Ax \in C$ (con $x \geq 0$), allora $\alpha(Ax) = A(\alpha x) \in C$ per $\alpha \geq 0$ (proprietà del cono)

Passo 2: Proiezione su un Insieme Convesso Chiuso¶

Teorema (Esistenza e Unicità della Proiezione): Dato un insieme convesso chiuso $S \subseteq \mathbb{R}^m$ e un punto $b \notin S$, esiste un unico punto $p \in S$ che minimizza la distanza da $b$, cioè: $$p = \arg\min_{z \in S} \|z - b\|$$

Dimostrazione: 1. Sia $d = \inf_{z \in S} \|z - b\|$ (la distanza infima). Esiste una sequenza $\{z_k\} \subseteq S$ tale che $\|z_k - b\| \to d$. 2. Mostriamo che $\{z_k\}$ è una sequenza di Cauchy. Per il teorema del parallelogramma: $$\|z_i + z_j - 2b\|^2 + \|z_i - z_j\|^2 = 2\|z_i - b\|^2 + 2\|z_j - b\|^2$$ 3. Per convessità, $(z_i + z_j)/2 \in S$, quindi $\|(z_i + z_j)/2 - b\| \geq d$. 4. Sostituendo: $4d^2 + \|z_i - z_j\|^2 \leq 2\|z_i - b\|^2 + 2\|z_j - b\|^2$ 5. Per $i, j \to \infty$, entrambi i termini a destra tendono a $2d^2$, quindi $\|z_i - z_j\| \to 0$. 6. Poiché $\mathbb{R}^m$ è completo e $S$ è chiuso, $z_k \to p \in S$. 7. L'unicità segue dalla stretta convessità della norma euclidea.

Passo 3: Caratterizzazione della Proiezione¶

Lemma (Condizione di Optimalità): Sia $p$ la proiezione di $b$ su $S$ convesso chiuso. Allora per ogni $z \in S$: $$(b - p)^T(z - p) \leq 0$$

Intuizione: Il vettore da $p$ a $b$ forma un angolo ottuso (o retto) con ogni vettore che va da $p$ verso qualsiasi altro punto di $S$.

Dimostrazione: 1. Per definizione di $p$, abbiamo $\|b - p\| \leq \|b - z\|$ per ogni $z \in S$. 2. Per convessità, $p + t(z - p) \in S$ per ogni $t \in [0,1]$. 3. Quindi $\|b - p\|^2 \leq \|b - p - t(z - p)\|^2$ per ogni $t \in [0,1]$. 4. Espandendo il lato destro: $$\|b - p\|^2 \leq \|b - p\|^2 - 2t(b - p)^T(z - p) + t^2\|z - p\|^2$$ 5. Semplificando: $0 \leq -2t(b - p)^T(z - p) + t^2\|z - p\|^2$ 6. Dividendo per $t > 0$: $0 \leq -2(b - p)^T(z - p) + t\|z - p\|^2$ 7. Per $t \to 0^+$: $(b - p)^T(z - p) \leq 0$

Passo 4: Il Teorema dell'Iperpiano Separatore¶

Teorema: Sia $S \subseteq \mathbb{R}^m$ un insieme convesso chiuso e sia $b \notin S$. Allora esiste un vettore $y \neq 0$ tale che: $$y^T b < \inf_{z \in S} y^T z$$

Intuizione: Possiamo trovare un piano che "taglia" tra $b$ e $S$, lasciando $b$ da una parte e tutto $S$ dall'altra.

Dimostrazione: 1. Sia $p$ la proiezione di $b$ su $S$ (esiste per il teorema del Passo 2). 2. Definiamo $y = b - p$. Notiamo che $y \neq 0$ perché $b \notin S$. 3. Dal Lemma del Passo 3, per ogni $z \in S$: $(b - p)^T(z - p) \leq 0$ 4. Quindi: $y^T(z - p) \leq 0$, ossia $y^T z \leq y^T p$ per ogni $z \in S$. 5. Dobbiamo mostrare che $y^T b < y^T p$. 6. Calcoliamo: $y^T b = (b - p)^T b = (b - p)^T (p + (b - p)) = (b - p)^T p + \|b - p\|^2$ 7. E: $y^T p = (b - p)^T p$ 8. Quindi: $y^T b = y^T p + \|b - p\|^2$ 9. Poiché $\|b - p\|^2 > 0$ (dato che $b \neq p$), abbiamo $y^T b > y^T p \geq y^T z$ per ogni $z \in S$.

Ops! Abbiamo ottenuto $y^T b > y^T z$, ma volevamo $y^T b < y^T z$. Basta prendere $-y$ invece di $y$:

Con $y' = -(b - p) = p - b$, otteniamo: $$y'^T b < \inf_{z \in S} y'^T z$$

Passo 5: Dimostrazione del Lemma di Farkas¶

Ora abbiamo tutti gli strumenti. Dimostriamo che esattamente uno dei due sistemi ha soluzione: 1. Sistema 1: $Ax = b$ con $x \geq 0$ 2. Sistema 2: $A^T y \geq 0$ con $b^T y < 0$

Dimostrazione:

Parte A: I due sistemi non possono entrambi avere soluzione (mutua esclusività)

Supponiamo per assurdo che entrambi abbiano soluzione. Siano $x$ e $y$ soluzioni rispettivamente. - Dal Sistema 1: $Ax = b$ con $x \geq 0$ - Dal Sistema 2: $A^T y \geq 0$ con $b^T y < 0$

Moltiplichiamo il Sistema 2 a sinistra per $x^T$: $$x^T A^T y \geq 0$$

Ma $x^T A^T y = (Ax)^T y = b^T y < 0$ (usando il Sistema 1).

Contraddizione! Quindi i due sistemi sono mutualmente esclusivi.

Parte B: Almeno uno dei due sistemi ha soluzione

Definiamo $C = \{ Ax \mid x \geq 0 \}$ = l'insieme di tutte le combinazioni lineari non-negative delle colonne di $A$.

$C$ è un cono convesso (dimostrato al Passo 1) e chiuso (combinazione finita di raggi).

Caso 1: Se $b \in C$, allora esiste $x \geq 0$ tale che $Ax = b$. Il Sistema 1 ha soluzione. ✓

Caso 2: Se $b \notin C$, applichiamo il Teorema dell'Iperpiano Separatore (Passo 4).

Esiste $y \neq 0$ tale che: $$y^T b < \inf_{z \in C} y^T z$$

Ora dobbiamo mostrare che: 1. $A^T y \geq 0$ 2. $b^T y < 0$

Dimostrazione di (1): $C$ è un cono che contiene l'origine ($0 \in C$ perché $A \cdot 0 = 0$).

Quindi $\inf_{z \in C} y^T z \leq y^T 0 = 0$.

Combinato con $y^T b < \inf_{z \in C} y^T z$, otteniamo: $$y^T b < 0$$

Questo è esattamente la condizione (2)! ✓

Per la condizione (1), osserviamo che ogni colonna $a_i$ di $A$ appartiene a $C$ (prendendo $x$ con tutte componenti zero tranne la $i$-esima uguale a 1).

Quindi per ogni colonna $a_i$: $y^T a_i \geq \inf_{z \in C} y^T z$

Inoltre, per il fatto che $C$ è un cono, se $z \in C$ allora $\alpha z \in C$ per ogni $\alpha \geq 0$.

Se esistesse una colonna $a_j$ con $y^T a_j < 0$, allora $y^T(\alpha a_j) = \alpha(y^T a_j) \to -\infty$ per $\alpha \to +\infty$, contraddicendo il fatto che l'infimo è finito.

Quindi $y^T a_i \geq 0$ per ogni colonna $a_i$, ossia $A^T y \geq 0$. ✓

Conclusione: Abbiamo dimostrato che: - I due sistemi sono mutualmente esclusivi (Parte A) - Almeno uno dei due ha sempre soluzione (Parte B)

Quindi esattamente uno dei due sistemi ha soluzione. ∎

Variabili Spiegate¶

Simbolo	Descrizione
$A$	Matrice $m \times n$ dei coefficienti dei vincoli
$x$	Vettore colonna $n \times 1$ delle variabili (incognite) del primo sistema
$b$	Vettore colonna $m \times 1$ dei termini noti
$y$	Vettore colonna $m \times 1$ delle variabili del sistema alternativo (spesso i "moltiplicatori")
$A^T$	La trasposta della matrice $A$

Esempio Svolto¶

Immagina di voler esprimere il vettore $b = \begin{pmatrix} -1 \ -1 \end{pmatrix}$ come combinazione lineare positiva dei vettori $a_1 = \begin{pmatrix} 1 \ 0 \end{pmatrix}$ e $a_2 = \begin{pmatrix} 0 \ 1 \end{pmatrix}$.

Il cono generato da $a_1$ e $a_2$ è l'intero primo quadrante (tutto ciò che è positivo). Chiaramente $b$ (che sta nel terzo quadrante) non è lì dentro. Quindi il Sistema 1 ($Ax=b, x \geq 0$) non ha soluzione.

Per Farkas, deve esistere una $y$ per il Sistema 2 ($A^T y \geq 0, b^T y < 0$). Cerchiamo un vettore $y$ che faccia un angolo acuto con $a_1$ e $a_2$, ma ottuso con $b$.

Prendiamo $y = \begin{pmatrix} 1 \ 1 \end{pmatrix}$. Verifichiamo: 1. $A^T y = \begin{pmatrix} 1 & 0 \ 0 & 1 \end{pmatrix} \begin{pmatrix} 1 \ 1 \end{pmatrix} = \begin{pmatrix} 1 \ 1 \end{pmatrix} \geq 0$. (Soddisfatto!) 2. $b^T y = \begin{pmatrix} -1 & -1 \end{pmatrix} \begin{pmatrix} 1 \ 1 \end{pmatrix} = -2 < 0$. (Soddisfatto!)

Ecco fatto. L'esistenza di $y=(1,1)$ è il "certificato" che $b=(-1,-1)$ non può essere generato positivamente da $(1,0)$ e $(0,1)$.

Riferimenti¶

Farkas, G. (1902). Über die Theorie der einfachen Ungleichungen.
Bertsimas, D., & Tsitsiklis, J. N. Introduction to Linear Optimization.
Boyd, S., & Vandenberghe, L. Convex Optimization.

Simbolo	Descrizione
\(A\)	Matrice \(m \times n\) dei coefficienti dei vincoli
\(x\)	Vettore colonna \(n \times 1\) delle variabili (incognite) del primo sistema
\(b\)	Vettore colonna \(m \times 1\) dei termini noti
\(y\)	Vettore colonna \(m \times 1\) delle variabili del sistema alternativo (spesso i "moltiplicatori")
\(A^T\)	La trasposta della matrice \(A\)