Utente:Venerabile Jorge/sandbox/prova ottimizzazione

L'ottimizzazione (o programmazione matematica, PM) è una branca della matematica applicata che studia teoria e metodi per la ricerca dei punti di massimo e minimo di una funzione matematica all'interno di un dominio specificato.

Descrizione

Un problema di ottimizzazione, talvolta detto di programmazione matematica, può essere formulato nel seguente modo:

Data: una funzione $f:A\to \mathbb {R}$ da un insieme $A$ nei numeri reali

Determinare un elemento $\mathbf {x} _{0}\in A$ tale che $f(\mathbf {x} _{0})\leq f(\mathbf {x} )$ per ogni $\mathbf {x} \in A$ ("minimizzazione") o tale che $f(\mathbf {x} _{0})\geq f(\mathbf {x} )$ per ogni $\mathbf {x} \in A$ ("massimizzazione").

Poiché punti di massimo per una funzione $f$ corrispondono a punti di minimo per la funzione ${\tilde {f}}=-f$, non è restrittivo formulare problemi di ottimizzazione in termini di minimizzazioni.

La funzione $f$ viene generalmente chiamata funzione obiettivo o funzione di costo. L'insieme $A$ può essere ad esempio un sottoinsieme dello |spazio euclideo $\mathbb {R} ^{n}$ definito in termini di vincoli, ovvero uguaglianze o disuguaglianze che gli elementi di $A$ devono soddisfare. Molti problemi nell'ambito delle scienze naturali, sia teoriche sia applicate, possono essere descritti da una formulazione di questo tipo.

I problemi di ottimizzazione richiedono necessariamente la creazione di algoritmi efficienti in quanto, generalmente, un problema di ottimizzazione possiede uno spazio delle possibili soluzioni di cardinalità esponenziale, quindi anche possedendo il più potente dei computer non potremmo permetterci di enumerare tutte le possibili soluzioni e scegliere la migliore. A titolo di esempio supponiamo di avere $n$ variabili $x(i),i=1,\ldots ,n$; che possono assumere $d(i)$ valori diversi $0,1,2,\ldots ,d(i)-1$; in questo caso avremo che il numero di soluzioni ammissibili per il problema sarebbe dato da: $ns=\sum _{1}^{n}d(i)$. Considerando $n=20{\text{ e }}d(i)=4$, si otterrebbe $ns=4^{20}\approx 10^{12}$. Di conseguenza un algoritmo enumerativo richiederebbe un tempo di esecuzione proporzionale a $10^{12}$ con soli 20 elementi.

L'ottimizzazione può essere suddivisa in due grandi categorie: dinamica e statica. Nell'ottimizzazione dinamica i vincoli e le variabili che esprimono il modello del problema possono variare nel tempo. Nella ottimizzazione statica vincoli e variabili sono costanti. A sua volta l'ottimizzazione statica si divide in continua e discreta in funzione del fatto che le variabili possano assumere valori continui o discreti. Nell'ambito della programmazione continua distinguiamo tra programmazione lineare, se funzione obiettivo e vincoli sono lineari, e programmazione non lineare altrimenti.

Un lettore non addetto potrebbe domandarsi come sia possibile trovare la soluzione ottima senza verificare una per una tutte le soluzioni disponibili. Questo può avvenire grazie a meccanismi di classificazione; il dominio delle soluzioni viene organizzato secondo una struttura che le ordina in funzione di determinate caratteristiche, quindi è possibile scartare a priori alcuni sottoinsiemi del dominio delle soluzioni senza esaminarle essendo sicuri del fatto che queste non potranno fornire soluzioni migliori di un determinato obiettivo. È un po' come entrare in una biblioteca e cercare un libro; i libri sono organizzati per argomento e per titolo alfabeticamente, quindi non sarà necessario esplorare tutti i libri della biblioteca per trovare quello che cerchiamo, ma solo un sottoinsieme. Questo è il meccanismo di funzionamento degli algoritmi e delle metodologie di risoluzione dei problemi di ottimizzazione tra cui ricordiamo il metodo del simplesso e la tecnica del branch and bound.

Limiti e formalizzazione

È applicabile solo a problemi decisionali con un solo decisore, un solo criterio di scelta ed ambiente certo. L'ambito di ricerca privilegiato dell'ottimizzazione sono i modelli esprimibili in termini di funzioni di più variabili, nei quali i punti di ottimo vengono ricercati ponendo anche vincoli espressi secondo equazioni o disequazioni anche in termini di derivate successive.

Nel caso più semplice, un problema di ottimizzazione consiste nel massimizzare o minimizzare una funzione reale scegliendo sistematicamente i valori di input da un insieme consentito e calcolando il valore della funzione. La generalizzazione della teoria e delle tecniche di ottimizzazione ad altre formulazioni costituisce una vasta area di matematica applicata. Più in generale, l'ottimizzazione include la ricerca dei "migliori valori disponibili" di alcune funzioni oggettive in un determinato dominio (o input), compresa una varietà di diversi tipi di funzioni oggettive e diversi tipi di domini.

Un qualsiasi problema di ottimizzazione può essere espresso nella seguente forma (nel caso della ricerca di un minimo, che è lo standard matematico in problemi di ottimizzazione):

$\left\{{\begin{matrix}\min {f(x)}\\x\in X\subseteq \mathbb {R} ^{n}\end{matrix}}\right.$

dove $f$ è una funzione reale, $x$ è il vettore delle variabili decisionali a $n$ componenti e $X$ è il sottoinsieme dello spazio euclideo $\mathbb {R} ^{n}$ definito dai vincoli.

Lo spazio $X$ del dominio di $f$ è detto "spazio di ricerca" ed i suoi elementi sono le "soluzioni candidate" o "soluzioni possibili".

Minimi e massimi

Obiettivo della programmazione matematica è quindi quello di individuare il punto $x$ nel dominio della funzione obiettivo (cioè i valori da assegnare alle $n$ variabili decisionali) che, rispettando i vincoli, minimizza o massimizza il valore della funzione obiettivo.

Minimi e massimi locali

Grafico che mostra un massimo e due minimi relativi di una funzione, di cui uno è anche minimo assoluto.

Sia $A\subseteq \mathbb {R} ^{n}$ e sia $f\colon A\to \mathbb {R}$ una funzione. Un punto di minimo locale (o relativo) è un elemento $\mathbf {x} ^{\ast }\in A$ tale che esiste un $\delta >0$ per cui si ha $f\left(\mathbf {x} ^{\ast }\right)\leq f\left(\mathbf {x} \right)$ per ogni $\mathbf {x} \in A$ tale che $\left\Vert \mathbf {x} -\mathbf {x} ^{\ast }\right\Vert \leq \delta .$ Ossia, in "vicino" a $\mathbf {x} ^{\ast }$ tutti i valori della funzione sono maggiori o uguali al valore di $f\left(\mathbf {x} ^{\ast }\right)$. Il valore $f(\mathbf {x} ^{\ast })$ è detto valore del minimo locale.

Un punto di massimo locale (o relativo) è definito in modo simile.

Minimi e massimi assoluti

Sia $A\subseteq \mathbb {R} ^{n}$ e sia $f\colon A\to \mathbb {R}$ una funzione. Un punto di minimo globale (o assoluto) è un elemento $\mathbf {x} ^{\ast }\in A$ per cui si ha $f\left(\mathbf {x} ^{\ast }\right)\leq f\left(\mathbf {x} \right)$ per ogni $\mathbf {x} \in A.$ Ossia è un punto del dominio per il quale i valori che la funzione funzione assume negli altri punti sono tutti maggiori o uguali al valore di $f\left(\mathbf {x} ^{\ast }\right)$ che è detto valore del minimo assoluto.

Un punto di massimo globale (o assoluto) è definito in modo simile, cioè se tutti i valori assunti dalla funzione negli altri punti sono minori o uguali del valore nel massimo assoluto.

La programmazione matematica è suddivisa in più famiglie di problemi a seconda delle caratteristiche della funzione obiettivo, dei vincoli e quindi delle tecniche di approccio. In generale si distinguono tre categorie:

• Programmazione lineare caratterizzati da funzione obiettivo e vincoli lineari a valori in $\mathbb {R} ^{n}$;
• Programmazione lineare intera caratterizzati da funzione obiettivo e vincoli lineari a valori in $\mathbb {Z} ^{n}$;
• Programmazione non lineare caratterizzati da funzione obiettivo o vincoli non lineari.

Metodi numerici

Risolvere un problema di ottimizzazione matematica si riferisce – in questo contesto – a

• la trasformazione del problema originale in un problema equivalente,
• un metodo teorico la cui descrizione permette lo sviluppo di un algoritmo numericamente applicabile.

La scelta di una tecnica appropriata dipende da

• la natura della funzione obiettivo $f$, la sua regolarità (continuità, derivabilità), proprietà specifiche (parità, convessità), conoscenza dei vicini dei suoi estremi,
• I vincoli $A$ che caratterizzano l'insieme dei punti ammissibili.

Semplificazioni

Il problema di origine è sostituito con un problema equivalente. Per esempio, con un cambiamento di variabili per suddividere il problema in sottoproblemi o la sostituzione di incognite per ridurne il numero.

La tecnica dei moltiplicatori di Lagrange permette di superare alcuni vincoli; questo metodo equivale ad introdurre delle penalità crescenti man mano che il punto si avvicina ai vincoli. L'algoritmo dei moltiplicatori di Hugh Everett permette di aggiornare i valori dei moltiplicatori in modo coerente ad ogni iterazione per garantire la convergenza. Quest'ultimo ha anche generalizzato l'interpretazione di questi moltiplicatori per applicarli a funzioni che non sono né continue né derivabili.

Ricerca degli zeri del gradiente

Numerosi metodi e algoritmi per il calcolo di uno zero di una funzione possono essere usati per trovare uno zero della derivata di $f$ (alcuni sono specifici di funzioni di una variabile) o del suo gradiente $\mathbf {\nabla } f$. Si applicano validamente in situazioni in cui i vincoli su $A$ rimangono inattivi.

Tutti questi metodi sono sviluppati nell'ambito di un processo iterativo.

Questi approcci possono soffrire di qualche limite. In particolare:

• La funzione deve essere sufficientemente regolare (almeno localmente) per essere derivabile (o doppiamente derivabile) per accedere alla matrice hessiana o ad una sua approssimazione.
• Non è sempre possibile esprimere esplicitamente il gradiente della funzione obiettivo.
• Le condizioni iniziali devono essere fissate prima dell'avvio del processo iterativo. La scelta iniziale può influenzare considerevolmente il risultato (divergenza dal processo iterativo). I metodi che convergono rapidamente sono generalmente più sensibili al riguardo.
• In alcuni casi, la velocità di convergenza può essere disastrosa: iterazioni successive si susseguono faticosamente (si parla allora di "stagnazione") lungo una stretta valle (funzione di Rosenbrock).
• Se la soluzione ottenuta è davvero un estremo (dopo aver verificato che non è un punto di sella), esso può anche essere locale.

Caso particolare: quando $f$ è polinomiale di grado 2 nei suoi argomenti (forma quadratica e lineare) e senza vincolo, annullare il gradiente è come risolvere un sistema lineare.

Classificazione JEL

La classificazione del Journal of Economic Literature pone la programmazione matematica, le tecniche di ottimizzazione e i relativi argomenti nelle sottocategorie JEL:C61-C63.

Bibliografia

• (EN) Reiner Horst, Panos M. Pardalos, eds. (1995): Handbook of Global Optimization, Kluwer Academic Publishers, ISBN 0-7923-3120-6
• (EN) Jonas Mockus, William Eddy, Audris Mockus, Linas Mockus, Gintaras Reklaitis (1997): Bayesian Heuristic Approache to Discrete and Global Optimizationn, Kluwer, ISBN 0-7923-4327-1
• (EN) Hector O. Fattorini (1999): Infinite dimensional optimization and Control theory, Cambridge University Press, ISBN 0-521-45125-6
• (EN) Stephen Boyd, Lieven Vandenberghe (2004): Convex Optimization, Cambridge University Press. ISBN 0-521-83378-7, disponibile anche in PDF.
• (EN) Aleksander Schrijver (1986): Theory of Linear and Integer Programming, J.Wiley, ISBN 0-471-90854-1
• (EN) Evgenij S. Levitin (1994): Perturbation Theory in Mathematical Programming and its Applications, J.Wiley, ISBN 0-471-93935-8

Voci correlate

• Algoritmo del simplesso
• Programmazione lineare
• Metodo dei minimi quadrati
• Metodo dei moltiplicatori di Lagrange
• Problema di ottimizzazione
• Ottimizzazione stocastica

Collegamenti esterni

Questa pagina sarà elencata nella seguente categoria una volta spostata nel namespace principale.

Categoria:

• Ottimizzazione