Leveraging Space-Filling Curves and the DIRECT Algorithm. A Novel Approach to Derivative-Free Multi-Dimensional Global Optimization

Bachelor Thesis from the year 2018 in the subject Mathematics - Applied Mathematics, Nanyang Technological University, language: English, abstract: This study aims to focus on a new approach to the Dividing Rectangles or DIRECT algorithm, which is used to solve multi-dimensional global optimization problems. It also delves into the resolution of DIRECT's combinatorial complexity in higher dimensions by transforming the problem domain into its one-dimensional equivalent.

Many real-world problems involve multivariate global optimization which can be difficult to solve. In this report, a new approach to the Dividing Rectangles or DIRECT algorithm for solving multi-dimensional global optimization problems with bounds and a real-valued objective function, is discussed. DIRECT is a variation of the standard Lipschitzian optimization omitting the requirement of having to specify a Lipschitz constant; by viewing the Lipschitzian constant as a weighting parameter for indicating the emphasis to be placed on global versus local search. Typically, this constant is not so small in standard Lipschitz approaches, since the constant needs be at least as large as the maximum rate of change of the objective function; which forces a higher emphasis on global search and thus, results in a slower convergence. However, DIRECT enables operation at both global and local level by concurrently searching using all possible constants. The global part of the algorithm figures out the basin of convergence of the optimum, which the local part of the algorithm can suitably exploit. This justifies the fast convergence of DIRECT in computing the approximate minimum with the guaranteed precision. One major drawback of DIRECT is its combinatorial complexity in higher dimensions where DIRECT often takes many more function evaluations to find a good approximation of the global minimum. One method to resolve this difficulty is to transform the problem domain into its one-dimensional equivalent. This approach is demonstrated in this report using space filling curves, to reduce the multiextremal optimization problem to the minimization of a univariate function. In this case, the Hölder continuity of space filling curves has been exploited to solve global optimization problems.