  


Newtonlike method with diagonal correction for distributed optimization
Dragana Bajovic(dbajovicuns.ac.rs) Abstract: We consider distributed optimization problems where networked nodes cooperatively minimize the sum of their locally known convex costs. A popular class of methods to solve these problems are the distributed gradient methods, which are attractive due to their inexpensive iterations, but have a drawback of slow convergence rates. This motivates the incorporation of secondorder information in the distributed methods, but this task is challenging: although the Hessians which arise in the algorithm design respect the sparsity of the network, their inverses are dense, hence rendering distributed implementations difficult. We overcome this challenge and propose a class of distributed Newtonlike methods, which we refer to as Distributed Quasi Newton (DQN). The DQN family approximates the Hessian inverse by: 1) splitting the Hessian into its diagonal and offdiagonal part, 2) inverting the diagonal part, and 3) approximating the inverse of the offdiagonal part through a weighted linear function. The approximation is parameterized by the tuning variables which correspond to different splittings of the Hessian and by different weightings of the offdiagonal Hessian part. Specific choices of the tuning variables give rise to different variants of the proposed general DQN method  dubbed DQN0, DQN1 and DQN2  which mutually tradeoff communication and computational costs for convergence. Simulations illustrate that the proposed DQN methods compare favorably with existing alternatives. Keywords: Distributed optimization, second order methods, Newtonlike methods, linear convergence. Category 1: Nonlinear Optimization Citation: Download: [PDF] Entry Submitted: 09/03/2015 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  