Ottimizzazione (matematica)

branca della matematica applicata
(Reindirizzamento da Programmazione matematica)

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.

Un esempio semplice di problema di ottimizzazione consiste nel massimizzare o minimizzare una funzione reale di una variabile reale su un dato intervallo dell'asse. La generalizzazione della teoria e delle tecniche di ottimizzazione ad altre formulazioni costituisce una vasta area della 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.

DescrizioneModifica

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

Data: una funzione   da un insieme   nei numeri reali
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 chiamata funzione obiettivo o funzione 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 dello spazio 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 di algoritmi di risoluzione efficienti in quanto, generalmente, lo spazio di ricerca ha una cardinalità 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 programmazione continua e discreta in funzione del fatto che lo spazio di ricerca   sia continuo o discreto. Nell'ambito della programmazione continua, con spazio di ricerca  , distinguiamo tra programmazione lineare, se la funzione funzione obiettivo e vincoli sono lineari, e programmazione non lineare altrimenti. Un'ulteriore classificazione può essere effettuata distinguendo problemi di programmazione statica e problemi di programmazione dinamica. 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.

Minimi e massimiModifica

 Lo stesso argomento in dettaglio: Massimo e minimo di una funzione.

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.

Minimi e massimi localiModifica

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

Sia   e sia   una funzione. Un punto di minimo locale (o relativo) è un elemento   tale che esiste un   per cui si ha   per ogni   tale che   Ossia, in "vicino" a   tutti i valori della funzione sono maggiori o uguali al valore di  . Il valore   è detto valore del minimo locale.

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

Minimi e massimi assolutiModifica

Sia   e sia   una funzione. Un punto di minimo globale (o assoluto) è un elemento   per cui si ha   per ogni   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   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:

Metodi numericiModifica

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  , la sua regolarità (continuità, derivabilità), proprietà specifiche (parità, convessità), conoscenza dei vicini dei suoi estremi,
  • I vincoli   che caratterizzano l'insieme dei punti ammissibili.

SemplificazioniModifica

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[1].

Ricerca degli zeri del gradienteModifica

Numerosi metodi e algoritmi per il calcolo di uno zero di una funzione possono essere usati per trovare uno zero della derivata di   (alcuni sono specifici di funzioni di una variabile) o del suo gradiente  . Si applicano validamente in situazioni in cui i vincoli su   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   è polinomiale di grado 2 nei suoi argomenti (forma quadratica e lineare) e senza vincolo, annullare il gradiente è come risolvere un sistema lineare.

Classificazione JELModifica

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

NoteModifica

  1. ^ (EN) Hugh Everett, Generalized Lagrange multiplier method for solving problems of optimum allocation of resources, in Operations Research, vol. 11, n. 3, 1963, pp. 399-417.

BibliografiaModifica

  • (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 correlateModifica

Altri progettiModifica

Collegamenti esterniModifica

Controllo di autoritàThesaurus BNCF 21954 · GND (DE4043664-0
  Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica