  In this paper, we address the challenge of solving large-scale
graph-structured nonlinear programs (gsNLPs) in a scalable manner. GsNLPs are
problems in which the objective and constraint functions are associated with
nodes on a graph and depend on the variables of adjacent nodes. This
graph-structured formulation encompasses various specific instances, such as
dynamic optimization, PDE-constrained optimization, multistage stochastic
optimization, and general network optimization. By leveraging the sequential
quadratic programming (SQP) framework, we propose a globally convergent
overlapping graph decomposition method to solve large-scale gsNLPs under
standard mild regularity conditions on the graph topology. In each iteration,
we perform an overlapping graph decomposition to compute an approximate Newton
direction in a parallel environment. Then, we select a suitable stepsize and
update the primal-dual iterate by performing a backtracking line search on an
exact augmented Lagrangian merit function. Built on the exponential decay of
sensitivity of gsNLPs, we show that the approximate Newton direction is a
descent direction of the augmented Lagrangian, which leads to global
convergence with a local linear convergence rate. In particular, global
convergence is achieved for sufficiently large overlaps, and the local linear
convergence rate improves exponentially in terms of the overlap size. Our
results match existing state-of-the-art guarantees established for dynamic
programs (which simply correspond to linear graphs). We validate the theory on
a semilinear elliptic PDE-constrained problem.
