12:30–1:30 pm Searle 240A
Tuesday, April 23, 2024, at 12:30 PM, in Jones 303, 5735 S. Ellis Avenue
CAM & Stats Student Seminar
Runxin Ni, Committee on Computational and Applied Mathematics
"Globally Convergent Distributed Sequential Quadratic Programming with Overlapping Graph Decomposition and Exact Augmented Lagrangian"
Abstract
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 graph nodes and depend only 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 generic network optimization. We propose a globally convergent overlapping graph decomposition method for solving large-scale gsNLPs under standard mild regularity conditions on the graph topology. In each iteration, we use an overlapping graph decomposition to compute an approximate Newton direction using parallel computations. We then select a suitable stepsize and update the primal-dual iterate by performing a backtracking line search on the exact augmented Lagrangian merit function. By leveraging 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 results for dynamic programs (which simply correspond to linear graphs). We validate the theory on an elliptic PDE-constrained problem.