Metodi numerici senza derivate per problemi di ottimizzazione black-box con variabili miste intere

In questa tesi si è voluto approfondire la risoluzione numerica di una particolare classe di problemi di ottimizzazione i cosiddetti problemi “black-box” con variabili miste intere. Il nome “black-box” deriva dal fatto che la funzione obiettivo agisce come una scatola nera, è possibile cioè studiarne il comportamento analizzando gli input e gli output, senza conoscerne il suo funzionamento interno. Spesso queste difficoltà derivano dal fatto che questi problemi sono ottenuti da procedure numeriche o mediante misurazioni sperimentali. Questi sono spesso caratterizzati dalla mancata conoscenza delle derivate della funzione obiettivo e dall'elevato costo computazionale della sua valutazione di funzione. Questo tipo di problemi sono molto frequenti nelle applicazioni. In questa tesi abbiamo analizzato numericamente il problema LEED (Low Energy Electron Diffraction) un vero e proprio problema “black-box” derivante dallo studio della struttura superficiale in scala atomica. Data la frequenza di questi tipi di problemi è stata sviluppata una classe di metodi numerici, detta “derivate-free”, ossia che non fa uso delle derivate della funzione obiettivo. I vantaggi di questi metodi sono l'affidabilità, la semplicità e la loro flessibilità: funzionano bene nella pratica e sono facili da implementare, inoltre hanno bisogno di pochi parametri. Tra i metodi derivative free abbiamo analizzato tre algoritmi noti in letteratura: BFO, DFL e NOMAD. Questi tre metodi cercano di trovare le soluzioni di minimo locale del problema partendo da un dato punto iniziale e andando a sondare i punti vicini seguendo delle direzioni che li caratterizzano. Del BFO è stata introdotta una nuova versione BFO-Relax che sfrutta la strategia di rilassamento delle variabili. Tutti i metodi sono stati analizzati sia dal punto di vista algoritmico che numerico su un'ampia classe di problemi test e sul problema reale LEED.