Fast Randomized Algorithms for Optimization and Other Applications of Geometric Random Walks

点击翻译按钮获取中文摘要

This is a companion project with CCR-95-28973 (entitled ``Optimization and Learning over Convex Sets'') and is an award under the Software Capitalization Program. The project's goal is to upgrade and update software that had been produced. These upgrades and updates are based on algorithms developed under support of CCR-92-08597. The software is for executing random walks that produce a sample from certain multi-variate probability distributions. An update of the software involves simply changing the ``number of steps'' parameter in the random walk. Applications of this discrete probabilistic software (i) to contingency tables and (ii) to the membership oracles for optimization over convex sets, are investigated. With good planned dissemination (for example, on the world wide-web)and well thought-out testing, other applications of this software are anticipated. ***