Optimization Online


Exponential Decay of Sensitivity in Graph-Structured Nonlinear Programs

Sungho Shin (sungho.shin***at***wisc.edu)
Mihai Anitescu (anitescu***at***mcs.anl.gov)
Victor Zavala (victor.zavala***at***wisc.edu)

Abstract: We study solution sensitivity for nonlinear programs (NLPs) whose structure is induced by a graph $\mathcal{G}=(\mathcal{V},\mathcal{E})$. These graph-structured 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 primal-dual 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 second-order 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


Download: [PDF]

Entry Submitted: 01/08/2021
Entry Accepted: 01/08/2021
Entry Last Modified: 01/08/2021

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society