Accession Number : ADA303004

Title :   Application of Convex Sampling to Optimization and Contingency Table Generation/Counting.

Descriptive Note : Doctoral thesis,

Corporate Author : CARNEGIE-MELLON UNIV PITTSBURGH PA SCHOOL OF COMPUTER SCIENCE

Personal Author(s) : Mount, John

PDF Url : ADA303004

Report Date : MAY 1995

Pagination or Media Count : 111

Abstract : The optimization problem of minimizing a linear objective function over a general convex 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.

Descriptors :   *OPTIMIZATION, *STOCHASTIC PROCESSES, *COUNTING METHODS, *STATISTICAL SAMPLES, TEST AND EVALUATION, ALGORITHMS, EMERGENCIES, SIZES(DIMENSIONS), RANDOM VARIABLES, ACCURACY, PROBLEM SOLVING, TIME, POLYNOMIALS, SAMPLING, TABLES(DATA), HYPOTHESES, MARKOV PROCESSES, GRADIENTS, COMMONALITY, CONVEX BODIES.

Subject Categories : Statistics and Probability

Distribution Statement : APPROVED FOR PUBLIC RELEASE