Applied Mathematics Colloquia with Mihai Anitescu: Exponential Decay of Sensitivity and Domain Decomposition with Overlap for Dynamic and Other Graph-Indexed Optimization

Speaker: Mihai Anitescu, University of Chicago/Argonne National Laboratory

Title: Exponential Decay of Sensitivity and Domain Decomposition with Overlap for Dynamic and Other Graph-Indexed Optimization

Abstract:

Many engineering control and optimization problems occupy an extensive area of space and time. These include production cost models in energy or the control of central plants. Model predictive control, one of the favorite approaches for physics-centered control, generally relies on direct numerical solvers, which tend to run out of memory for such problems. Approaches relying on domain decomposition are then key to fit in memory, but theory for such second-order methods tends to be lacking in multicomponent systems.

To address this issue, we prove that certain classes of graph-indexed optimization (GIO) problems exhibit exponential decay of sensitivity with respect to perturbation in the data. GIOs include dynamic optimization (for the linear graph), or distributed, including network control (for the mesh/network-time product graph). This feature allows for very efficient approximation, solutions, or policies based on domain decomposition with overlap relative to centralized or monolithic approaches. In particular, we prove that the proper efficiency metric increases exponentially fast with the overlap size. Immediate consequences of such behavior are that distributed control policies with overlap approach the performance of centralized policies exponentially fast and that Schwarz-type algorithms exhibit, in addition to exceptional parallelism and reduced memory footprint per subproblem, a linear rate of convergence that tends exponentially fast to zero.

Applied Mathematics Colloquium