» Download Article
A Decomposition/Synchronization Scheme for Formulating and Solving Optimization Problems
Estimation and Control of Networked Systems, Volume # 1 | Part# 1
Authors
Anderson, James; Papachristodoulou, Antonis
Digital Object Identifier (DOI)
10.3182/20090924-3-IT-4005.00017
Page Numbers:
96-101
Index Terms
Decentralized and cooperative optimization; Consensus problems; Decentralized algorithms for computation over sensor networks
Abstract
Large-scale optimization problems, even when convex, can be challenging to solve directly. Recently, a considerable amount of research has focused on developing methods for solving such optimization problems in a distributed manner. The assumption that is usually made is that the global objective function is a sum of convex functions, which is restrictive. In this paper, we automatically decompose a convex function to be minimized into a sum of smaller functions that may or may not be convex and assign each sub-function to an agent in a networked system. Each agent is allowed to communicate with other agents in order to solve the original optimization problem. We propose an algorithm which will converge when the interaction between the agents is strong enough to lead to synchronization between common variables.
References
Bertsekas, D.P. and Tsitsiklis, J.N. (1989). Parallel and Distributed Computation: Numerical
Methods. Prentice Hall.
Boyd, S., Ghosh, A., Prabhakar, B., and Shah, D. (2006). Randomized gossip algorithms. IEEE Transactions on Imformation Theory, 52(6), 2508{2530.
Boyd, S. and Vandenberghe, L. (2004). Convex Optimization. Cambridge University Press.
Godsil, C. and Royle, G. (2000). Algebraic Graph Theory. Springer-Verlag, Inc.
Goemans, M.X. and Williamson, D.P. (1995). Improved approximation algorithms for maximum cut and satisfiability problems using semidefnite programming. Journal of the ACM, 42, 1115-1145.
Jadbabaie, A., Lin, J., and Morse, A.S. (2003). Coordination of groups of mobile autonomous agents using nearest neighbor rules. IEEE Transactions on Automatic Control, 48(60), 988-1001.
Karisch, S.E., Rendl, F., and Clausen, J. (2000). Solving graph bisection problems with semidefnite programming. INFORMS Journal on Computing, 12(3), 177-191.
Karypis, G. and Kumar, V. (1998). A fast and high quality multilevel scheme for partitioning irregular graphs. SIAM J. Sci. Comput., 20(1), 359{392.
Khalil, H.K. (2001). Nonlinear Systems. Prentice Hall, Inc., third edition.
Li, X. and Chen, G. (2003). Synchronization and desynchronization of complex dynamical networks: An engineering viewpoint. IEEE Transactions on Circuits and Systems-I: Fundamental Theory and Applications, 50(11), 1381-1390.
Nedic, A. and Ozdaglar, A. (2008). Convergence rate for consensus with delays. J. Glob Optim.
Nedic, A. and Ozdaglar, A. (2009). Distributed sub-gradient methods for multi-agent optimization. IEEE Transactions on Automatic Control, 54(1), 48-61.
Olfati-Saber, R. (2006). Flocking for multi-agent dynamic systems: Algorithms and theory. IEEE Transactions On Automatic Control, 51(3), 401-420.
Pecora, L.M. and Barahona, M. (2005). Synchronization of oscillators in complex networks. Chaos and Complexity Letters, 1(61).
Pecora, L.M. and Carroll, T.L. (1997). Master stability functions for synchronized coupled systems. Physical Review Letters, 80(10), 2109-2112.
Rantzer, A. (2008). Using game theory for distributed control engineering. Technical Report ISRN LUTFD2/TFRT--7620--SE, Department of Automatic Control, Lund University, Sweden. Presented at Games 2008, 3rd World Congress of the Game Theory Society.
Rantzer, A. (2009). Dynamic dual decomposition for distributed control. In Proceedings of American Control Conference. St. Louis.
Srikant, R. (2003). The Mathematics of Internet Congestion Control. BirkhÄauser.
Strogatz, S. (2003). SYNC: The emerging science of spontaneous order. Hyperion Press, New York.