MAS: Ottimizzazione Locale Senza Derivate – La Mia Guida Pratica e Affascinante!
Ciao a tutti, appassionati di numeri e algoritmi! Vi siete mai trovati di fronte a un problema di ottimizzazione talmente ingarbugliato da non sapere da che parte iniziare, soprattutto se le derivate sono un miraggio o un incubo da calcolare? Beh, oggi voglio parlarvi di una soluzione che ho scoperto e che trovo semplicemente geniale: si chiama Model-and-Search (MAS). È un algoritmo di ottimizzazione locale derivative-free (cioè, non ha bisogno delle derivate!) che promette di scovare i minimi locali di una funzione con un budget limitato di valutazioni. E credetemi, fa il suo lavoro egregiamente!
Cos’è questo Model-and-Search (MAS) di cui tutti parlano?
Immaginate di dover trovare il punto più basso in una vallata (un minimo locale) avendo a disposizione solo una mappa molto generale e la possibilità di misurare l’altitudine solo in alcuni punti specifici. MAS fa proprio questo: cerca di ottimizzare una funzione deterministica all’interno di un dominio definito da limiti (box-bounded), il tutto senza conoscere le derivate della funzione. Questo è un enorme vantaggio quando abbiamo a che fare con funzioni “scatola nera” (black-box), dove l’unica cosa che possiamo fare è fornire un input e osservare l’output, oppure quando calcolare le derivate è troppo costoso o complesso.
L’obiettivo principale di MAS è quello di migliorare il valore della soluzione corrente (l’incumbent) combinando una serie di tecniche intelligenti. Tra queste, spiccano la stima del gradiente (anche se non lo calcola direttamente, lo approssima!) e la costruzione e ottimizzazione di modelli quadratici. E qui viene il bello: MAS ha un approccio innovativo basato sulla sensibilità per costruire un modello quadratico incompleto quando non ci sono abbastanza punti per crearne uno completo. Questo modello surrogato, anche se incompleto, è abbastanza furbo da guidare la ricerca verso zone promettenti.
Come funziona la magia di MAS? Un mix di “Modello” e “Ricerca”
MAS, come suggerisce il nome, ha due anime: quella basata sui modelli (model-based search) e quella di ricerca diretta (direct search). Non si fossilizza su un unico approccio, ma li combina in modo flessibile. Pensatelo come un esploratore che usa sia mappe dettagliate (i modelli) quando disponibili, sia l’intuito e l’osservazione diretta del terreno (la ricerca diretta) quando le mappe scarseggiano.
Ecco alcuni dei suoi “trucchi del mestiere”:
- Riutilizzo intelligente dei punti: Prima di valutare nuovi punti (che è un’operazione costosa), MAS cerca di spremere ogni goccia di informazione dai punti già valutati in precedenza. Economia ed efficienza prima di tutto!
- Costruzione di modelli adattiva: Se i punti disponibili lo permettono, MAS costruisce un modello (lineare o quadratico, completo o incompleto) della funzione obiettivo. Questo modello viene poi ottimizzato per suggerire un nuovo punto candidato promettente. La novità sta nel costruire modelli quadratici incompleti dando priorità ai termini con maggiore “sensibilità” sull’obiettivo, approssimata usando le componenti del gradiente del modello.
- Line search: Se MAS identifica una direzione di discesa promettente, non se la lascia scappare! Esegue una line search, ovvero esplora lungo quella direzione per trovare il punto migliore possibile.
- Formazione di una base positiva: Nelle iterazioni “sfortunate” in cui non si trova un miglioramento, MAS non si perde d’animo. Si assicura che i punti valutati formino una “base positiva” attorno al miglior punto noto. Questo è un dettaglio tecnico fondamentale che garantisce la convergenza dell’algoritmo verso un punto di Karush-Kuhn-Tucker (KKT), che per i problemi con vincoli di box è un candidato a essere un minimo locale.
A differenza degli algoritmi basati su regioni di fiducia (trust-region) che aggiornano un raggio in base all’accuratezza del modello, MAS è più flessibile sulla geometria dei punti e sulla forma e lunghezza del modello costruito. E se non si riesce a costruire un modello surrogato, entra in gioco la componente di ricerca diretta, ma con un set di direzioni di ricerca che mira sia a trovare un punto migliorativo sia a facilitare la costruzione di un modello lineare futuro.
L’algoritmo è stato testato su una vasta collezione di 501 problemi pubblici, con dimensioni e complessità variabili, e i risultati sono stati strabilianti: MAS si comporta bene indipendentemente dalla convessità o dalla “liscezza” (smoothness) del problema. Questo lo rende un candidato ideale, per esempio, per rifinire soluzioni ottenute da algoritmi con una componente di ricerca globale più ampia.
I mattoncini di MAS: Come si costruisce il successo
Scendendo un po’ più nel dettaglio, ogni iterazione di MAS ha due obiettivi principali. Il primo è, ovviamente, trovare un punto che migliori la soluzione corrente. Per farlo, esegue sequenzialmente diversi passaggi algoritmici. Se uno di questi passaggi identifica un punto migliorativo, l’algoritmo esegue una line search lungo quella direzione e l’iterazione si conclude con successo, saltando i passaggi rimanenti.
Il secondo obiettivo è costruire un modello che predica un potenziale punto migliorativo. Lo scopo è avere il punto migliore al centro della “scatola di ricerca” per predire meglio il suo vicinato. Se il modello non riesce a predire un miglioramento, l’obiettivo finale dell’iterazione è assicurarsi che ci sia una base positiva attorno al miglior punto conosciuto. Questa formazione di una base positiva in un’iterazione infruttuosa è cruciale per la convergenza.
MAS utilizza diverse routine ausiliarie, come:
- Truncate Step: Assicura che le valutazioni della funzione avvengano solo all’interno dei limiti della regione ammissibile.
- Line Search: Valuta i punti candidati, verificando che non siano troppo vicini a punti già valutati e che soddisfino un criterio di decremento minimo. Se trova un punto migliorativo, continua lungo quella direzione.
- Linear Independence: Identifica un sottoinsieme di vettori linearmente indipendenti da un dato set, preferendo quelli con norma minore (più vicini al punto corrente, quindi più informativi per modelli locali).
- Form Basis (Interior/Boundary): Se non ci sono abbastanza vettori linearmente indipendenti per formare una base, questa routine ne aggiunge di nuovi, gestendo diversamente i casi in cui il punto corrente è interno o sul bordo del dominio.
- Build Model (Linear/Quadratic): Costruisce modelli interpolanti (da lineari completi a quadratici incompleti o completi) a seconda dei punti disponibili, usando l’approccio basato sulla sensibilità per i termini quadratici.
- Positive Basis: Se non si trovano miglioramenti, verifica e, se necessario, completa il set di punti per formare una base positiva.
Due routine principali orchestrano questi passaggi: MAS Neighborhood, che utilizza i punti valutati vicini al punto corrente per costruire modelli e cercare miglioramenti, e MAS All, che occasionalmente utilizza tutti i punti valutati per costruire modelli, accelerando la convergenza specialmente per problemi “ben comportati” (lisci).
L’algoritmo principale, Model-and-Search, inizia con un set iniziale di punti, li valuta, e poi itera. Ogni iterazione decide se lanciare MAS All o MAS Neighborhood. Il raggio di ricerca (r_k) viene aggiornato: diminuisce nelle iterazioni infruttuose e aumenta in quelle fruttuose, con un occhio di riguardo se si trovano più punti migliorativi o se il modello predice miglioramenti molto vicini al punto corrente.
Perché MAS brilla più degli altri? I suoi superpoteri
MAS non è solo un altro algoritmo DFO. La sua forza risiede nella combinazione intelligente di diverse strategie. La capacità di costruire modelli quadratici incompleti quando i dati scarseggiano, dando priorità ai termini più “sensibili”, è una vera chicca. Questo permette di sfruttare al meglio le informazioni disponibili, anche quando sono poche.
Inoltre, la gestione flessibile del raggio di ricerca e la capacità di passare da una strategia basata su modelli a una di ricerca diretta (e viceversa) lo rendono estremamente adattabile. Non si incaponisce su un’unica strada, ma sceglie quella più promettente in base alla situazione. E la garanzia di convergenza a un punto KKT, sotto ipotesi blande (funzione continuamente differenziabile e limitata inferiormente), gli dà una solida base teorica.
MAS alla prova del nove: L’esempio del “cammello a sei gobbe” e oltre
Per farvi capire meglio come lavora MAS, prendiamo un esempio classico: la funzione “six-hump camel” (camel6). È una funzione a due variabili con sei minimi locali, di cui due globali. Partendo da un punto casuale, MAS è riuscito a trovare uno dei minimi globali in meno di 60 valutazioni della funzione! L’algoritmo ha iniziato esplorando con un raggio ampio, poi, una volta identificata una regione promettente, ha ristretto il raggio per una ricerca locale più intensa e raffinata. Le figure nel paper originale mostrano magnificamente questa danza tra esplorazione e sfruttamento.
Ma non si è fermato qui. MAS è stato messo alla frusta su un set di 501 problemi di test, che includono funzioni continue e discontinue, somme di quadrati, polinomi, funzioni trigonometriche, esponenziali, logaritmiche, convesse e non convesse, con un numero di variabili da 1 a 300. Un vero e proprio campo di battaglia!
Numeri che parlano: MAS contro i campioni
E come se l’è cavata MAS contro altri solutori DFO noti come DFO, PATTERN, IMFIL, NOMAD e BOBYQA? In una parola: egregiamente. Su tutto l’arco delle valutazioni della funzione (fino a un budget di 300), MAS ha superato gli altri, risolvendo una frazione maggiore di problemi.
Ad esempio, con una tolleranza di (10^{-6}), dopo 100 valutazioni, MAS risolveva circa il 35% dei problemi, contro il 29-32% dei suoi migliori competitor (NOMAD e BOBYQA). Con il budget massimo, MAS arrivava al 46%, mantenendo il vantaggio. Questa superiorità si è vista sia su problemi convessi che non convessi, e sia su problemi lisci che non lisci. È interessante notare che su problemi non convessi, dove NOMAD (grazie alle sue capacità multistart) a volte trova ottimi locali migliori con budget elevati, MAS si è distinto per l’efficienza con budget limitati (meno di 100 valutazioni), il che è cruciale se lo si usa come “rifinitore” locale in un framework di ottimizzazione globale.
Anche l’impatto della dimensionalità è stato analizzato. Come c’era da aspettarsi, tutti gli algoritmi DFO soffrono la “maledizione della dimensionalità”. Tuttavia, MAS si è dimostrato il migliore anche in questo scenario, specialmente per problemi a bassa dimensionalità (1-10 variabili), risolvendone il 78% entro 300 valutazioni. Per dimensioni più elevate (11-300 variabili), dove i metodi basati su modelli tendono ad avere un vantaggio, MAS ha comunque mantenuto la leadership.
Esperimenti con varianti di MAS hanno anche dimostrato che la componente di ricerca basata su modelli è essenziale per le sue prestazioni, e che la routine MAS All (che usa tutti i punti per costruire modelli) contribuisce a un ulteriore miglioramento, specialmente su problemi lisci.
Cosa ci portiamo a casa da questa avventura con MAS?
Beh, per me MAS è una vera boccata d’aria fresca nel mondo dell’ottimizzazione derivative-free. La sua capacità di combinare stima del gradiente, costruzione di modelli quadratici (anche incompleti ma intelligenti) e ricerca diretta, il tutto riutilizzando efficientemente le informazioni, lo rende uno strumento potente e versatile.
È particolarmente bravo nel rifinire soluzioni locali con un numero limitato di valutazioni della funzione, indipendentemente dalla convessità o dalla liscezza del problema. La sua convergenza garantita a un punto KKT gli dà anche una certa autorevolezza teorica.
Personalmente, sono entusiasta delle potenzialità di MAS. Gli autori del paper suggeriscono che il lavoro futuro includerà l’incorporazione di MAS come algoritmo di ricerca locale all’interno di un framework di ottimizzazione globale. Non vedo l’ora di vedere cosa combinerà! Quindi, la prossima volta che vi imbattete in un problema di ottimizzazione ostico e senza derivate a portata di mano, date una chance a Model-and-Search. Potrebbe sorprendervi!
Fonte: Springer