Application of Convex Sampling to Optimization and Contingency TableGeneration/Counting

摘要

The optimization problem of minimizing a linear objective function over a generalconvex body given only by a weak membership oracle is a central problem in convex optimization. Traditional methods require the (expensive) construction of separating relations (cuts) or gradient information (which is often expensive). We demonstrate how a sampling procedure can be used as the central routine in a randomized polynomial time algorithm for approximately minimizing a linear objective function over an up-monotone convex set presented by a membership oracle. The sampling procedure is a Markov chain that uses only local membership tests. We further demonstrate a direct application of this technique to an important stochastic optimization problem called 'component commonality.' A second application of the above sampling scheme is a statistical hypothesis testing procedure involving contingency tables. The test involves counting contingency tables (matrices of non-negative integers) obeying given row and column constraints which is known to be hard. Under fairly natural assumptions the Markov technique yields an effective procedure for approximating, to any desired accuracy, the necessary counts. We also develop a powerful exact counting scheme, for fixed dimension, and use it to validate the random technique.