(558c) Exponential Decay of Sensitivity in Graph-Structured Nonlinear Programs

A graph-structured nonlinear program (gNLP) 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) [1,2], network optimization (energy systems and supply chain) [3,4,5], optimization with embedded discretized partial differential equations (PDEs) [6], and multi-stage stochastic programming [7]. Characterization of the nodal sensitivity of such problems (the sensitivity of the solution at a particular node against the data perturbation on another node) allows addressing a wide range of questions that are of practical interest. For example, in the context of dynamic optimization, it allows understanding the relationship between the prediction horizon length and the control/estimation performance [8]. This further enables systematically balancing the computational complexity and the expected control/estimation performance. Furthermore, in the context of energy infrastructures, it allows understanding how far the disturbance in one part of the network may propagate to the other part; this enables assessing the flexibility and reliability of operations [9].

In this work, we aim to quantitatively characterize the nodal solution sensitivity of gNLPs. Building upon the existing NLP sensitivity theory [10,11], we show that the nodal sensitivity decays exponentially with respect to the distance to the perturbation point [12]. Remarkably, this result (which we call exponential decay of sensitivity; EDS) holds under fairly standard assumptions used in classical NLP sensitivity theory: second-order sufficiency conditions (SOSC) and the linear independence constraint qualification (LICQ) [10,11]. In practical terms, these regularity conditions (LICQ and SOSC) can be interpreted as having sufficient flexibility and positive objective curvature. This interpratation enables an intuitive explanation of EDS that the positive objective curvature and the flexibility of the system damps the propagation of the perturbation. In the context of control, the regularity conditions can be obtained from controllability and observability [13]. These results generalize our previous results under simpler settings [14,15]. Also, it provides new insights on how perturbations propagate through graphs and on how the NLP formulation influences such propagation. Moreover, EDS allows the creation of novel computing strategies and optimization formulations, which include the overlapping Schwarz decomposition method (also known as domain decomposition) [14,16,17], online algorithms for dynamic optimization [18], diffusing-horizon model predictive control [19], and flexibility-maximizing design method (currently under study).

References:

[1] Rawlings, James Blake, David Q. Mayne, and Moritz Diehl. Model predictive control: theory, computation, and design. Vol. 2. Madison, WI: Nob Hill Publishing, 2017.
[2] Rao, Christopher V., James B. Rawlings, and David Q. Mayne. "Constrained state estimation for nonlinear discrete-time systems: Stability and moving horizon approximations." IEEE transactions on automatic control 48.2 (2003): 246-258.
[3] Huneault, M., and F. D. Galiana. "A survey of the optimal power flow literature." IEEE transactions on Power Systems 6.2 (1991): 762-770.
[4] Zlotnik, Anatoly, Michael Chertkov, and Scott Backhaus. "Optimal control of transient flow in natural gas networks." 2015 54th IEEE conference on decision and control (CDC). IEEE, 2015.
[5] Dembo, Ron S., John M. Mulvey, and Stavros A. Zenios. "Practice ORLarge-Scale Nonlinear Network Models and Their Application." Operations Research 37.3 (1989): 353-372.
[6] Biegler, Lorenz T., et al. "Large-scale PDE-constrained optimization: an introduction." Large-Scale PDE-Constrained Optimization. Springer, Berlin, Heidelberg, 2003. 3-13.
[7] Pereira, Mario VF, and Leontina MVG Pinto. "Multi-stage stochastic optimization applied to energy planning." Mathematical programming 52.1 (1991): 359-375.
[8] Zavala, Victor M., et al. "On-line economic optimization of energy systems using weather forecast information." Journal of Process Control 19.10 (2009): 1725-1736.
[9] Greene, Scott, and I. Dobson. Margin and sensitivity methods for security analysis of electric power systems. 1998.
[10] Robinson, Stephen M. "Strongly regular generalized equations." Mathematics of Operations Research 5.1 (1980): 43-62.
[11] Dontchev, Asen L., and R. Tyrrell Rockafellar. Implicit functions and solution mappings. Vol. 543. New York: Springer, 2009.
[12] Shin, Sungho, Mihai Anitescu, and Victor M. Zavala. "Exponential Decay of Sensitivity in Graph-Structured Nonlinear Programs." arXiv preprint arXiv:2101.03067 (2021).
[13] Shin, Sungho, and Victor M. Zavala. "Exponential Decay of Sensitivity in Dynamic Optimization: A Graph-Theoretic Approach." arXiv preprint arXiv:2101.06350 (2021).
[14] Shin, Sungho, Mihai Anitescu, and Victor M. Zavala. "Overlapping Schwarz Decomposition for Constrained Quadratic Programs." 2020 59th IEEE Conference on Decision and Control (CDC). IEEE, 2020.
[15] Na, Sen, and Mihai Anitescu. "Exponential decay in the sensitivity analysis of nonlinear dynamic programming." SIAM Journal on Optimization 30.2 (2020): 1527-1554.
[16] Shin, Sungho, et al. "Graph-Based Modeling and Decomposition of Energy Infrastructures." arXiv preprint arXiv:2010.02404 (2020).
[17] Na, Sen, et al. "Overlapping Schwarz Decomposition for Nonlinear Optimal Control." arXiv preprint arXiv:2005.06674 (2020).
[18] Na, Sen, and Mihai Anitescu. "Superconvergence of online optimization for model predictive control." arXiv preprint arXiv:2001.03707 (2020).
[19] Shin, Sungho, and Victor M. Zavala. "Diffusing-horizon model predictive control." arXiv preprint arXiv:2002.08556 (2020).