A diffusion based high performance algorithm for continuous and discrete global optimization

Optimization is ubiquitous in various fields of Science and Engineering, providing an excellent tool for tackling complex problems. The ability of modelling such complexity often leads to Global Optimization Problems, which are problems that classical gradient based (local) optimization algorithms — such as gradient descent — fail to solve efficiently. The rugged landscape of cost/reward functions poses, in fact, several challenges for algorithms that perform optimization by employing information on local structure of the function, that could yield therefore to solutions that are optimal only locally. Moreover, in real world scenarios, optimization problems may be represented by functions that are not differentiable, and that are therefore unfeasible from the perspective of a gradient informed optimization algorithm. We propose a — highly parallel and GPU compatible — novel approach for solving such problems, based on the physical intuition that, during the diffusion of heat on an unbounded medium, heat travels from hot to colder areas; imagining therefore objective functions as temperature profiles in Heat Equation Initial Value Problems, this procedure smooths those local optima which are less significative in terms of magnitude, and therefore less desirable as solutions, providing — moreover — a regularizing effect that enables the definition of a weaker notion of gradient, thus making gradient based optimization a viable choice for traditionally non differentiable functions. First, we provide a theoretical framework to describe in a formal manner the smoothing properties of Heat Diffusion in objective functions and prove a form of continuity between relaxed functions and solutions. Then we provide a description of the algorithm, both from a theoretical and from a numerical perspective. After presenting two benchmarks (with features that are challenging for classical gradient based optimization algorithms) we extend the theory in order to characterize, effectively, the same heuristic on discrete spaces, that would in principle lack of the basic properties to describe Heat Diffusion. The discretization of the method is, finally, tested on the famous Maximum Cut Problem, providing interesting results if compared to the SOTA algorithm for its solution. We conclude our investigation proposing possible improvements, and possible directions in the field of Global Optimization.

L’ottimizzazione é pervasiva in vari campi della Scienza e dell’Ingegneria, in quanto fornisce uno strumento eccellente per affrontare problemi complessi. L’abilità di modellare tale complessità porta spesso ad avere Problemi di Ottimizzazione Globali, i quali sono problemi che gli algoritmi di ottimizzazione (locale) classici basati su gradiente — come la discesa del gradiente — non sono in grado di risolvere efficientemente. La natura ruvida del profilo delle funzioni di costo/ricompensa pone, infatti, diverse sfide agli algoritmi che effettuano ottimizzazione sfruttando informazione riguardante la struttura locale della funzione, che potrebbero quindi risultare in soluzioni che sono ottime solo localmente. Inoltre, negli scenari del mondo reale, i problemi di ottimizzazione potrebbero essere rappresentati da funzioni non differenziabili, che sono quindi irrisolvibili dal punto di vista di un algoritmo di ottimizzazione informato dal gradiente. Proponiamo dunque un nuovo approccio — altamente parallelo e compatibile con GPU — per risolvere tali problemi, basato sull’intuizione fisica per cui, durante la diffusione di calore su un mezzo infinito, il calore viaggia dalle aree calde a quelle fredde; immaginando dunque le funzioni obiettivo come profili di temperatura in un Problema al Valore Iniziale per l’equazione del calore, questa procedura smussa quegli ottimi locali che sono meno significativi in termini di entità, e quindi soluzioni meno desiderabili, fornendo — inoltre — un effetto regolarizzante che induce la definizione di una nozione più debole di gradiente, rendendo dunque gli algoritmi di ottimizzazione basati su gradiente una scelta percorribile per funzioni non differenziabili in senso classico. In primo luogo, forniamo un ecosistema teorico per descrivere in maniera formale le proprietà smussanti della diffusione del calore a dimostriamo una forma di continuità tra funzioni rilassate e soluzioni. In seguito forniamo una descrizione dell’algoritmo, sia da un punto di vista teorico che numerico. Dopo aver presentato due benchmark (con proprietà sfidanti per gli algoritmi di ottimizzazione classici basati su gradiente) estendiamo la teoria in modo da caratterizzare, efficacemente, la stessa euristica su spazi discreti, che in linea di principio mancherebbero delle proprietà basilari per descrivere la diffusione di calore. La discretizzazione del metodo é, infine, testata sul celebre Problema del Maximum Cut, fornendo risultati interessanti se comparati con l’algoritmo allo stato dell’arte per la sua risoluzione. Concludiamo la nostra analisi proponendo possibili miglioramenti e possibili direzioni nel campo dell’ottimizzazione globale.