Efficient random algorithms for constrained global and convex optimization.

Abstract

Several Markov chain sampling algorithms, including the Hit-and-Run algorithm, are unified within the framework of random walks taking steps inside balls centered at the current point. Several new Markov chain sampling algorithms are developed within this theoretical framework. Using existing results for the complexity of one random ball walk, the theory of Markov chain conductance is used to derive complexity results for the class of random ball walks, including the polynomiality of Hit-and-Run over certain convex regions. A technique based on filtering Markov chains is used to extend these results to any well-rounded convex body. These complexity bounds are validated through a series of empirical trials and statistical tests. Further results are presented bounding the complexity of generating samples from arbitrary distributions by filtering random ball walks. Using a result from coupling theory, we demonstrate how the random ball walks may be used to generate samples having exactly a specified distribution. The random ball walk sampling algorithms are applied to develop the first polynomial time implementation of the Pure Adaptive Search optimization algorithm for convex programming, as well as a quasi-polynomial implementation of the Adaptive Search algorithm. A new random optimization algorithm, called Relaxed Adaptive Search, is developed on the basis of relaxing the feasible region to obtain a region more suitable for rapid convergence of Markov chain samplers. Relaxed Adaptive Search is demonstrated to have quasi-polynomial complexity when applied to convex programming. An approximate version of the Adaptive Search algorithm called Hide-and-Seek is coupled with the Generalized Lagrange Multiplier method to develop an efficient global optimization procedure for nonlinear programs involving both equality and inequality constraints. When applied to a difficult automotive design problem, it is demonstrated that this version of Hide-and-Seek significantly outperforms a commercial optimization algorithm.