  


Exponential Decay of Sensitivity in GraphStructured Nonlinear Programs
Sungho Shin (sungho.shinwisc.edu) Abstract: We study solution sensitivity for nonlinear programs (NLPs) whose structure is induced by a graph $\mathcal{G}=(\mathcal{V},\mathcal{E})$. These graphstructured NLPs arise in many applications such as dynamic optimization, stochastic optimization, optimization with partial differential equations, and network optimization. We show that the sensitivity of the primaldual solution at node $i\in \mathcal{V}$ against a data perturbation at node $j\in \mathcal{V}$ is bounded by $\Upsilon \rho^{d_\mathcal{G}(i,j)}$ for constants $\Upsilon>0$ and $\rho\in(0,1)$ and where $d_\mathcal{G}(i,j)$ is the distance between $i$ and $j$ on $\mathcal{G}$. In other words, the sensitivity of the solution decays exponentially with the distance to the perturbation point. This result, which we call exponential decay of sensitivity (EDS), holds under fairly standard assumptions used in classical NLP sensitivity theory: the strong secondorder sufficiency condition and the linear independence constraint qualification. We also present conditions under which the constants $(\Upsilon,\rho)$ remain uniformly bounded; this allows us to characterize behavior for NLPs defined over subgraphs of infinite graphs (e.g., as those arising in problems with unbounded domains). Our results provide new insights on how perturbations propagate through the NLP graph and on how the problem formulation influences such propagation. Specifically, we provide empirical evidence that positive objective curvature and constraint flexibility tend to dampen propagation. The developments are illustrated with numerical examples. Keywords: nonlinear programming; graphs, sensitivity Category 1: Nonlinear Optimization Citation: Download: [PDF] Entry Submitted: 01/08/2021 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  