Ottimizzazione vincolata: esistenza e ottimalità

Dal caso non vincolato al vincolato

Il problema è $\min_{x\in S}f(x)$, con $f\in C^1$ e $S\subset\mathbb R^n$ l'insieme dei punti che soddisfano i vincoli. Il percorso è quello del caso non vincolato: esistenza della soluzione, poi condizioni di ottimalità, poi la loro forma secondo la struttura di $S$.

Esistenza della soluzione

Se $S$ è compatto e non vuoto, il teorema di Weierstrass assicura il minimo. Se $S$ è chiuso e non limitato si ripete il ragionamento dei livelli, tenendo conto solo dei punti di $S$:

$$\mathcal L_S(\alpha)=\{x\in S:\ f(x)\le\alpha\}$$

purché non sia vuoto.

Proposizione. Se $f$ è continua e per un $\alpha$ l'insieme $\mathcal L_S(\alpha)$ è compatto, il problema ammette soluzione.

Dimostrazione. Come nel caso non vincolato. Per Weierstrass esiste $x^*\in\mathcal L_S(\alpha)$ con $f(x^*)\le f(x)$ per ogni $x\in\mathcal L_S(\alpha)$, e $f(x^*)\le\alpha$. Se $x\in S$ è fuori da $\mathcal L_S(\alpha)$, allora $f(x)>\alpha\ge f(x^*)$. $\blacksquare$

Come prima conviene una proprietà di $f$. La funzione $f$ è coerciva su $S$ se per ogni successione $\{x_k\}\subseteq S$

$$\|x_k\|\to+\infty\quad\Longrightarrow\quad f(x_k)\to+\infty$$

Il confronto riguarda solo le successioni che restano in $S$.

Proposizione (senza dimostrazione). Se $S$ è chiuso e non vuoto e $f$ è continua su $S$, tutti gli insiemi $\mathcal L_S(\alpha)$ sono compatti se e solo se $f$ è coerciva su $S$.

Corollario. Se $S$ è chiuso e non vuoto e $f$ è continua e coerciva su $S$, il problema ammette soluzione.

Dimostrazione. Per la proposizione appena enunciata ogni livello non vuoto è compatto, e la prima proposizione dà la soluzione. $\blacksquare$

Esempio. Sia

$$S=\Bigl\{x\in\mathbb R^n:\ \sum_{i=1}^nx_i=1,\ x\ge0\Bigr\}$$

dove $x\ge0$ vale per ogni componente. $S$ è chiuso, perché definito da un'uguaglianza e da disuguaglianze non strette. È anche limitato: le componenti sono non negative e sommano a $1$, quindi $0\le x_i\le1$. Quindi $S$ è compatto e una funzione continua ha minimo su $S$.

I segni contano. Con $x_2-x_3$ al posto di $x_2+x_3$ nella somma, $S$ resta chiuso ma non è più limitato: $x_2$ e $x_3$ possono crescere insieme senza cambiare la somma.

Sia $f(x)=\sum_ic_ix_i$. L'intuizione è dare tutto il valore, cioè $1$, alla variabile di costo minore. Per dimostrare che è ottimo serve una condizione di ottimalità: $S$ è un poliedro, intersezione di un iperpiano e di semispazi, quindi convesso, e $f$ è lineare, quindi convessa. Il gradiente $c$ è costante e non nullo, quindi la condizione $\nabla f(x)=0$ del caso non vincolato non può valere. Servono condizioni per i problemi vincolati.

Direzioni ammissibili

Nel caso non vincolato le condizioni nascono dall'assenza di direzioni di discesa: da un minimo non si può scendere. Con i vincoli una direzione di discesa può uscire da $S$, e allora non è un movimento permesso. Serve il concetto di direzione ammissibile.

Definizione. Un vettore $d\ne0$ è una direzione ammissibile in $\bar x\in S$ se esiste $\bar t>0$ tale che

$$\bar x+td\in S\qquad\forall t\in(0,\bar t\,]$$

Se $\bar x$ è interno a $S$, ogni direzione è ammissibile.

Direzioni ammissibili sul bordo di $S$

$\bar{x}$$x_1$$x_2$

• $S$
• $\bar{x}+td$

angolo di $d$

2,6

Proposizione. Se $\bar x$ è un minimo locale di $f$ su $S$, non esiste una direzione ammissibile e di discesa in $\bar x$. Se $f\in C^1$, per ogni direzione ammissibile $d$ in $\bar x$

$$\nabla f(\bar x)^\top d\ge0$$

Dimostrazione. Se $d$ fosse ammissibile e di discesa, per $t>0$ abbastanza piccolo $\bar x+td$ sarebbe in $S$, vicino a $\bar x$ e con $f(\bar x+td)<f(\bar x)$, contro il minimo locale. Se fosse $\nabla f(\bar x)^\top d<0$, la direzione $d$ sarebbe di discesa, e si è appena visto che non può esserlo. $\blacksquare$

Il prodotto $\nabla f(\bar x)^\top d$ è la derivata direzionale di $f$ lungo $d$.

Vincoli separati: il caso scatolare

Siano i vincoli

$$\ell_i\le x_i\le u_i,\qquad i=1,\dots,n$$

con $\ell_i<u_i$. Ogni vincolo riguarda una sola variabile, quindi si ragiona variabile per variabile con $d=\pm e_i$, dove $e_i$ ha solo la componente $i$ non nulla. La direzione $e_i$ è ammissibile se $\bar x_i<u_i$, la direzione $-e_i$ se $\bar x_i>\ell_i$.

Proposizione. Se $\bar x$ è un minimo locale di $f\in C^1$ su $S$, per ogni $i$

$$\frac{\partial f}{\partial x_i}(\bar x) \begin{cases} \ge0&\text{se }\bar x_i=\ell_i\\ \le0&\text{se }\bar x_i=u_i\\ =0&\text{se }\ell_i<\bar x_i<u_i \end{cases}$$

Dimostrazione. Con $d=e_i$ la condizione dà $\frac{\partial f}{\partial x_i}(\bar x)\ge0$ se $\bar x_i<u_i$. Con $d=-e_i$ dà $-\frac{\partial f}{\partial x_i}(\bar x)\ge0$ se $\bar x_i>\ell_i$. I tre casi sono le tre righe. $\blacksquare$

Già con i vincoli più semplici le condizioni sono più articolate di $\nabla f(x)=0$.

Una variabile con vincolo $[\ell ,u]$

$\ell$$u$$\bar{x}$$x_i$

• $f$
• tangente in $\bar{x}$
• $S=[\ell ,u]$

$m$

−0,3

Vincoli accoppiati: il simplesso

Si torna a $S=\{x:\ \sum_ix_i=1,\ x\ge0\}$, dove un vincolo lega tutte le variabili. Una direzione con una sola componente non nulla non conserva la somma. Servono almeno due componenti non nulle: una aumenta e un'altra diminuisce. Una componente uguale a $0$ può solo aumentare, una uguale a $1$ solo diminuire, una strettamente fra $0$ e $1$ può fare entrambe le cose. Le direzioni ammissibili più semplici hanno quindi due componenti non nulle: $d=e_j-e_i$, con $\bar x_i>0$.

Proposizione. Se $\bar x$ è un minimo locale di $f\in C^1$ sul simplesso, per ogni $i$ con $\bar x_i>0$ e per ogni $j$

$$\frac{\partial f}{\partial x_i}(\bar x)\le\frac{\partial f}{\partial x_j}(\bar x)$$

In particolare le derivate parziali delle componenti positive sono uguali tra loro.

Dimostrazione. Se $\bar x_i>0$, $d=e_j-e_i$ è ammissibile e $\nabla f(\bar x)^\top d=\frac{\partial f}{\partial x_j}(\bar x)-\frac{\partial f}{\partial x_i}(\bar x)\ge0$. Se $\bar x_i>0$ e $\bar x_j>0$ si possono usare sia $e_j-e_i$ sia $e_i-e_j$, quindi vale l'uguaglianza. $\blacksquare$

L'obiettivo lineare

Si ordinano le variabili in modo che $c_1\le c_2\le\dots\le c_n$ e si prende $\bar x=e_1$. L'unica componente positiva è la prima, e

$$\frac{\partial f}{\partial x_1}=c_1\le c_j=\frac{\partial f}{\partial x_j}\qquad\forall j$$

quindi $e_1$ soddisfa le condizioni. Poiché $S$ e $f$ sono convessi, vale un risultato che si riprende più avanti.

Proposizione (senza dimostrazione). Per un problema convesso, cioè con $S$ convesso e $f$ convessa, le condizioni di ottimalità sono necessarie e sufficienti per un minimo globale.

Quindi $e_1$ è un minimo globale: tutto il valore va alla variabile di costo minore.

Dimostrazioni

Dimostrati: esistenza con un livello compatto su $S$; esistenza con la coercività su $S$; condizione necessaria con le direzioni ammissibili; caso scatolare; simplesso.

Senza dimostrazione: livelli tutti compatti se e solo se $f$ è coerciva su $S$; sufficienza delle condizioni nei problemi convessi.