Pattern Hit-and-Run for sampling efficiently on polytopes |
| |
Authors: | Huseyin Onur Mete Zelda B Zabinsky |
| |
Institution: | Industrial and Systems Engineering, University of Washington, Seattle, WA 98195-2650, United States |
| |
Abstract: | Pattern Hit-and-Run (PHR) is a Markov chain Monte Carlo sampler for a target distribution that was originally designed for general sets embedded in a box. A specific set of interest to many applications is a polytope intersected with discrete or mixed continuous/discrete lattices. PHR requires an acceptance/rejection mechanism along a bidirectional walk to guarantee feasibility. We remove this inefficiency by utilizing the linearity of the constraints defining the polytope, so each iteration of PHR can be efficiently implemented even though the variables are allowed to be integer valued. Moreover, PHR converges to a uniform distribution in polynomial time for a class of discrete polytopes. |
| |
Keywords: | Random search algorithms Global optimization Simulated annealing Markov chain Monte Carlo sampling |
本文献已被 ScienceDirect 等数据库收录! |