ALOP-Colloquium with Sungho Shin, University of Wisconsin-Madison

On Monday, November 15, 2021, at 16:00 c.t., Ph.D. candidate Sungho Shin, University of Madison-Wisonsin will speak about his recent work:

Title: Graph-Structured Nonlinear Programming: Properties and Algorithms

A graph-structured nonlinear program (NLP) is a nonlinear optimization problem whose algebraic structure is induced by a graph. These problems arise in diverse applications such as dynamic optimization (model predictive control and moving horizon estimation), network optimization (energy systems and supply chain), optimization with embedded discretized partial differential equations, and multi-stage stochastic programming. Building upon the existing NLP sensitivity theory, we show that the nodal solution sensitivity against parametric perturbation decays exponentially with respect to the distance from the perturbation point. Remarkably, this result (which we call exponential decay of sensitivity; EDS) holds under fairly standard regularity assumptions used in classical NLP sensitivity theory: second-order sufficiency conditions and the linear independence constraint qualification. EDS allows the creation of novel computing strategies, the overlapping Schwarz decomposition method (also known as domain decomposition). This method decomposes a graph-structured NLP into multiple smaller subproblems over overlapping subdomains and solves the subproblems in parallel and iteratively with the exchange of information at boundries. Based on the EDS result, we prove that for a certain class of problems satisfying the regularity assumptions, the convergence rate of the overlapping Schwarz method improves exponentially with the size of overlap; thus, overlap accelerates the convergence. With real-world case studies on gas and electric networks, we demonstrate the effectiveness of the overlapping Schwarz method.

This presentation will take place via ZOOM. A link will be e-mailed prior to the event