14/05/2021
La ricerca dell’ottimo accompagna praticamente tutte le nostre azioni. La classica query in Google Maps circa il percorso più rapido per raggiungere il nostro locale preferito ne è un esempio. E – per quanto di valore soggettivo – persino definire quale locale effettivamente preferiamo è in realtà un problema di ottimizzazione.
Soppesiamo variabili e parametri per la quasi totalità delle nostre scelte, pur spesso non associando questi problemi di ottimizzazione alla ricerca di una soluzione matematica. Inseguiamo il nostro punto di ottimo (il punto di minimo o il punto massimo), senza una reale consapevolezza del processo mentale che ci porta a considerarlo come tale.
Nella quarta lezione di Moxoff Academy, il Prof. Luca Formaggia (Full Professor in Numerical Analysis Dip. di Matematica al Politecnico di Milano e parte del Comitato Scientifico di Moxoff) ha illustrato – dal punto di vista della matematica – uno degli aspetti con cui siamo sicuramente più in confidenza nella nostra vita quotidiana: la ricerca di efficienza che pervade anche le nostre più semplici attività.
Applicazioni dei problemi di ottimizzazione
In campo produttivo e aziendale, i problemi di ottimizzazione sono all’ordine del giorno, in un’ottica di performance, di costi, di prezzi e di risparmio. Nel caso di una realtà industriale, ad esempio, minimizzare i costi di produzione o di manutenzione di un macchinario è fondamentale. Nel caso di un impianto di produzione, ridurre le emissioni è imprescindibile e normato dalla legge, oltre che un dovere sociale. Pensiamo, inoltre, alla continua ricerca della perfetta (o ottima) forma aerodinamica per automobili, imbarcazioni, o velivoli commerciali e militari.
Il Machine Learning (in italiano, Apprendimento Automatico) è esso stesso un’applicazione delle tecniche di ottimizzazione. L’apprendimento, infatti, si sostanzia nella capacità dell’algoritmo di minimizzare – in funzione dei dati di input – l’errore di stima dei valori di output. I metodi di ottimizzazioni per questa classe di problemi devono poter operare efficientemente in presenza di grandi quantità` di dati e, possibilmente, tenere conto delle loro proprietà` statistiche.
Come funzionano i metodi di ottimizzazione
I metodi di ottimizzazione matematica sono essenzialmente metodi iterativi, che mirano a far convergere la funzione obiettivo (cioè, ciò che si desidera ottimizzare) in un punto di minimo ottimale. Il punto minimo si distinguerà in punto di minimo locale e punto di minimo globale. La velocità di convergenza caratterizza il percorso che porta al raggiungimento del minimo cercato. Nella scelta dell’algoritmo a cui affidarsi, nell’ identificare il punto di minimo per iterazione, si valuta e si accetta inevitabilmente un trade off tra la velocità di convergenza e il costo del calcolo computazionale.
Metodi deterministici e algoritmi stocastici
I metodi deterministici per il calcolo dei diversi tentativi di iterazione sono i più noti e diffusi.. Si dividono in due macro categorie. Nei metodi di ricerca (Line Search) si sceglie ad ogni iterazione una direzione da seguire e lungo la quale avanzare verso il minimo. I più conosciuti sono il metodo del gradiente, il metodo del gradiente coniugato, il metodo del momentum, e i metodi di Newton e quasi-Newton. I metodi dell’area di confidenza (Trust Region), sono invece caratterizzati dalla scelta ad ogni passo iterativo di una regione di confidenza opportuno, all’interno della quale utilizzare un modello quadratico della funzione obiettivo, il cui minimo è il punto di partenza per l’iterazione successiva.
Nell’ambito di tecniche di apprendimento automatico basate su reti neurali (Deep Learning) si usano sovente i cosiddetti metodi stocastici, quali il metodo del gradiente stocastico. In tali metodi, il gradiente della funzione obiettivo viene approssimato ad ogni iterazione con il gradiente ottenuto considerando un campione casuale dei dati. Questo riduce il corso computazionale e introduce una stocasticità che può aiutare la ricerca del punto ottimale. Tra questa classe di metodi ricade anche il metodo ADAM, tra i più usati nel contesto del Deep Learning.
Metodi per minimi globali
I metodi citati in precedenza ricercano dei minimi locali. La ricerca di un minimo globale di una funzione generica è un problema computazionalmente difficile. Si possono usare diverse euristiche, tra le quali i metodi basati sulla evoluzione iterativa di un campionamento dello spazio dei parametri del problema. Per esempio gli algoritmi genetici.
Gli algoritmi genetici si riferiscono non più alla ricerca di un punto specifico, ma ad un gruppo di soluzioni potenziali (una popolazione) e per questo possono portare ad elevati costi computazionali. Sono caratterizzati dalle dinamiche di selection (una sorta di “selezione naturale” per trovare i candidati migliori), crossover (la combinazione di due selezioni) e mutation (la generazione di stringhe generiche casuali per l’esplorazione su uno spazio più ampio).
Ottimizzazione multi-obiettivo,
Nel caso in cui l’ottimizzazione si muova su più punti da ottimizzare gli uni in relazione agli altri, si mira ad individuare un insieme di soluzioni di minimo (il cosiddetto fronte di Pareto) tra cui scegliere la soluzione ottimale preferita, in base alla specifica esigenza da esaminare. Tutti i punti sul Fronte di Pareto delineano infatti soluzioni ugualmente ottimali (la cosiddetta ottimalità di Pareto). Un semplice esempio è il famigerato rapporto qualità / prezzo: sceglieremo il punto di ottimo in base alle nostre esigenze (miglior prezzo per la qualità desiderata).
Contattaci per ricevere ulteriori informazioni
