Optimization Online


Newton-like method with diagonal correction for distributed optimization

Dragana Bajovic(dbajovic***at***uns.ac.rs)
Dusan Jakovetic(djakovet***at***uns.ac.rs)
Natasa Krejic(natasak***at***uns.ac.rs)
Natasa Krklec Jerinkic(natasa.krklec***at***dmi.uns.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 second-order 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 Newton-like 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 off-diagonal part, 2) inverting the diagonal part, and 3) approximating the inverse of the off-diagonal 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 off-diagonal Hessian part. Specific choices of the tuning variables give rise to different variants of the proposed general DQN method -- dubbed DQN-0, DQN-1 and DQN-2 -- which mutually trade-off communication and computational costs for convergence. Simulations illustrate that the proposed DQN methods compare favorably with existing alternatives.

Keywords: Distributed optimization, second order methods, Newton-like methods, linear convergence.

Category 1: Nonlinear Optimization


Download: [PDF]

Entry Submitted: 09/03/2015
Entry Accepted: 09/03/2015
Entry Last Modified: 09/03/2015

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society