(705d) Overlapping Domain Decomposition Schemes for Graph-Structured Optimization Problems

Structured optimization problems arise in diverse estimation and control applications for chemical processes, infrastructure networks, and supply chains. Such problems are computationally challenging due to their high dimensionality and large physical scale, which makes them difficult to implement in a real-time setting. As such, specialized algorithms that exploit the underlying structure of these problems are necessary to manage their computational complexity and the difficulty in their implementation. A key observation about these problems is that the underlying structure can be expressed in the form of a connected graph. For instance, a network optimization problem naturally inherits a spatial graph topology while a time-dependent optimization problem inherits a temporal graph topology (e.g., a tree).

Decomposition schemes have been increasingly used for solving large-scale optimization problems as they can help exploit parallel computing architectures and practical limitations of centralized schemes. In a typical decomposition scheme, the problem graph domain is decomposed into multiple subdomains and the subproblems associated with the subdomains are solved iteratively by exchanging primal/dual information at their boundaries. This type of paradigm is used by methods such as the alternating direction method of multipliers (ADMM) [1], Lagrangian decomposition [2], Benders decomposition [3], and Gauss-Seidel schemes [4]. ADMM, in particular, has been widely used in applications due to its convenience of implementation [5]. However, the convergence of ADMM is often slow and the algorithm parameters are difficult to tune [1, Section 3.2.2].

In this work, we present a new parallel decomposition paradigm for the solution of graph-structured optimization problems. Specifically, we propose to use the overlapping domain decomposition method which is widely used for the solution of PDEs [6]-[8] to address the slow convergence issue of existing decomposition schemes. A key and novel design concept of the proposed scheme is that it uses overlapping subdomains to promote and accelerate convergence. We show that the algorithm converges if the size of the overlap is sufficiently large and that the convergence rate improves exponentially with the size of the overlap [9]. In particular, we demonstrate that the proposed method achieves superior computational performance over ADMM. The high efficiency is achieved thanks to a more efficient exploitation of the graph structure.

References:
[1] S. Boyd, N. Parikh, E. Chu, B. Peleato, J. Eckstein et al., "Distributed optimization and statistical learning via the alternating direction method of multipliers," Foundations and Trends in Machine learning, vol. 3, no. 1, pp. 1–122, 2011.
[2] P. Giselsson, M. D. Doan, T. Keviczky, B. De Schutter, and A. Rantzer, "Accelerated gradient methods and dual decomposition in distributed model predictive control," Automatica, vol. 49, no. 3, pp. 829–833, 2013.
[3] A. M. Geoffrion, "Generalized benders decomposition," Journal of optimization theory and applications, vol. 10, no. 4, pp. 237–260, 1972.
[4] S. Shin and V. M. Zavala, "Multi-grid schemes for multi-scale coordination of energy systems," in Energy Markets and Responsive Grids.
[5] A. Kozma, C. Conte, and M. Diehl, "Benchmarking large-scale distributed convex quadratic programming algorithms," Optimization Methods and Software, vol. 30, no. 1, pp. 191–214, 2015. Springer, 2018, pp. 195–222.
[6] A. Toselli and O. Widlund, "Domain decomposition methods-algorithms and theory". Springer Science & Business Media, 2006, vol. 34.
[7] M. Dryja and O. B. Widlund, "Domain decomposition algorithms with small overlap," SIAM Journal on Scientific Computing, vol. 15, no. 3, pp. 604–620, 1994.
[8] V. Dolean, P. Jolivet, and F. Nataf, "An introduction to domain decomposition methods:algorithms, theory, and parallel implementation". SIAM, 2015, vol. 144.
[9] S. Shin, V. M. Zavala, and M. Anitescu. "Decentralized Schemes with Overlap for Solving Graph-Structured Optimization Problems". arXiv preprint arXiv:1810.00491, 2018.