(177h) Overlapping Schwarz: A New Decomposition Paradigm for Large-Scale Optimization

Structured optimization problems arise in a number of applications such as network optimization, optimization with embedded partial differential equations (PDEs), model predictive control, and stochastic programming. Diverse decomposition paradigms have been proposed to tackle such problems in a scalable manner; these include Benders decomposition [1], Lagrangian dual decomposition [2], the alternating direction method of multipliers (ADMM) [3], and block Jacobi/Gauss-Seidel [4]. Such algorithms decompose the original problem into subproblems and coordinate subproblem solutions by using primal-dual information at the boundary of the subdomains. These algorithms are flexible but exhibit slow convergence [5].

In this work we propose a different decomposition paradigm for optimization: Overlapping Schwarz Decomposition. Overlapping Schwarz methods have been traditionally used to solve linear algebra systems arising from partial differential equations [6], but we have recently shown that these methods can be generalized to solve structured optimization problems [7,8,9]. In the proposed scheme, we consider optimization problems whose algebraic structure can be represented by graphs. The graph domain is partitioned into overlapping subdomains, yielding a set of coupled subproblems. The algorithm computes the primal-dual solution of the subproblems in parallel and facilitates convergence by communicating the solution information in the coupled regions. The size of overlap is the key algorithmic parameter. In particular, we show that convergence can be guaranteed if the overlap is sufficiently large and that the convergence rate improves exponentially with the size of the overlap (i.e., the larger the overlap, the faster the convergence). However, increasing the size of overlap increases the subproblem complexity at the same time; thus, one needs to tune the size of overlap to achieve optimal convergence performance. Overlapping Schwarz schemes provide a bridge between fully decentralized (no overlap) and centralized algorithms (the overlap is the entire domain).

Our convergence results rely on a fundamental property of structured optimization problems that we call exponential decay of sensitivity [9,10,11]. This property states that the sensitivity of the primal-dual solution at a given node decays exponentially with respect to the distance from the node on which parametric perturbation is applied. We establish sufficient conditions for this property to hold and provide an explicit estimate of the sensitivity coefficients. Our results reveal that local convexity and generalized controllability provide sufficient conditions for exponential decay of sensitivity to hold.

Overlapping Schwarz decomposition is a flexible and versatile approach for decomposing structured optimization problems. Specifically, we show that this paradigm can be applied to decompose problems at three different levels: (i) problem level, (ii) subproblem level (within an augmented Lagrangian or sequential quadratic programming method), and (iii) linear algebra level (within an interior point method). Problem level decomposition enables fully decentralized and asynchronous implementation (no centralized coordinator is necessary), thus advantageous for decentralized control, but the convergence may not be robust for non-convex problems [7,9]. The linear algebra level decomposition requires centralized implementation but enables efficient computations and robust convergence (inherit the convergence of the outer loop) [12]. The effectiveness of the proposed algorithms is demonstrated with a wide variety of problem instances that arise in energy systems [13,14].

References:
[1] Geoffrion, Arthur M. "Generalized benders decomposition." Journal of optimization theory and applications 10.4 (1972): 237-260.
[2] Lemaréchal, Claude. "Lagrangian relaxation." Computational combinatorial optimization. Springer, Berlin, Heidelberg, 2001. 112-156.
[3] Boyd, Stephen, et al. "Distributed optimization and statistical learning via the alternating direction method of multipliers." Foundations and Trends® in Machine learning 3.1 (2011): 1-122.
[4] Shin, Sungho, and Victor M. Zavala. "Multi-grid schemes for multi-scale coordination of energy systems." Energy Markets and Responsive Grids. Springer, New York, NY, 2018. 195-222.
[5] Kozma, Attila, Christian Conte, and Moritz Diehl. "Benchmarking large-scale distributed convex quadratic programming algorithms." Optimization Methods and Software 30.1 (2015): 191-214.
[6] Chan, Tony F., and Jun Zou. "Additive Schwarz domain decomposition methods for elliptic problems on unstructured meshes." Numerical Algorithms 8.2 (1994): 329-346.
[7] Shin, Sungho, Victor M. Zavala, and Mihai Anitescu. "Decentralized schemes with overlap for solving graph-structured optimization problems." IEEE Transactions on Control of Network Systems (2020).
[8] Shin, Sungho, et al. "A parallel decomposition scheme for solving long-horizon optimal control problems." 58th IEEE Conference on Decision and control. IEEE, 2019.
[9] Shin, Sungho, Mihai Anitescu, and Victor M. Zavala. "Overlapping Schwarz Decomposition for Constrained Quadratic Programs." arXiv preprint arXiv:2003.07502, (2020).
[10] Na, Sen, and Mihai Anitescu. "Exponential Decay in the Sensitivity Analysis of Nonlinear Dynamic Programming." arXiv preprint arXiv:1912.06734 (2019).
[11] Shin, Sungho, and Victor M. Zavala. "Diffusing-Horizon Model Predictive Control." arXiv preprint arXiv:2002.08556 (2020).
[12] Gerstner, Philipp, et al. "A Domain Decomposition Approach for Solving Dynamic Optimal Power Flow Problems in Parallel with Application to the German Transmission Grid." Preprint Series of the Engineering Mathematics and Computing Lab 1 (2016).
[13] Coffrin, Carleton, et al. "Powermodels. jl: An open-source framework for exploring power flow formulations." 2018 Power Systems Computation Conference (PSCC). IEEE, 2018.
[14] GasModels.jl, GitHub repository, https://github.com/lanl-ansi/GasModels.jl