Enhanced Ordinal Optimization: A Theoretical Study And Applications

Ordinal optimization is an important tool to deal with simulation-based optimization problems. This dissertation studies several fundamental issues on the conventional ordinal optimization that are raised in practice: How to deal with multiple objective functions? How to deal with the constraint of limited memory space? How to compare the selection rules in an easy way and find the best one for a given problem to improve the efficiency of ordinal optimization? How to explain the good application results of ordinal optimization in deterministic complex optimization? To address these issues, the enhanced ordinal optimization is proposed. The major contributions are as follows.1) Define the concept of layers to introduce the order among the solution candidates of multi-objective optimization. The ideas of ordinal comparison and goal softening in the conventional ordinal optimization are extended to the case of multiple objective functions. It is proven that the observed layers converge to the corresponding true layers exponentially fast as the number of simulation increases. Define the ordered performance curve in the multi-objective case to classify the multi-objective optimization problems according to the difficulty to solve. A regression function is used to quantify the size of the selected set. As a demonstration, the values of the coefficients in the regression function are tabulized for the case of two-objective optimization problems. The numerical results show that by focusing on the selected set one can usually save the computing budget by at least one order of magnitude.2) The concept of descriptive complexity is used to mathematically formulate the strategy optimization with the constraint of limited memory space. A method based on the ordered binary decision diagram is proposed to calculate the upper bound of the descriptive complexity, and is used to construct simple strategies. Other methods are usually based on heuristics orintuition. The method proposed in this dissertation can better utilize the limited memory space. In the famous benchmark problem of team decision, the Witsenhausen counterexample, the proposed sampling method is combined with ordinal optimization. With minor performance degradation, the combined method finds a strategy with a 40-fold save in the descriptive length comparing with the best-so-far strategy.3) Regression functions are proposed to approximate the selection sizes of different selection rules. This supplies an easy way to compare the selection rules and find the best one for the given optimization problem so that the performance of ordinal optimization can be improved. Three properties of the good selection rules are proven theoretically and justified by experiments: no elimination, global comparison, and using the mean value of the observation to evaluate the designs. To facilitate the practical application, some simple rules are summarized to indicate the optimal selection rule among the ones known so far, under different circumstances. 4) Through clearly describing the uncertainties in stochastic simulation optimization and deterministic complex optimization, a unified formulation is proposed for the two types of optimization problems. Based on the concept of descriptive complexity, the equivalence between the two types of problems with respect to the unpredictability is shown. It is shown that as long as the design space is extremely large, and it is time-consuming to accurately evaluate the objective function, then the two types of problems are equivalent to ordinal optimization from an engineering viewpoint, and the selection sizes in both problems can be calculated through a common regression function.