Proiezioni, condizioni KKT e iperpiani

La proiezione di un punto su un insieme

Dati un insieme $S\subseteq\mathbb R^n$ e un punto $X\in\mathbb R^n$, proiettare $X$ su $S$ vuol dire trovare il punto di $S$ a distanza minima da $X$. Poi si ricavano le condizioni di ottimalità per i vincoli lineari, le KKT, e con quelle si calcola la distanza di un punto da un iperpiano.

La proiezione è un problema di ottimizzazione: con $X$ fissato si minimizza, per $Y\in S$, la distanza euclidea o il suo quadrato:

$$x^*=\arg\min_{Y\in S}\ \|X-Y\|^2$$

La proiezione è ben definita solo se il problema ha una soluzione e questa è unica.

Proiezione di $X$ su $S$

$X$$x^{\ast }$$Y$$x_1$$x_2$

• $S$
• $\Vert X-x^{\ast }\Vert$
• $\Vert X-Y\Vert$

$X_1$

1,7

$X_2$

0,6

$Y_1$

−0,3

$Y_2$

0,4

Proposizione. Se $S$ è chiuso, convesso e non vuoto, la proiezione di $X$ su $S$ esiste ed è unica. Non serve che $S$ sia limitato.

Dimostrazione. Sia $f(Y)=\|X-Y\|^2$. Se $\|Y\|\to+\infty$ allora $f(Y)\to+\infty$, quindi $f$ è coerciva su $\mathbb R^n$ e perciò anche su $S$. Poiché $S$ è chiuso e non vuoto, il problema ha soluzione. Per l'unicità

$$\nabla f(Y)=2(Y-X),\qquad\nabla^2f(Y)=2I$$

e $2I$ è definita positiva, quindi $f$ è strettamente convessa. Su un insieme convesso una funzione strettamente convessa ha al più un minimo. $\blacksquare$

Si può così definire l'operatore di proiezione sugli insiemi chiusi, convessi e non vuoti.

Direzioni ammissibili in un insieme convesso

Un minimo locale di $f$ su $S$ non ha direzioni che siano insieme di discesa e ammissibili. Se $S$ è convesso, le direzioni ammissibili si trovano subito.

Proposizione. Se $S$ è convesso e $x,\hat x\in S$ con $\hat x\ne x$, la direzione $d=\hat x-x$ è ammissibile in $x$, e $x+td\in S$ per ogni $t\in[0,1]$.

Dimostrazione. Il punto $x+td=(1-t)x+t\hat x$ è una combinazione convessa di due punti di $S$, quindi appartiene a $S$ per la convessità. $\blacksquare$

Vincoli lineari e teoremi dell'alternativa

Il caso scatolare e il simplesso hanno una forma particolare, che ha permesso di ragionare con le direzioni ammissibili. Con vincoli lineari generali, di disuguaglianza e di uguaglianza, il problema è

$$\begin{aligned} &\min_x f(x)\\ &a_i^\top x-b_i\le0,\quad i=1,\dots,m\\ &g_j^\top x-c_j=0,\quad j=1,\dots,p \end{aligned}$$

In forma compatta $Ax-b\le0$ e $Gx-c=0$, con $A\in\mathbb R^{m\times n}$ di righe $a_i^\top$ e $G\in\mathbb R^{p\times n}$ di righe $g_j^\top$. Le disuguaglianze si scrivono sempre con $\le$.

Se $\bar x$ è un minimo locale, non esiste una direzione ammissibile di discesa. Questo equivale a dire che un sistema di equazioni e disequazioni lineari in $d$ non ha soluzione: la discesa è $\nabla f(\bar x)^\top d<0$ e l'ammissibilità si scrive con relazioni lineari.

I teoremi dell'alternativa (non studiati) mettono in relazione due sistemi lineari: il primo ha soluzione se e solo se il secondo non ne ha. Servono perché è più semplice gestire l'esistenza di una soluzione che la sua non esistenza. Il sistema delle direzioni ammissibili di discesa non ha soluzione, quindi ne ha l'altro sistema, e da lì si arriva alle condizioni KKT.

La lagrangiana

Si associa un moltiplicatore a ogni vincolo: $\lambda\in\mathbb R^m$ alle disuguaglianze e $\mu\in\mathbb R^p$ alle uguaglianze. La lagrangiana è

$$L(x,\lambda,\mu)=f(x)+\lambda^\top(Ax-b)+\mu^\top(Gx-c)$$

Esempio. Con due disuguaglianze e un'uguaglianza lineari i moltiplicatori sono tre: $\lambda_1,\lambda_2$ e $\mu_1$. La funzione obiettivo può essere non lineare. Per $f(x)=5x_1^3-2x_2^2+3x_3-x_1x_4$ e le disuguaglianze $6x_1+3x_2-3x_3+4x_4-5\le0$ e $5x_1-x_2-x_3-2x_4+1\le0$, con l'uguaglianza lasciata in forma generica

$$\begin{aligned} L&=5x_1^3-2x_2^2+3x_3-x_1x_4\\ &\quad+\lambda_1(6x_1+3x_2-3x_3+4x_4-5)\\ &\quad+\lambda_2(5x_1-x_2-x_3-2x_4+1)\\ &\quad+\mu_1(g_1^\top x-c_1) \end{aligned}$$

Le condizioni KKT

Teorema (senza dimostrazione). Se $\bar x$ è un minimo locale del problema con vincoli lineari, esistono $\bar\lambda\in\mathbb R^m$ e $\bar\mu\in\mathbb R^p$ tali che

$$\begin{gathered} A\bar x-b\le0,\qquad G\bar x-c=0\\ \nabla_xL(\bar x,\bar\lambda,\bar\mu)=0\\ \bar\lambda^\top(A\bar x-b)=0,\qquad\bar\lambda\ge0 \end{gathered}$$

Le quattro condizioni sono l'ammissibilità, l'annullamento del gradiente della lagrangiana, la complementarità e il segno dei moltiplicatori delle disuguaglianze. I moltiplicatori $\bar\mu$ delle uguaglianze non hanno vincoli di segno.

Il gradiente rispetto a $x$ ha $n$ componenti. I termini $\lambda^\top(Ax-b)$ e $\mu^\top(Gx-c)$ sono lineari in $x$ e derivano in $A^\top\lambda$ e $G^\top\mu$: la trasposta serve perché $A^\top$ è $n\times m$ e $\lambda$ ha $m$ componenti. Quindi

$$\nabla_xL(x,\lambda,\mu)=\nabla f(x)+A^\top\lambda+G^\top\mu$$

Complementarità. Ogni $\bar\lambda_i$ è non negativo e ogni vincolo $a_i^\top\bar x-b_i$ è non positivo, quindi ogni prodotto è non positivo. La loro somma è zero soltanto se ogni prodotto è zero:

$$\bar\lambda_i\,(a_i^\top\bar x-b_i)=0,\qquad i=1,\dots,m$$

Quindi un vincolo non attivo, cioè con $<0$, ha moltiplicatore nullo, e un moltiplicatore positivo indica un vincolo attivo, cioè con $=0$. Un fattore diverso da zero obbliga l'altro a esserlo: da qui il nome.

Proposizione (senza dimostrazione). Se $f$ è convessa le condizioni KKT sono anche sufficienti: un punto che le soddisfa è un minimo globale.

Vincoli scatolari con le KKT

Le condizioni trovate con le direzioni ammissibili per $\ell_i\le x_i\le u_i$, con $\ell_i<u_i$, si ricavano ora per via algebrica. I vincoli vanno scritti con $\le0$:

$$x_i-u_i\le0,\qquad\ell_i-x_i\le0$$

I vincoli sono $2n$, quindi servono $2n$ moltiplicatori non negativi: $\lambda^+\in\mathbb R^n$ per i limiti superiori e $\lambda^-\in\mathbb R^n$ per quelli inferiori, dove il segno ricorda il cambio di verso. La lagrangiana, scritta per esteso, è

$$\begin{aligned} L&=f(x)+\sum_{i=1}^n\lambda_i^+(x_i-u_i)\\ &\quad+\sum_{i=1}^n\lambda_i^-(\ell_i-x_i) \end{aligned}$$

Derivando rispetto a $x_i$ restano solo i termini di indice $i$. Se $\bar x$ è un minimo locale, esistono $\bar\lambda^+,\bar\lambda^-\ge0$ tali che per ogni $i$

$$\begin{gathered} \frac{\partial f}{\partial x_i}(\bar x)+\bar\lambda_i^+-\bar\lambda_i^-=0\\ \bar\lambda_i^+(\bar x_i-u_i)=0,\quad\bar\lambda_i^-(\ell_i-\bar x_i)=0 \end{gathered}$$

I tre casi si distinguono con la complementarità:

• $\bar x_i=\ell_i$: allora $\bar x_i<u_i$, quindi $\bar\lambda_i^+=0$ e $\frac{\partial f}{\partial x_i}(\bar x)=\bar\lambda_i^-\ge0$;
• $\bar x_i=u_i$: allora $\bar x_i>\ell_i$, quindi $\bar\lambda_i^-=0$ e $\frac{\partial f}{\partial x_i}(\bar x)=-\bar\lambda_i^+\le0$;
• $\ell_i<\bar x_i<u_i$: entrambi i vincoli sono non attivi, quindi i due moltiplicatori sono nulli e $\frac{\partial f}{\partial x_i}(\bar x)=0$.

Sono le stesse tre condizioni di prima, ottenute da un'altra strada.

Classificazione e iperpiano ottimo

Ogni paziente di un insieme ha etichetta $+1$ se ha una patologia e $-1$ se non ce l'ha. Si vuole un modello che separi i due gruppi: un nuovo paziente riceve l'etichetta dal lato dell'iperpiano in cui cade.

Gli iperpiani di separazione sono infiniti. Uno troppo vicino a una classe separa in modo poco convincente. Il criterio naturale è metterlo a metà, equidistante dalle due classi: è l'iperpiano ottimo. Per definirlo serve saper calcolare la distanza di un punto da un iperpiano.

Un iperpiano di separazione

$-1$$-1$$-1$$+1$$+1$$+1$$x_1$$x_2$

• $H$

posizione di $H$

−1,9

La distanza di un punto da un iperpiano

Un iperpiano di $\mathbb R^n$ è

$$H=\{x\in\mathbb R^n:\ v^\top x+b=0\}$$

con $v\in\mathbb R^n$ non nullo, il vettore normale, e $b\in\mathbb R$ uno scalare, non il vettore dei termini noti di $Ax-b$. In $\mathbb R^2$ è una retta, e dalla geometria la distanza di un punto $X$ dalla retta è $|v_1X_1+v_2X_2+b|/\sqrt{v_1^2+v_2^2}$. In $\mathbb R^n$ la stessa espressione si scrive con il prodotto scalare.

Proposizione. La distanza di $X\in\mathbb R^n$ da $H$ è

$$\operatorname{dist}(X,H)=\frac{|v^\top X+b|}{\|v\|}$$

Dimostrazione. La distanza di $X$ da $H$ è la distanza dalla sua proiezione su $H$, cioè dalla soluzione di

$$\min_x\ \tfrac12\|x-X\|^2\quad\text{con}\quad v^\top x+b=0$$

La funzione è strettamente convessa e $H$ è chiuso, convesso e non vuoto, quindi la proiezione $x^*$ esiste ed è unica. Il vincolo è lineare e la funzione è convessa, quindi le KKT sono necessarie e sufficienti. C'è un solo vincolo, di uguaglianza: un moltiplicatore $\mu_1$, senza complementarità né segno.

$$L(x,\mu_1)=\tfrac12\|x-X\|^2+\mu_1(v^\top x+b)$$

Le KKT sono l'annullamento del gradiente e l'ammissibilità:

$$\begin{gathered} x^*-X+\mu_1v=0\\ v^\top x^*+b=0 \end{gathered}$$

La prima dà $x^*=X-\mu_1v$. Sostituita nella seconda,

$$v^\top X-\mu_1\|v\|^2+b=0 \quad\Longrightarrow\quad \mu_1=\frac{v^\top X+b}{\|v\|^2}$$

e quindi

$$\|x^*-X\|=|\mu_1|\,\|v\|=\frac{|v^\top X+b|}{\|v\|}\qquad\blacksquare$$

Distanza di $X$ da $H$

$X$$x^{\ast }$$v$$x_1$$x_2$

• $H$

$X_1$

1,5

$X_2$

1,5

Dimostrazioni

Dimostrati: esistenza e unicità della proiezione; direzione ammissibile in un insieme convesso; distanza di un punto da un iperpiano.

Senza dimostrazione: condizioni KKT per vincoli lineari; sufficienza delle KKT per $f$ convessa; teoremi dell'alternativa.