Nota: se vi interessa solo l’algoritmo e non la discussione cercate il Teorema in grassetto più giù.
Conosciamo bene il metodo dei moltiplicatori di Lagrange per estremizzare una funzione soggetta a dei vincoli. Supponiamo di voler trovare i punti critici della funzione $f: \mathbb{R}^n \to \mathbb{R}$ soggetta ai $k$ vincoli $g_j(\mathbf x) = 0$ dove $j = 1,2,\ldots, k$. Allora i punti critici di $f$ soggetta al vincolo sono i punti critici della Lagrangiana
$$\mathcal{L}(\boldsymbol \lambda, \mathbf x) = f(\mathbf x)-\sum_{j=1}^k \lambda_j g_j (\mathbf x)$$
senza alcun vincolo, dove le variabili ausiliarie $\boldsymbol \lambda$ sono dette moltiplicatori di Lagrange. Calcolando le derivate della lagrangiana, otteniamo che la soluzione del problema è la soluzione delle $n+k$ equazioni in $n+k$ variabili:
$$\begin{cases}
\pdv{\mathcal{L}}{\lambda_j} = g_j = 0\\
\pdv{\mathcal{L}}{x_i} = \pdv{f}{x_i}-\sum_{j=1}^k \lambda_j \pdv{\mathcal{g_j}}{x_i}=0\\
\end{cases}$$
Chiamiamo la soluzione $\mathbf x^*$, $\boldsymbol \lambda^*$. Sotto quali condizioni questa soluzione è un massimo/minimo?
In un problema non vincolato calcoleremmo la matrice hessiana della funzione, ovvero la matrice delle derivate seconde. Se è definita positiva nel punto critico allora il punto è un minimo; se è definita negativa allora il punto è un massimo. In questo caso l’Hessiana di $\mathcal{L}$ è la matrice quadrata $(k+n)$ data da:
$$H = \begin{pmatrix} 0 & -(D\mathbf g)^T\\-D\mathbf g & D^2 \mathcal{L}\end{pmatrix}$$
dove:
- $D\mathbf g$ è la matrice $n \times k$ i cui elementi sono $(D\mathbf g)_{ij} = \partial_i g_j$ e le derivate $\partial_i$ si riferiscono alle variabili $x_i$.
- $D^2 \mathcal{L}$ è la matrice $n \times n$ delle derivate seconde di $\mathcal{L}$ rispetto alle variabili $\mathbf x$, ovvero i cui elementi sono $(D^2 \mathcal{L})_{ij} = \partial_i \partial_j \mathcal L$.
- La matrice in alto a sinistra (di dimensioni $k \times k$) è nulla perché è il termine che corrisponde a due derivate rispetto a $\lambda$.
- È sottinteso che tutte le quantità sono calcolate nel punto $\mathbf x^*$, $\boldsymbol \lambda^*$
Poiché $H$ ha questa forma, notiamo subito che il test che utilizziamo di solito non può valere: se infatti $\mathbf v = (1,0,\ldots,0)$ è il vettore il cui unico componente non nullo è il primo, allora per qualsiasi $f,g,\mathcal L$ abbiamo sempre $\mathbf v^T H \mathbf v=0$. Quindi l’Hessiana della Lagrangiana è sempre indefinito, e dobbiamo quindi adoperare un test diverso. Ciò accade perché le $\boldsymbol{\lambda}$ sono solo variabili ausiliarie.
L’idea che ci permette di proseguire è di risolvere tutti i vincoli $g_j (\mathbf x)=0$, almeno idealmente, ottenendo un insieme $D \in \mathbb{R}^n$, ovvero
$$D = \{\mathbf x \in \mathbb{R}^n\,\,\mathrm{t.c.}\,\, g_j (\mathbf x)=0\,\,\forall j\}$$
Ad esempio se $g_1(x,y,z)=x^2+y^2-1$ (un cilindro infinito) e $g_2(x,y,z)= x+y+z$ (un piano), $D$ sarà data dai punti $(x,y,z)$ che soddisfano sia $x^2+y^2=1$ e $x+y+z=0$, ottenendo per risultato una specie di ellisse storto.
A questo punto possiamo “sostituire” il risultato ottenuto in $f(\mathbf x)$ e ottenere una funzione $D\to \mathbb{R}$ che possiamo studiare tradizionalmente. Consideriamo infatti una curva $\mathbf r(t) \in D$ tale che $\mathbf r(0)=\mathbf x^*$ e $\mathbf r'(0)=\mathbf v$. Allora:
$$\dv{^2 f(\mathbf r(t))}{t^2}\bigg\lvert_{t=0} = \mathbf v^T\, D^2 \mathcal{L} (\mathbf x^*, \boldsymbol \lambda^*)\,\mathbf v$$
La dimostrazione consiste nel calcolare la derivata seconda di $f(\mathbf r(t))$ usando il fatto che $\mathbf x^*$ è un punto critico e il fatto che la derivata seconda di $g_j(\mathbf r(t))$ è nulla (semplicemente perché $g_j(\mathbf r(t))=0$ per definizione).
Per trasformare questo risultato in un test, resta da capire quali sono i possibili vettori $\mathbf v$, ma ciò non è difficile. Infatti derivando la condizione $g_j(\mathbf r(t))$, otteniamo che $\mathbf v$ è tangente ad una curva in $D$ se e solo se $(D\mathbf g)^T\mathbf v =0$, ovvero se e solo se $\mathbf v \in \mathrm{ker}(D\mathbf g)^T$. Pertanto abbiamo il seguente test:
- Se $\mathbf v^T\, D^2 \mathcal{L} (\mathbf x^*, \boldsymbol \lambda^*)\,\mathbf v \geq 0$ per ogni $\mathbf v \in \mathrm{ker}(D\mathbf g)^T$ allora il punto $(\mathbf x^*, \boldsymbol \lambda^*)$ è un minimo.
- Se $\mathbf v^T\, D^2 \mathcal{L} (\mathbf x^*, \boldsymbol \lambda^*)\,\mathbf v \leq 0$ per ogni $\mathbf v \in \mathrm{ker}(D\mathbf g)^T$ allora il punto $(\mathbf x^*, \boldsymbol \lambda^*)$ è un massimo.
- Se $\mathbf v^T\, D^2 \mathcal{L} (\mathbf x^*, \boldsymbol \lambda^*)\,\mathbf v$ assume segni diversi per $\mathbf v \in \mathrm{ker}(D\mathbf g)^T$ allora il punto $(\mathbf x^*, \boldsymbol \lambda^*)$ è una sella.
Il test che abbiamo appena sviluppato è in realtà abbastanza tedioso: dobbiamo calcolare la derivata dei vincoli, trovarne il kernel e verificare che la derivata seconda della lagrangiana sia definita positiva sul kernel. A partire da questa condizione, se ne può trovare una equivalente sull’Hessiana originale:
Notazione. Data una matrice $A$ (non per forza quadrata), chiamiamo $A_m$ la sottomatrice quadrata di $A$ ottenuta prendendo le prime $m$ righe e le prime $m$ colonne di $A$.
Teorema. Data $f: \mathbb{R}^n \to \mathbb{R}$ soggetta ai $k$ vincoli $g_j(\mathbf x) = 0$ dove $j = 1,2,\ldots, k$ e supposto che $(D\mathbf g)_k$ abbia determinante non nullo, allora
- Se $(-1)^k \det{H_j} > 0$ per $2k+1\leq j \leq n+k$ allora il punto critico è un minimo.
- Se $(-1)^{j-k} \det{H_j} > 0$ per $2k+1\leq j \leq n+k$ allora il punto critico è un massimo.
- Se le prime due condizioni sono entrambe violate ma $\det{H_j}\neq 0$ per $2k+1\leq j \leq n+k$, allora il punto critico è una sella.
La condizione è piuttosto curiosa, ma tale è. Può essere semplificata in alcuni casi particolari: infatti se $n=2$ e $k=1$, cioè due variabili e un vincolo, allora
- Se $\det{H} < 0$ il punto è un minimo
- Se $\det{H} > 0$ il punto è un massimo
che è notevolmente più semplice.