An Investigation of Model-Based Approaches in Solving a Variety of Global Optimization Problems

Abstract

Model-based optimization methods are a class of random search methods that are useful for solving global optimization problems. These types of methods have shown significant empirical success in solving a multitude of real-world problems in which the objective functions are often highly ill-structured. In this dissertation, we propose new approaches to incorporate and extend model-based methods with the goal of promoting them for future applications.

Part I: We propose a novel algorithm for solving the classical P-median problem. The essential aim is to identify the optimal extended penalty multipliers corresponding to the optimal solution of the underlying problem. For this, we first explore the structure of the data matrix in the P-median problem to recast it as another equivalent global optimization problem over the space of the extended penalty multipliers. Then, we present a model-based algorithm to find the extended penalty multipliers corresponding to the optimal solution of the original P-median problem.

Part II: For general multi-objective optimization problems, we propose a new performance metric called domination measure to measure the quality of a solution, which can be intuitively interpreted as the size of the portion of the solution space that dominates that solution. As a result, we reformulate the original multi-objective problem into a stochastic single-objective one and propose a model-based approach to solve it. We show that an ideal version algorithm of the proposed approach converges to a representative set of the global optima of the reformulated problem. We also investigate the numerical performance of an implementable version algorithm by comparing it with numerous existing multi-objective optimization methods on popular benchmark test functions.

Part III: The fields of research for both stochastic optimization and multi-objective optimization are well studied and highly developed. Surprisingly, a paucity of research has attempted to explore the combination of both stochastic and multi-objective optimization. Therefore, we propose a model-based method for solving optimization problems in which a solution performance is measured by multiple objectives that are subject to stochastic noise. Since the objective functions cannot be evaluated directly, the values are estimated via simulation. The proposed method integrates a new allocation heuristic within the model-based framework. This heuristic improves the efficiency of the method by allocating the majority of the computational budget to solutions that play a crucial role in updating the parameters of the sampling distribution used to facilitate the search process. The proposed method is designed to deal with multiple objectives and uncertainty simultaneously.