Article
Full entry |
PDF
(1.9 MB)
Feedback
PDF
(1.9 MB)
Feedback
Keywords:
distributed optimization; coupled constraints; dual averaging; variational inequality; multi-agent networks
distributed optimization; coupled constraints; dual averaging; variational inequality; multi-agent networks
Summary:
This paper investigates a distributed algorithm for the multi-agent constrained optimization problem, which is to minimize a global objective function formed by a sum of local convex (possibly nonsmooth) functions under both coupled inequality and affine equality constraints. By introducing auxiliary variables, we decouple the constraints and transform the multi-agent optimization problem into a variational inequality problem with a set-valued monotone mapping. We propose a distributed dual averaging algorithm to find the weak solutions of the variational inequality problem with an $O(1/\sqrt{k})$ convergence rate, where $k$ is the number of iterations. Moreover, we show that weak solutions are also strong solutions that match the optimal primal-dual solutions to the considered optimization problem. A numerical example is given for illustration.
References:
[1] Auslender, A., Correa, R.: Primal and dual stability results for variational inequalities. Comput. Optim. Appl. 17 (2000), 117-130. DOI | MR 1806249
[2] Auslender, A., Teboulle, M.: Projected subgradient methods with non-Euclidean distances for non-differentiable convex minimization and variational inequalities. Math. Program. 120 (2009), 27-48. DOI | MR 2496425
[3] Bertsekas, D. P., Tsitsiklis, J. N.: Parallel and Distributed Computation: Numerical Methods. Prentice hall Englewood Cliffs, NJ 1989. MR 0896902
[4] Borwein, J. M., Zhu, Q. J.: Techniques of Variational Analysis. Springer Science and Business Media, New York 2004. MR 2144010 | Zbl 1076.49001
[5] Chang, T. H., Nedić, A., Scaglione, A.: Distributed constrained optimization by consensus-based primal-dual perturbation method. IEEE Trans. Automat. Control 59 (2014), 1524-1538. DOI | MR 3225227
[6] Chen, G., Xu, G., Li, W., Hong, Y.: Distributed mirror descent algorithm with Bregman damping for nonsmooth constrained optimization. IEEE Trans. Automat. Control (2023), 1-8. DOI | MR 4664160
[7] Cherukuri, A., Cortés, J.: Distributed generator coordination for initialization and anytime optimization in economic dispatch. IEEE Trans. Control Network Syst. 2 (2015), 226-237. DOI | MR 3401184
[8] Duchi, J. C., Agarwal, A., Wainwright, M. J.: Dual averaging for distributed optimization: Convergence analysis and network scaling. IEEE Trans. Automat. Control 57 (2011), 592-606. DOI | MR 2932818
[9] Facchinei, F., Pang, J. S.: Finite-dimensional Variational Inequalities and Complementarity Problems. Springer Science and Business Media, 2007. MR 1955648
[10] Gutman, I., Xiao, W.: Generalized inverse of the Laplacian matrix and some applications. Bulletin (Académie serbe des sciences et des arts. Classe des sciences mathématiques et naturelles. Sciences mathématiques) (2004), 15-23. MR 2099614
[11] Hiriart-Urruty, J. B., Lemaréchal, C.: Convex Analysis and Minimization Algorithms I: Fundamentals. Springer Science and Business Media, 2013. MR 1261420
[12] Johansson, B., Keviczky, T., Johansson, M., Johansson, K. H.: Subgradient methods and consensus algorithms for solving convex optimization problems. In: 47th IEEE Conference on Decision and Control, IEEE 2008, pp. 4185-4190. DOI
[13] Koshal, J., Nedić, A., Shanbhag, U. V.: Multiuser optimization: Distributed algorithms and error analysis. SIAM J. Optim. 21 (2011), 1046-1081. DOI | MR 2837563
[14] Liang, S., Zeng, X., Hong, Y.: Distributed nonsmooth optimization with coupled inequality constraints via modified Lagrangian function. IEEE Trans. Automat. Control 63 (2017), 1753-1759. DOI | MR 3807659
[15] Liang, S., Wang, L., Yin, G.: Distributed smooth convex optimization with coupled constraints. IEEE Trans. Automat. Control 65 (2019), 347-353. DOI | MR 4052883
[16] Liang, S., Wang, L., Yin, G.: Distributed dual subgradient algorithms with iterate-averaging feedback for convex optimization with coupled constraint. IEEE Trans. Cybernetics 51 (2019), 2529-2539. DOI
[17] Liu, Q., Wang, J.: A second-order multi-agent network for bound-constrained distributed optimization. IEEE Trans. Automat. Control 60 (2015), 3310-3315. DOI | MR 3432700
[18] Lou, Y., Hong, Y., Wang, S.: Distributed continuous-time approximate projection protocols for shortest distance optimization problems. Automatica 69 (2016), 289-297. DOI | MR 3500113 | Zbl 1338.93026
[19] Nedić, A., Ozdaglar, A.: Approximate primal solutions and rate analysis for dual subgradient methods. SIAM J. Optim. 19 (2009), 1757-1780. DOI | MR 2486049
[20] Nesterov, Y.: Introductory Lectures on Convex Optimization: A Basic Course. Springer Science and Business Media, 2003. MR 2142598
[21] Nesterov, Y.: Dual extrapolation and its applications to solving variational inequalities and related problems. Math. Program. 109.2-3 (2007), 319-344. DOI | MR 2295146
[22] Nesterov, Y.: Primal-dual subgradient methods for convex problems. Math. Program. 120 (2009), 221-259. DOI | MR 2496434
[23] Nesterov, Y., Shikhman, V.: Dual subgradient method with averaging for optimal resource allocation. Europ. J. Oper. Res. 270 (2018), 907-916. DOI | MR 3814538
[24] Rabbat, M., Nowak, R.: Distributed optimization in sensor networks. In: Proc. 3rd International Symposium on Information Processing in Sensor Networks, 2004, pp. 20-27.
[25] Regina, S. B., Iusem, A.: Set-Valued Mappings and Enlargements of Monotone Operators. Springer, New York 2003.
[26] Rockafellar, R. T.: Characterization of the subdifferentials of convex functions. Pacific J. Math. 17 (1966), 497-510. DOI | MR 0193549
[27] Rockafellar, R. T.: On the maximality of sums of nonlinear monotone operators. Trans. Amer. Math. Soc. 149 (1970), 75-88. DOI | MR 0282272
[28] Ruszczynski, A.: Nonlinear Optimization. Princeton University Press, 2011. MR 2199043
[29] Shafarevich, I. R., Remizov, A. O.: Linear Algebra and Geometry. Springer Science and Business Media, 2012. MR 2963561
[30] Tu, Z., Li, W.: Multi-agent solver for non-negative matrix factorization based on optimization. Kybernetika 57 (2021), 60-77. DOI | MR 4231857
[31] Xiao, L., Boyd, S.: Optimal scaling of a gradient method for distributed resource allocation. J. Optim. Theory Appl. 129 (2006), 469-488. DOI | MR 2281152
[32] Xiao, L., Boyd, S., Kim, S. J.: Distributed average consensus with least-mean-square deviation. J. Parallel Distributed Comput. 67 (2007), 33-46. DOI
[33] Yao, J. C.: Variational inequalities with generalized monotone operators. Math. Oper. Res. 19 (1994), 691-705. DOI | MR 1288894
[34] Yi, P., Hong, Y., Liu, F.: Distributed gradient algorithm for constrained optimization with application to load sharing in power systems. Systems Control Lett. 83 (2015), 45-52. DOI | MR 3373270 | Zbl 1327.93033
[35] Yi, P., Hong, Y., Liu, F.: Initialization-free distributed algorithms for optimal resource allocation with feasibility constraints and application to economic dispatch of power systems. Automatica 74 (2016), 259-269. DOI | MR 3569392
[36] Yi, P., Pavel, L.: A distributed primal-dual algorithm for computation of generalized Nash equilibria via operator splitting methods. In: 2017 IEEE 56th Annual Conference on Decision and Control, IEEE 2017, pp. 3841-3846. DOI
[37] Zeng, X., Liang, S., Hong, Y., Chen, J.: Distributed computation of linear matrix equations: An optimization perspective. IEEE Trans. Automat. Control 64 (2018), 1858-1873. DOI | MR 3951032
[38] Zeng, X., Yi, P., Hong, Y.: Distributed continuous-time algorithm for constrained convex optimizations via nonsmooth analysis approach. IEEE Trans. Automat. Control 62 (2016), 5227-5233. DOI | MR 3708893
[39] Zhang, Y., Zavlanos, M.: A consensus-based distributed augmented Lagrangian method. In: 2018 Conference on Decision and Control, IEEE 2018, pp. 1763-1768. DOI
[40] Zhu, M., Martínez, S.: On distributed convex optimization under inequality and equality constraints. IEEE Trans. Automat. Control 57 (2011), 151-164. DOI | MR 2917654
Search
Partner of
