| Nested Partitions (NP) is a recently developed meta-heuristic method for solving large-scale optimization problems, when they are difficult to solve by exact algorithms such as mathematical programming algorithms. This thesis is concerned with enhancing the theoretical foundation of NP, and providing useful approaches to improve its performance and applicability.;The NP method partitions the solution space and concentrates the search on most promising regions, which are determined by the promising index calculated from sample solutions. The traditional promising index simply uses the best sample value in each region to decide which region to move to in the next iteration. This thesis aims at developing a more informative index, called statistical promising index, based on extreme value theory. It provides better accuracy and robustness than traditional index. It is also proved to have asymptotic properties, and is capable of quantifying the quality and reliability of each region and a move decision. The quantities are utilized to control the sample size of each region, and serve as early indicators of future algorithm performance. It further enables the calculation of statistical bounds, which prune unpromising regions and compensate for the lack of bounding procedure in NP. Deterministic optimization problems are tested, and numerical results demonstrate the effectiveness of proposed algorithms.;This thesis also proposes to predict the future performance of the NP method, based on the solutions obtained at the early iterations. The motivation is to provide guidelines to select a good NP algorithm setting from multiple candidates without running each to the end. Numerical tests show the accuracy of the proposed lower bound embedded prediction procedures.;Finally, this thesis applies NP to solve finite-horizon total-cost Markov decision processes with non-stationary policies. The global perspective of NP is combined with the local search power of sensitivity-based analysis. An intelligent partitioning approach is developed to determine the new partitions adaptively based on the information from previous iterations. It is vastly superior to the traditional partitioning schemes, which are decided beforehand when limited information is known. The proposed algorithm can provide good approximation of the optimum. |
