Questa vocesull'argomento matematica applicata è solo unabbozzo.
L'ottimizzazione (oprogrammazione matematica,PM) è una branca dellamatematica applicata che studia teoria e metodi per la ricerca deipunti di massimo e minimo di unafunzione matematica all'interno di un dominio specificato.
Un esempio semplice di problema di ottimizzazione consiste nel massimizzare o minimizzare una funzione reale di una variabile reale su un dato intervallo. La generalizzazione della teoria e delle tecniche di ottimizzazione ad altre formulazioni costituisce una vasta area della matematica applicata. Più in generale, l'ottimizzazione comprende la ricerca dei "migliori valori disponibili" di una certa funzione obiettivo in un determinato dominio (o input), e considera una varietà di diversi tipi di funzioni obiettivo e diversi tipi di domini.
Un problema di ottimizzazione, talvolta dettodi programmazione matematica, può essere formulato nel seguente modo:
- data unafunzione
da uninsieme
, - determinare un elemento
tale che
per ogni
("minimizzazione") o tale che
per ogni ("massimizzazione").
Poiché punti di massimo per una funzione
corrispondono a punti di minimo per la funzione
, non è restrittivo formulare problemi di ottimizzazione in termini di minimizzazioni.
La funzione viene generalmente chiamatafunzione obiettivo ofunzione di costo. L'insieme
, detto generalmente spazio di ricerca, può essere un insieme discreto o continuo. In molti casi di rilevante importanza applicativa, può essere identificato con un sottoinsieme dellospazio euclideo
definito in termini di vincoli, ovvero uguaglianze o disuguaglianze che gli elementi di 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 dialgoritmi di risoluzione efficienti in quanto, generalmente, lo spazio di ricerca ha unacardinalità tale da precludere la possibilità di ricerche esaustive. A titolo di esempio se è descritto da
variabili, ciascuna delle quali può assumere
valori, lo spazio di ricerca contiene
elementi. Una ricerca esaustiva risulta pertanto inattuabile ed è necessario ricorrere ad algoritmi che permettano di sfruttare in modo efficace eventuali proprietà della funzione e dello spazio di ricerca.
I problemi di ottimizzazione possono essere classificati in base alle principali caratteristiche dello spazio di ricerca e della funzione. In particolare, si distingue generalmente tra programmazionecontinua ediscreta in funzione del fatto che lo spazio di ricerca sia continuo o discreto. Nell'ambito della programmazione continua, con spazio di ricerca, distinguiamo tra programmazionelineare, se la funzionefunzione obiettivo e vincoli sono lineari, e programmazionenon lineare altrimenti. Un'ulteriore classificazione può essere effettuata distinguendo problemi di programmazionestatica e problemi di programmazionedinamica. Nell'ottimizzazione dinamica, alla formulazione precedentemente esposta viene aggiunta una variabile temporale dalla quale vengono a dipendere le quantità in gioco, ovvero lo spazio di ricerca e, eventualmente, la funzione obiettivo.
Obiettivo della programmazione matematica è quindi quello di individuare il punto
nel dominio della funzione obiettivo (cioè i valori da assegnare alle
variabili decisionali) che, rispettando i vincoli, minimizza o massimizza il valore della funzione obiettivo.
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 unalgoritmo numericamente applicabile.
La scelta di una tecnica appropriata dipende da:
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 deimoltiplicatori 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 diHugh 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[1].
Numerosi metodi ealgoritmi per il calcolo di uno zero di una funzione possono essere usati per trovare uno zero della derivata di (alcuni sono specifici difunzioni di una variabile) o del suogradiente
. Si applicano validamente in situazioni in cui i vincoli su rimangono inattivi.
Tutti questi metodi sono sviluppati nell'ambito di unprocesso 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 allamatrice 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 è unpunto di sella), esso può anche essere locale.
Caso particolare: quando è polinomiale di grado 2 nei suoi argomenti (forma quadratica elineare) e senza vincolo, annullare il gradiente è come risolvere un sistema lineare.
