Decentralized optimization over tree graphs. (English) Zbl 1470.90149
Summary: This paper presents a decentralized algorithm for non-convex optimization over tree-structured networks. We assume that each node of this network can solve small-scale optimization problems and communicate approximate value functions with its neighbors based on a novel multi-sweep communication protocol. In contrast to existing parallelizable optimization algorithms for non-convex optimization, the nodes of the network are neither synchronized nor assign any central entity. None of the nodes needs to know the whole topology of the network, but all nodes know that the network is tree-structured. We discuss conditions under which locally quadratic convergence rates can be achieved. The method is illustrated by running the decentralized asynchronous multi-sweep protocol on a radial AC power network case study.
MSC:
| 90C35 | Programming involving graphs or networks |
| 90C26 | Nonconvex programming, global optimization |
References:
| [1] | Bellman, R., Dynamic programming, Science, 153, 3731, 34-37 (1966) · doi:10.1126/science.153.3731.34 |
| [2] | Bernardini, D.; Bemporad, A., Stabilizing model predictive control of stochastic constrained linear systems, IEEE Trans. Autom. Control, 57, 6, 1468-1480 (2011) · Zbl 1369.93687 · doi:10.1109/TAC.2011.2176429 |
| [3] | Bertsekas, D., Convexification procedures and decomposition methods for nonconvex optimization problems, J. Optim. Theory Appl., 29, 2, 169-197 (1979) · Zbl 0389.90080 · doi:10.1007/BF00937167 |
| [4] | Bertsekas, DP, Dynamic programming and suboptimal control: A survey from ADP to MPC, Eur. J. Control, 11, 4-5, 310-334 (2005) · Zbl 1293.49056 · doi:10.3166/ejc.11.310-334 |
| [5] | Bertsekas, DP, Dynamic Programming and Optimal Control (2007), MA: Athena Scientific Belmont, MA · Zbl 1209.90343 |
| [6] | Bertsekas, DP, Abstract Dynamic Programming (2013), MA: Athena Scientific Belmont, MA · Zbl 1312.90086 |
| [7] | Bertsekas, D., Constrained Optimization and Lagrange Multiplier Methods (2014), Singapore: Academic Press, Singapore · Zbl 0572.90067 |
| [8] | Bertsekas, D.; Tsitsiklis, J., Parallel and Distributed Computation: Numerical Methods (1989), NJ: Prentice Hall Englewood Cliffs, NJ · Zbl 0743.65107 |
| [9] | Boyd, S., Parikh, N., Chu, E., Peleato, B., Eckstein, J.: Distributed optimization and statistical learning via the alternating direction method of multipliers. Found. Trends Mach. Learn. 3(1), 1-122 (2011) · Zbl 1229.90122 |
| [10] | Braun, P.; Grüne, L.; Kellett, CM; Weller, SR; Worthmann, K., A distributed optimization algorithm for the predictive control of smart grids, IEEE Trans. Autom. Control, 61, 12, 3898-3911 (2016) · Zbl 1359.93270 · doi:10.1109/TAC.2016.2525808 |
| [11] | Du, X., Engelmann, A., Jiang, Y., Faulwasser, T., Houska, B.: Distributed state estimation for AC power systems using Gauss-Newton ALADIN. In: In Proceedings of the 58th IEEE Conference on Decision and Control, pp. 1919-1924 (2019) |
| [12] | Engelmann, A.; Jiang, Y.; Mühlpfordt, T.; Houska, B.; Faulwasser, T., Toward distributed OPF using ALADIN, IEEE Trans. Power Syst., 34, 1, 584-594 (2018) · doi:10.1109/TPWRS.2018.2867682 |
| [13] | Gondzio, J., Grothey, A.: Exploiting structure in parallel implementation of interior point methods for optimization. CMS 6(2), 135-160 (2009) · Zbl 1170.90518 |
| [14] | Grüne, L., Semmler, W.: Using dynamic programming with adaptive grid scheme for optimal control problems in economics. J. Econ. Dyn. Control 28, 2427-2456 (2004) · Zbl 1202.49026 |
| [15] | Hamdi, A.: Two-level primal-dual proximal decomposition technique to solve large scale optimization problems. Appl. Math. Comput. 160(3), 921-938 (2005) · Zbl 1122.90061 |
| [16] | Hamdi, A., Mishra, S.K.: Decomposition methods based on augmented Lagrangians: a survey. In: Mishra, S. (ed.) Topics in nonconvex optimization, pp. 175-203. Springer (2011) · Zbl 1247.90249 |
| [17] | Hong, M.; Luo, ZQ; Razaviyayn, M., Convergence analysis of alternating direction method of multipliers for a family of nonconvex problems, SIAM J. Optim., 26, 1, 337-364 (2016) · Zbl 1356.49061 · doi:10.1137/140990309 |
| [18] | Houska, B., Diehl, M.: Nonlinear robust optimization via sequential convex bilevel programming. Math. Program., Ser. A 142, 539577 (2013) · Zbl 1282.90240 |
| [19] | Houska, B.; Frasch, J.; Diehl, M., An augmented Lagrangian based algorithm for distributed nonconvex optimization, SIAM J. Optim., 26, 2, 11011127 (2016) · Zbl 1345.90069 · doi:10.1137/140975991 |
| [20] | Hult, R., Zanon,M.,Gros, S., Falcone, P.: Primal decomposition of the optimal coordination of vehicles at traffic intersections. In: 2016 IEEE 55thConference on Decision and Control (CDC), pp. 2567-2573 |
| [21] | Jiang, Y.; Zanon, M.; Hult, R.; Houska, B., Distributed algorithm for optimal vehicle coordination at traffic intersections, IFAC-PapersOnLine, 50, 1, 11577-11582 (2017) · doi:10.1016/j.ifacol.2017.08.1511 |
| [22] | Kekatos, V., Giannakis, G.B.: Distributed robust power system state estimation. IEEE Trans. Power Syst. 28(2), 1617-1626 (2012) |
| [23] | Kellerer, A.; Steinke, F., An approximate min-sum algorithm for smart grid dispatch with continuous variables, IFAC-PapersOnLine, 49, 307-312 (2016) · doi:10.1016/j.ifacol.2016.10.709 |
| [24] | Kellerer, A.; Steinke, F., Scalable economic dispatch for smart distribution networks, IEEE Trans. Power Syst., 30, 1739-1746 (2014) · doi:10.1109/TPWRS.2014.2358375 |
| [25] | Keshavarz, A.; Boyd, S., Quadratic approximate dynamic programming for input-affine systems, Int. J. Robust Nonlinear Control, 24, 3, 432-449 (2014) · Zbl 1285.93103 · doi:10.1002/rnc.2894 |
| [26] | Khoshfetrat Pakazad, S., Hansson, A., Andersen, M.S., Nielsen, I.: Distributed primal-dual interior-point methods for solving tree-structured coupled convex problems using message-passing. Optim. Methods Softw. 32(3), 401-435 (2017) · Zbl 1364.90357 |
| [27] | Kouzoupis, D.; Klintberg, E.; Diehl, M.; Gros, S., A dual Newton strategy for scenario decomposition in robust multistage MPC, Int. J. Robust Nonlinear Control, 28, 6, 2340-2355 (2018) · Zbl 1390.49030 · doi:10.1002/rnc.4019 |
| [28] | Kouzoupis, D., Quirynen, R., Garcia, J., Erhard, M., Diehl, M.: A quadratically convergent primal decomposition algorithm with soft coupling for nonlinear parameter estimation. In: 2016 IEEE 55th Conference on Decision and Control (CDC), pp. 1086-1092 (2016) |
| [29] | Kouzoupis,D.: Structure-exploiting numericalmethods for tree-sparse optimal control problems. Ph.D. thesis, University of Freiburg (2019) |
| [30] | Lucia, S., Andersson, J.A., Brandt, H., Diehl, M., Engell, S.: Handling uncertainty in economic nonlinear model predictive control: A comparative case study. J. Process Control 24(8), 1247-1259 (2014) |
| [31] | Luss, R., Optimal control by dynamic programming using systematic reduction in grid size, Int. J. Control, 51, 5, 995-1013 (1990) · Zbl 0703.49022 · doi:10.1080/00207179008934113 |
| [32] | Makhdoumi, A.; Ozdaglar, A., Convergence rate of distributed ADMM over networks, IEEE Trans. Autom. Control, 62, 10, 5082-5095 (2017) · Zbl 1390.90551 · doi:10.1109/TAC.2017.2677879 |
| [33] | Molzahn, DK; Dörfler, F.; Sandberg, H.; Low, SH; Chakrabarti, S.; Baldick, R.; Lavaei, J., A survey of distributed optimization and control algorithms for electric power systems, IEEE Trans. Smart Grid, 8, 6, 2941-2962 (2017) · doi:10.1109/TSG.2017.2720471 |
| [34] | Nedić, A., Olshevsky, A., Shi, W.: Decentralized consensus optimization and resource allocation. In: Large-Scale and Distributed Optimization, pp. 247-287. Springer (2018) · Zbl 1412.90112 |
| [35] | Nesterov, Y., Introductory Lectures on Convex Optimization: A Basic Course (2013), Berlin: Springer, Berlin · Zbl 1086.90045 |
| [36] | Nesterov, Y.; Polyak, BT, Cubic regularization of Newton method and its global performance, Math. Program., 108, 1, 177-205 (2006) · Zbl 1142.90500 · doi:10.1007/s10107-006-0706-8 |
| [37] | Nocedal, J.; Wright, SJ, Numerical Optimization (2006), Berlin: Springer, Berlin · Zbl 1104.65059 |
| [38] | Pakazad, S.; Hansson, A.; Andersen, M., Distributed primal-dual interior-point methods for solving tree-structured coupled problems using message passing, Optim. Methods Softw., 32, 3, 401-435 (2017) · Zbl 1364.90357 · doi:10.1080/10556788.2016.1213839 |
| [39] | Peng, Q., Low, S.: Distributed algorithm for optimal power flow on a radial network. In: 53rd IEEE Conference on Decision and Control, pp. 167-172. IEEE (2014) |
| [40] | Rawlings, J.; Mayne, D.; Diehl, M., Model Predictive Control: Theory and Design (2017), Madison, WI: Nob Hill Publishing, Madison, WI |
| [41] | Robinson, S., Strongly regular generalized equations, Math. Oper. Res., 5, 1, 43-62 (1980) · Zbl 0437.90094 · doi:10.1287/moor.5.1.43 |
| [42] | Shi, W.; Ling, Q.; Yuan, K.; Wu, G.; Yin, W., On the linear convergence of the ADMM in decentralized consensus optimization, IEEE Trans. Signal Process., 62, 7, 1750-1761 (2014) · Zbl 1394.94532 · doi:10.1109/TSP.2014.2304432 |
| [43] | Terelius, H.; Topcu, U.; Murray, RM, Decentralized multi-agent optimization via dual decomposition, IFAC Proc., 44, 1, 11245-11251 (2011) · doi:10.3182/20110828-6-IT-1002.01959 |
| [44] | Wächter, A.; Biegler, LT, On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming, Math. Program., 106, 1, 25-57 (2006) · Zbl 1134.90542 · doi:10.1007/s10107-004-0559-y |
| [45] | Wang, Y.; O’Donoghue, B.; Boyd, S., Approximate dynamic programming via iterated Bellman inequalities, Int. J. Robust Nonlinear Control, 25, 10, 1472-1496 (2015) · Zbl 1317.93237 · doi:10.1002/rnc.3152 |
| [46] | Zavala, V.; Laird, C.; Biegler, L., Interior-point decomposition approaches for parallel solution of large-scale nonlinear parameter estimation problems, Chem. Eng. Sci., 63, 19, 4834-4845 (2008) · doi:10.1016/j.ces.2007.05.022 |
| [47] | Zimmerman, RD; Murillo-Sánchez, CE; Thomas, RJ, Matpower: Steady-state operations, planning, and analysis tools for power systems research and education, IEEE Trans. Power Syst., 26, 1, 12-19 (2011) · doi:10.1109/TPWRS.2010.2051168 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
