Speaker: Victor M Zavala
Title: Exponential Decay of Sensitivity in Graph-Structured Nonlinear ProgramsAbstract: We study solution sensitivity for nonlinear programs (NLPs) whose structures are induced by graphs. These NLPs arise in many applications such as dynamic optimization, stochastic optimization, optimization with partial differential equations, and network optimization. We show that for a given pair of nodes, the sensitivity of the primal-dual solution at one node against a data perturbation at the other node decays exponentially with respect to the distance between these two nodes on the graph. In other words, the solution sensitivity decays exponentially as one moves away from the perturbation point. This result, which we call exponential decay of sensitivity, holds under fairly standard assumptions: the strong second-order sufficiency condition and the linear independence constraint qualification. We discuss how this property provides new and interesting insights on the behavior of complex systems and how it enables the design of new and scalable decomposition algorithms.