Ottimizzazione: minimi, esistenza e insiemi convessi

Estremo inferiore e minimo

Data $f:X\subseteq\mathbb R^n\to\mathbb R$, l'immagine $Y=f(X)=\{f(x):x\in X\}$ è un sottoinsieme di $\mathbb R$. Ha quindi senso il suo estremo inferiore:

$$f^*=\inf_{x\in X}f(x)=\inf Y\in\mathbb R^*$$

L'estremo inferiore esiste sempre nei reali estesi $\mathbb R^*$: vale $-\infty$ se $Y$ non ha minoranti e, per convenzione, $\inf\emptyset=+\infty$.

Il minimo invece può mancare. Se esiste $x^*\in X$ con $f(x^*)=f^*$, allora $f^*$ è il valore minimo e si scrive $f^*=\min_{x\in X}f(x)$. Il problema si scrive con $\min$ anche prima di sapere se il minimo esiste: la scrittura sottintende che l'esistenza va verificata.

Il problema di ottimizzazione

Dati $f$ e un insieme $S\subseteq X$, il problema di ottimizzazione è

$$\min_{x\in S}f(x)$$

$S$ è l'insieme ammissibile. Il problema è non vincolato se $S=\mathbb R^n$, quindi $x$ varia liberamente, e vincolato se $S$ è un sottoinsieme proprio di $\mathbb R^n$. Il problema è

• inammissibile se $S=\emptyset$, e allora $f^*=+\infty$;
• illimitato inferiormente se per ogni $M>0$ esiste $x\in S$ con $f(x)<-M$, cioè $f^*=-\infty$.

Un problema di massimo è un problema di minimo per la funzione opposta, con gli stessi punti ottimi:

$$\max_{x\in S}f(x)=-\min_{x\in S}\bigl(-f(x)\bigr)$$

Minimi globali e locali

Un punto $x^*\in S$ è minimo globale di $f$ su $S$ se $f(x^*)\le f(x)$ per ogni $x\in S$: è il migliore possibile su tutto $S$. È stretto se $f(x^*)<f(x)$ per ogni $x\in S$ diverso da $x^*$, e allora è l'unico punto di minimo globale.

Un punto $x^*\in S$ è minimo locale se è il migliore fra i punti ammissibili vicini: esiste $\varepsilon>0$ tale che

$$f(x^*)\le f(x)\quad\forall x\in S\cap B(x^*,\varepsilon)$$

È stretto se la disuguaglianza è stretta per $x\ne x^*$. Spesso minimizzando si trova un minimo locale: un minimo globale è più difficile da trovare, e anche da riconoscere.

Esempio. $f(x)=-x^2$ su $S=[-1,2]$. Il minimo globale è $x^*=2$, perché su $S$ si ha $x^2\le4$, quindi $f(x)\ge-4=f(2)$. Il punto $\bar x=-1$ è minimo locale: con $\varepsilon=1$ si ha $S\cap B(-1,1)=[-1,0)$, dove $x^2\le1$ e quindi $f(x)\ge-1=f(-1)$. Non è globale, perché $f(2)=-4$.

Minimo locale e minimo globale di $-x^2$ su $[-1,2]$

$\bar{x}$$x^{\ast }$$x$$f(x)$

• livello $f(\bar{x})$
• $f$ su $S$
• $f$ su $S\cap B(\bar{x},\epsilon )$
• $S\cap B(\bar{x},\epsilon )$

$\epsilon$

1

I quattro esiti

Per il problema $\min_{x\in S}f(x)$ capita sempre uno e uno solo di questi casi:

1. inammissibile: $S=\emptyset$, $f^*=+\infty$. Per esempio $f(x)=x^2$ con $S=\{x:x>1,\ x<-1\}$;
2. illimitato inferiormente: $f^*=-\infty$. Per esempio $-x^2$ su $[0,+\infty)$, oppure $x^3$ su $\mathbb R$;
3. estremo inferiore ma non soluzione ottima: $f^*$ è finito, ma nessun $x^*\in S$ ha $f(x^*)=f^*$. Per esempio $e^x$ su $\mathbb R$, con $f^*=0$, oppure $x^2$ o $x$ su $(1,+\infty)$, con $f^*=1$;
4. soluzione ottima: esiste un minimo globale. Per esempio $x^2$ su $[1,+\infty)$, con $x^*=1$, oppure $x^2$ su $\mathbb R$, con $x^*=0$.

Nel caso 3 il valore $f^*$ si avvicina senza essere raggiunto. La causa può essere la funzione, come $e^x$, sempre positiva, oppure l'insieme: $(1,+\infty)$ è aperto a sinistra e non contiene il punto $1$ che darebbe il minimo. Per questo serve riconoscere gli insiemi aperti e chiusi.

$x^2$ su un insieme chiuso e su uno aperto

$S=[1,+\infty )$

$x^{\ast }=1$$x$$f(x)$

• $x^2$ su $S$
• $S$

$S=(1,+\infty )$

$f^{\ast }=1$$x$$f(x)$

• $x^2$ su $S$
• $S$

Programmazione matematica

Il problema $\min_{x\in S}f(x)$ è di programmazione matematica se $S$ è descritto da un numero finito di disequazioni e di equazioni:

$$\begin{aligned} S=\{x\in\mathbb R^n:\ &g_i(x)\le0,\ i=1,\dots,m,\\ &h_j(x)=0,\ j=1,\dots,p\} \end{aligned}$$

È un caso particolare del problema di ottimizzazione, in cui $S$ ha questa struttura precisa. Per esempio $\min\{\log x:x\ge1\}$ e $\min\{x+y:y\ge0,\ y\le x^3\}$.

Esistenza del minimo

In più variabili la funzione non si disegna e il minimo non si trova a occhio. Prima di cercarlo conviene sapere se esiste. Le condizioni sono due, una per il caso vincolato e una per quello non vincolato.

Teorema di Weierstrass. Se $S\subseteq\mathbb R^n$ è non vuoto e compatto e $f$ è continua su $S$, allora $f$ ammette minimo globale e massimo globale su $S$.

Un problema con $S$ così è quindi nel caso 4. Se invece $S=\mathbb R^n$, che non è limitato, la continuità non basta: $e^x$ è continua e non ha minimo.

L'insieme di livello $\alpha$ di $f:\mathbb R^n\to\mathbb R$ è

$$L_\alpha=\{x\in\mathbb R^n:f(x)\le\alpha\}$$

purché non sia vuoto. Rispetto al contorno di livello, dove vale $f(x)=\alpha$, l'uguaglianza diventa $\le$.

Teorema. Sia $f$ continua su $\mathbb R^n$. Se esiste un $\alpha$ per cui $L_\alpha$ è non vuoto e compatto, allora $f$ ammette minimo globale su $\mathbb R^n$.

Basta un solo $\alpha$: l'insieme di livello sostituisce l'insieme compatto che manca, e il minimo è globale su tutto $\mathbb R^n$. È una conseguenza del teorema di Weierstrass.

Esempio. Per $f(x)=x^2$, con $\alpha=-1$ non ci sono punti con $x^2\le-1$, quindi non c'è un insieme di livello. Con $\alpha=1$ si ottiene $L_1=[-1,1]$, non vuoto, chiuso e limitato. Quindi $x^2$ ha minimo globale su $\mathbb R$.

Insiemi di livello di $x^2$

$x^{\ast }$$x$$f(x)$

• $f(x)=x^2$
• livello $\alpha$
• $L_{\alpha }$

$\alpha$

1

Segmenti e insiemi convessi

Il segmento chiuso e il segmento aperto fra $x,y\in\mathbb R^n$ sono

$$\begin{aligned} [x,y]&=\{z:\ z=ty+(1-t)x,\ t\in[0,1]\}\\ (x,y)&=\{z:\ z=ty+(1-t)x,\ t\in(0,1)\} \end{aligned}$$

Per $t=0$ si ha $z=x$, per $t=1$ si ha $z=y$: il segmento aperto esclude gli estremi.

Un insieme $C\subseteq\mathbb R^n$ è convesso se, comunque scelti $x,y\in C$, si ha $[x,y]\subseteq C$. In un insieme non convesso alcune coppie hanno il segmento dentro, ma almeno una lo ha in parte fuori.

Un insieme convesso e uno non convesso

Convesso

$x$$y$$x_1$$x_2$

• $C$
• $[x,y]$

Non convesso

$x$$y$$x_1$$x_2$

• $C$
• $[x,y]$

prima coordinata di $x$

−1

seconda coordinata di $x$

0,6

prima coordinata di $y$

1

seconda coordinata di $y$

0,6

Proposizione. $\mathbb R^n$ e l'insieme vuoto sono convessi.

Dimostrazione. Ogni punto di un segmento di $\mathbb R^n$ sta in $\mathbb R^n$. In $\emptyset$ non si possono scegliere due punti, quindi nessuna coppia viola la definizione.

Proposizione (dimostrata in parte). L'intersezione di due insiemi convessi è convessa, e così quella di un numero finito o infinito di convessi.

Dimostrazione. Si dimostra per due insiemi e per un numero finito. Siano $C_1,C_2$ convessi e $x,y\in C_1\cap C_2$. Poiché $x,y\in C_1$ e $C_1$ è convesso, $[x,y]\subseteq C_1$; allo stesso modo $[x,y]\subseteq C_2$. Quindi $[x,y]\subseteq C_1\cap C_2$. Con tre o più insiemi si interseca un convesso alla volta.

Dimostrazioni

Dimostrati: $\mathbb R^n$ e $\emptyset$ sono convessi; intersezione di insiemi convessi (in parte).