Vai ai contenuti. | Spostati sulla navigazione | Spostati sulla ricerca | Vai al menu | Contatti | Accessibilità

| Crea un account

Zanella, Filippo - Varagnolo, Damiano - Cenedese, Angelo - Pillonetto, Gianluigi - Schenato, Luca (2011) Newton-Raphson consensus for distributed convex optimization. [Rapporto tecnico]

Full text disponibile come:

[img]
Anteprima
Documento PDF (Contains the proofs of the offered propositions) - Versione pubblicata
418Kb

Abstract (inglese)

We study the problem of unconstrained distributed optimization in the context of multi-agents systems subject to limited communication connectivity. In particular we focus on the minimization of a sum of convex cost functions, where each component of the global function is available only to a specific agent and can thus be seen as a private local cost. The agents need to cooperate to compute the minimizer of the sum of all costs. We propose a consensus-like strategy to estimate a Newton-Raphson descending update for the local estimates of the global minimizer at each agent. In particular, the algorithm is based on the separation of time-scales principle and it is proved to converge to the global minimizer if a specific parameter that tunes the rate of convergence is chosen sufficiently small. We also provide numerical simulations and compare them with alternative distributed optimization strategies like the Alternating Direction Method of Multipliers and the Distributed Subgradient Method.


Statistiche Download - Aggiungi a RefWorks
Tipo di EPrint:Rapporto tecnico
Anno di Pubblicazione:12 Dicembre 2011
Parole chiave (italiano / inglese):distributed optimization, convex optimization, consensus algorithms, multi-agent systems, Newton-Raphson methods
Settori scientifico-disciplinari MIUR:Area 09 - Ingegneria industriale e dell'informazione > ING-INF/04 Automatica
Struttura di riferimento:Dipartimenti > Dipartimento di Ingegneria dell'Informazione
Codice ID:4293
Depositato il:29 Set 2011 15:20
Simple Metadata
Full Metadata
EndNote Format

Bibliografia

I riferimenti della bibliografia possono essere cercati con Cerca la citazione di AIRE, copiando il titolo dell'articolo (o del libro) e la rivista (se presente) nei campi appositi di "Cerca la Citazione di AIRE".
Le url contenute in alcuni riferimenti sono raggiungibili cliccando sul link alla fine della citazione (Vai!) e tramite Google (Ricerca con Google). Il risultato dipende dalla formattazione della citazione.

D. Puccinelli and M. Haenggi, ``Wireless sensor networks: applications and challenges of ubiquitous sensing,'' IEEE Circuits and Systems Magazine, vol. 5, no. 3, pp. 19 -- 31, 2005. Cerca con Google

A. Ipakchi and F. Albuyeh, ``Grid of the future - are we ready to transition to a smart grid?'' IEEE Power Energy Magazine, vol. 7, no. 2, pp. 52 -- 62, 2009. Cerca con Google

P. J. Huber, Robust statistics. John Wiley \& Sons Inc, 2009. Cerca con Google

S. Boyd, N. Parikh, E. Chu, B. Peleato, and J. Eckstein, ``Distributed Optimization and Statistical Learning via the Alternating Direction Method of Multipliers,'' Stanford Statistics Dept., Tech. Rep., 2010. Cerca con Google

J. N. Tsitsiklis, ``Problems in decentralized decision making and computation,'' Ph.D. dissertation, MIT, 1984. Cerca con Google

D. P. Bertsekas, A. Nedi\'c, and A. E. Ozdaglar, Convex Analysis and Optimization. Athena Scientific, 2003. Cerca con Google

S. Boyd and L. Vandenberghe, Convex Optimization. Cambridge University Press, 2004. Cerca con Google

D. P. Bertsekas and J. N. Tsitsiklis, Parallel and Distributed Computation: Numerical Methods.\hskip 1em plus 0.5em minus 0.4em\relax Athena Scientific, 1997. Cerca con Google

D. P. Bertsekas, Network Optimization: Continuous and Discrete Models. Belmont, Massachusetts: Athena Scientific, 1998. Cerca con Google

K. C. Kiwiel, ``Convergence of approximate and incremental subgradient methods for convex optimization,'' SIAM J. on Optim., vol. 14, no. 3, pp. 807 -- 840, 2004. Cerca con Google

B. Johansson, ``On distributed optimization in networked systems,'' Ph.D. dissertation, KTH Electrical Engineering, 2008. Cerca con Google

A. Nedi\'c and D. P. Bertsekas, ``Incremental subgradient methods for nondifferentiable optimization,'' SIAM J. on Optim., vol. 12, no. 1, pp. 109 -- 138, 2001. Cerca con Google

D. Blatt, A. Hero, and H. Gauchman, ``A convergent incremental gradient method with a constant step size,'' SIAM J. on Optim., vol. 18, no. 1, pp. 29 -- 51, 2007. Cerca con Google

S. S. Ram, A. Nedi\'c, and V. Veeravalli, ``Incremental stochastic subgradient algorithms for convex optimzation,'' SIAM J. on Optim., vol. 20, no. 2, pp. 691 -- 717, 2009. Cerca con Google

B. Johansson, M. Rabi, and M. Johansson, ``A randomized incremental subgradient method for distributed optimization in networked systems,'' SIAM J. on Optim., vol. 20, no. 3, pp. 1157 -- 1170, 2009. Cerca con Google

A. Nedi\'c, A. Ozdaglar, and P. A. Parrilo, ``Constrained consensus and optimization in multi-agent networks,'' IEEE TAC, vol. 55, no. 4, pp. 922 -- 938, 2010. Cerca con Google

A. Nedi\'c, ``Asynchronous broadcast-based convex optimization over a network,'' IEEE TAC, vol. PP, no. 99, pp. 1 -- 1, 2010. Cerca con Google

M. Rabbat and R. Nowak, ``Distributed optimization in sensor networks,'' in IPSN, 2004. Cerca con Google

B. Johansson, T. Keviczky, M. Johansson, and K. H. Johansson, ``Subgradient methods and consensus algorithms for solving convex optimization problems,'' in CDC, December 2008, pp. 4185 -- 4190. Cerca con Google

M. G. Rabbat, R. D. Nowak, and J. A. Bucklew, ``Generalized consensus computation in networked systems with erasure links,'' in Sig. Proc. Advances in Wireless Comm., June 2005, pp. 1088 -- 1092. Cerca con Google

L. Xiao, M. Johansson, and S. Boyd, ``Simultaneous routing and resource allocation via dual decomposition,'' IEEE Trans. on Comm., vol. 52, no. 7, pp. 1136 -- 1144, 2004. Cerca con Google

I. D. Schizas, A. Ribeiro, and G. B. Giannakis, ``Consensus in ad hoc WSNs with noisy links - part I: Distributed estimation of deterministic signals,'' IEEE Trans. on Sig. Proc., vol. 56, pp. 350 -- 364, 2008. Cerca con Google

C. Fischione, ``F-Lipschitz optimization with Wireless Sensor Networks applications,'' IEEE TAC, to appear, 2011. Cerca con Google

C. Fischione and U. J\"onsson, ``Fast-Lipschitz optimization with Wireless Sensor Networks applications,'' in IPSN, 2011. Cerca con Google

J. Van Ast, R. Bab\vska, and B. D. Schutter, ``Particle swarms in optimization and control,'' in IFAC World Congress, 2008. Cerca con Google

E. Alba and J. M. Troya, ``A survey of parallel distributed genetic algorithms,'' Complexity, vol. 4, no. 4, pp. 31 -- 52, 1999. Cerca con Google

R. O. Saber, J. Fax, and R. Murray, ``Consensus and cooperation in multi-agent networked systems,'' Proceedings of IEEE, vol. 95, no. 1, pp. 215--233, January 2007. Cerca con Google

F. Garin and L. Schenato, Networked Control Systems. Springer, 2011, ch. A Survey on distributed estimation and control applications using linear consensus algorithms, pp. 75--107. Cerca con Google

A. Nedi\'c and A. Ozdaglar, ``Distributed subgradient methods for multi-agent optimization,'' IEEE TAC, vol. 54, no. 1, pp. 48 -- 61, 2009. Cerca con Google

A. Nedi\'c and A. Ozdaglar, ``On the rate of convergence of distributed subgradient methods for multi-agent optimization,'' in CDC, 2007. Cerca con Google

A. Jadbabaie, A. Ozdaglar, and M. Zargham, ``A distributed Newton method for network optimization,'' in CDC, 2009. Cerca con Google

M. Zargham, A. Ribeiro, A. Ozdaglar, and A. Jadbabaie, ``Accelerated dual descent for network optimization,'' in ACC, 2011. Cerca con Google

P. Kokotovi\'c, H. K. Khalil, and J. O'Reilly, Singular Perturbation Methods in Control: Analysis and Design, ser. Classics in applied mathematics.\hskip 1em plus 0.5em minus 0.4em\relax SIAM, 1999, no. 25. Cerca con Google

H. K. Khalil, Nonlinear Systems, 3rd ed. Prentice Hall, 2001. Cerca con Google

L. Xiao, S. Boyd, and S. Lall, ``A scheme for robust distributed sensor fusion based on average consensus,'' in IPSN, 2005, pp. 63-- 70. Cerca con Google

S. Bolognani, S. D. Favero, L. Schenato, and D. Varagnolo, ``Consensus-based distributed sensor calibration and least-square parameter identification in wsns,'' International Journal of Robust and Nonlinear Control, vol. 20, no. 2, pp. 176--193, 2010. Cerca con Google

K. Tanabe, ``Global analysis of continuous analogues of the Levenberg-Marquardt and Newton-Raphson methods for solving nonlinear equations,'' Annals of the Institute of Statistical Mathematics, vol. 37, no. 1, pp. 189--203, 1985. Cerca con Google

R. Hauser and J. Nedi\'c, ``The continuous Newton-Raphson method can look ahead,'' SIAM J. on Optim., vol. 15, pp. 915 -- 925, 2005. Cerca con Google

A. R. Teel, D. Nesic, and P. V. Kokotovic, ``A note on input-to-state stability of sampled-data nonlinear systems,'' in CDC, vol. 3, December 1998, pp. 2473 -- 2478. Cerca con Google

V. Sundarapandian, ``Global asymptotic stability of nonlinear cascade systems,'' Applied Mathematics Letters, vol. 15, no. 3, pp. 275 -- 277, April 2002. Cerca con Google

Download statistics

Solo per lo Staff dell Archivio: Modifica questo record