Computational Complexity of Adaptive Algorithms in Monte Carlo Optimization (Math Programming, Stochastic Analysis).

Abstract

This dissertation examines the complexity of a class of adaptive Monte Carlo algorithms used to solve convex programs. We define a measure of computational complexity involving the distribution of the number of iterations needed to achieve a solution within a specified error. This error is the difference between the obtained solution and the optimum. A conical convex program is then a stochastic worst case according to this measure. Finally, applying the complexity measure to the stochastic worst case provides an upper bound on complexity as a function of problem dimension. The analysis yields sufficient conditions for a Monte Carlo algorithm to have a linear bound on complexity as a function of dimension. It also provides confidence intervals for the true optimum in terms of observed performance of the algorithm. We analyze the complexity of two new Monte Carlo algorithms: a conceptual Pure Adaptive Search and an implementable Adaptive Mixing Algorithm. We show that the complexity of Pure Adaptive Search has a bound that is linear in dimension for convex programs. We experimentally approximate a linear bound on the complexity of the Adaptive Mixing Algorithm for a subset of convex programs. The advantages and disadvantages of these two algorithms clarify some of the conditions and results of the analysis. Furthermore, the Adaptive Mixing Algorithm is a first step in using this analysis to design a practical algorithm with linear complexity in dimension.