Esistenza delle soluzioni ottime §

In questo capitolo trattiamo dell’esistenza di soluzioni di problemi di ottimiz- zazione del tipo:

$$\min f(x)x\in C$$

dove $C\subseteq {\mathbb{R}}^n$ e $f:C\to \mathbb{R}$. Abbiamo quattro casi possibli:

1. L’insieme ammissibile $C$ è vuoto;
2. Il problema è illimitato inferiormente;
3. Il problema è limitato inferiormente ma non ammette soluzioni ottime: Esempio $f(x)=e^{-x},x\ge 0$
4. Il problema ha almeno una soluzione ottima.

Proposizione 1 §

Sia $C$ chiuso e $f$ continua. Allora l’insieme delle soluzioni ottime $SOL(C,f)$ è chiuso.

Dim §

Se $SOL(C,f)=\varnothing$, è chiuso per convenzione. Consideriamo un insieme di soluzioni non vuoto:

$$SOL(C,f):=\{x\in C|f(x)=\overline{f}\}$$

Facciamo vedere che è chiuso dimostrando che ogni successione convergente contenuta in $SOL(C,f)$ converge ad un punto di esso. Sia $\{x{\}}_k\subseteq SOL(C,f)$ e ${\lim }_{k\to \infty }{x}_k=\overline{x}$. Come prima cosa, essendo $C$ chiuso per ipotesi $\overline{x}\in C$. Mostriamo ora come la continuità della $f$ implichi che l’insieme è chiuso:

$$\overline{f}=\underset{k\to \infty }{\lim }f(x_k)=f(\underset{k\to \infty }{\lim }{x}_k)=f(\overline{x})$$

$\square$

Non si può non enunciare il Teorema di Weierstrass, che garantisce l’esistenza dell’insieme delle soluzioni quando $C$ è compatto ed $f$ continua.

Quando non si può applicare Weierstrass direttamente, è utile il teorema sugli insiemi di livello, posso ragionare su $C\bigcap \mathcal{L}(\alpha ,f)$ per un qualche $\alpha \in Im(f)$, che potrebbe essere limitato. Ha le stesse soluzioni ottime, dalla definizione di insieme di livello!

Utile il seguente fatto:

Teorema §

Gli insiemi di livello di una funzione continua e coerciva sono Compatti

Dim §

La chiusura segue dalla definzione di insieme di livello e della continuità della $f$, la limitatezza dalla coercività della funzione! (prima o poi se mi allontano troppo $f\ge \alpha$).

Oss §

Le curve di livello di una funzione convessa in generale non sono insiemi convessi, questo vale solo quando la funzione è affine (dimostrazione ovvia, basta considerare gli insiemi complementari).

Oss conclusiva §

Possiamo combinare i precedenti teoremi/osservazioni con questo enunciato:

Il problema $MIN(C,f)$ con $f$ continua e coerciva, $C$ insieme chiuso, allora $SOL(C,f)$ è non vuoto e compatto

infatti $SOL(C,f)=SOL(C\bigcap \mathcal{L},f)$ che per continuità e coercività è compatto, quindi non vuoto per il Teorema di Weierstrass e chiuso per la Proposizione 1.