Computational Mathematics and Statistics Seminar by
Speaker: Ahmed Attia, Computational Mathematician, Argonne National Laboratory
Title: Optimizing Over Distributions: A General Approach to Black-Box Combinatorial Optimization
Abstract:
Combinatorial optimization problems are hard for a common set of reasons: the search space grows explosively, the objective is expensive to evaluate, and there is no gradient to follow. This talk presents a general framework that addresses all three. Rather than searching for a single best solution, we optimize over a family of probability distributions on the discrete search space, replacing the original objective with its expectation which is a smooth, differentiable function of the distribution's parameters even when the underlying problem is not. This recovers gradients where none existed and yields stochastic optimization algorithms that scale well beyond the reach of enumeration. The framework requires only the ability to evaluate the objective, making it well suited to problems where each evaluation involves a simulation or an inverse solve.
Much of the talk concerns what happens when this machinery is specialized: the choice of distribution is where problem structure enters. Using optimal experimental design and sensor placement in inverse problems as the running application, I will show how the same underlying algorithm accommodates binary selection under budget constraints, designs that remain robust to uncertainty in the model, and parametric policies over graphs and meshes that turn the framework into a method for trajectory and path design. I will close by noting a natural connection to reinforcement learning and what it suggests for future work.
Computational Mathematics and Statistics