Multi-scale search for black-box optimization : theory & algorithms

This thesis focuses on a special class of MP algorithms for continuous black-box optimization. Black-box optimization has been a recurrent subject of interest for decades, as many real-world applications can be modeled as black-box optimization problems. In particular, this research work studies algorithms that partition the problem's decision space over multiple scales in search for the optimal solution and investigates three central topics. Plenty of such algorithms have been proposed and analyzed independently. Furthermore, the theoretical analysis has been dominantly concerned with the asymptotic (limit) behavior of the algorithms and their convergence to optimal points, whereas finite-time behavior is more crucial in practice. Due to their systematic sampling of the decision space, the aforementioned algorithms are inherently exploratory. This prevents from using them effectively on computationally expensive optimization problems. The bulk of these algorithms has been tailored towards single-objective optimization, whilst in practice, most real-world problems involve the optimization of \emph{multiple} objectives. The present thesis refers to these algorithms as Multi-scale Search Optimization (MSO) algorithms and addresses the above issues as follows. First, a theoretical methodology is presented to \emph{consolidate} the analysis of MSO algorithms and study their \emph{finite-time} convergence based on three basic assumptions: i). local H\"{o}lder continuity of the objective function $f$; ii). partitions boundedness; and iii). partitions sphericity. Moreover, the worst-case finite-time performance and convergence rate of several leading MSO algorithms, viz. Lipschitzian optimization methods, Multilevel Coordinate Search (MCS), Dividing RECTangles (DIRECT), and optimistic optimization methods have been shown. Second, in order to deal with expensive optimization, an algorithm---referred to as the Naive Multi-scale Search Optimization (NMSO) algorithm---within the MSO framework is developed. When compared with other MSO algorithms, NMSO's exploitative search component is more dominant than its exploratory one. Besides preserving its asymptotically-consistent property, NMSO enjoys a finite-time convergence, which is generally difficult to establish for exploitation-biased algorithms. Along with its theoretical study, a numerical assessment of NMSO---comparing it with established multi-scale search algorithms such as MCS and DIRECT---has been conducted. Based on the results, NMSO demonstrates a better performance than the compared algorithms under limited (expensive) evaluation budget, particularly in problems with separability, multi-modality, and low dimensionality. This is in line with the Black-box Optimization Competition (BBComp) held at GECCO'15, where NMSO finished third out of twenty-eight competitors in solving 1000 black-box problems. Third, in order to expand the frontiers of multi-scale search algorithms, two MSO algorithmic instances are extended for multi-objective optimization: i). Multi-Objective DIviding RECTangles (MO-DIRECT); ii) Multi-Objective Simultaneous Optimistic Optimization (MO-SOO). Both of these algorithms are asymptotically convergent towards the Pareto front. Furthermore, based on the presented theoretical methodology to analyze MSO algorithms, an upper bound on the Pareto-compliant unary additive epsilon indicator is established as a function of the number of iterations. The bound is characterized by the objectives smoothness as well as the structure of the Pareto front with respect to its extrema. First time in the literature, a deterministic upper bound on a Pareto-compliant indicator has been presented for a solver of continuous multi-objective problems. Finally, to validate the efficacy of the proposed multi-objective MSO algorithms, a Black-box Multi-objective Optimization Benchmarking (BMOBench) platform is built around 100 multi-objective optimization problems from the literature, where the performance assessment is reported in terms of Pareto- and Non-Pareto-compliant data profiles. BMOBench can be employed as a comprehensive platform for benchmarking any multi-objective optimization algorithm. Besides the built platform, 300 bi-objective were used in comparing the proposed multi-objective MSO algorithms with the state-of-the-art algorithms. Based on the results, MO-SOO shows a performance on a par with the top performing algorithm, viz. SMS-EMOA and DMS, especially with limited number of function evaluations. Future work includes: i). breaking away from MSO's systematic sampling towards more adaptive/learning scheme; ii). handling large-scale problems and general constraints; and iii). employing indicator-based techniques for multi-objective MSO.Doctor of Philosophy (SCE