Abstract
This talk presents the Polytope Division Method (PDM), a greedy algorithm for solving high-dimensional configuration optimization problems—such as those arising in model reduction and optimal experimental design—where one seeks an optimal sampling of parameter spaces. Classical approaches like standard greedy sampling rely on fixed training sets and quickly suffer from the curse of dimensionality. PDM replaces global sampling with an adaptive, geometry-driven strategy based on recursive polytope subdivision. At each step, the method evaluates the objective only at samples in dynamically refined regions. This yields a sampling complexity that scales linearly with dimension, avoiding exponential growth. The approach requires no a priori choice of training set size and focuses computational effort where it matters most. Applications to reduced basis methods and empirical interpolation demonstrate strong performance gains. Numerical results show that PDM achieves comparable accuracy to classical methods at significantly lower offline computational cost.
