Accelerated Dual Descent for Network Optimization

Details Accelerated Dual Descent for Network Optimization Accelerated Dual Descent for Network Optimization

2011-04-06

arxiv.org/abs/1104.1157v1

Mathematics

Optimization and Control

Full version of a paper of the same name to appear in the proceedings of American Control Conference, 2011. (8 pages, 4 figure

Scientific paper

Dual descent methods are commonly used to solve network optimization problems because their implementation can be distributed through the network. However, their convergence rates are typically very slow. This paper introduces a family of dual descent algorithms that use approximate Newton directions to accelerate the convergence rate of conventional dual descent. These approximate directions can be computed using local information exchanges thereby retaining the benefits of distributed implementations. The approximate Newton directions are obtained through matrix splitting techniques and sparse Taylor approximations of the inverse Hessian.We show that, similarly to conventional Newton methods, the proposed algorithm exhibits superlinear convergence within a neighborhood of the optimal value. Numerical analysis corroborates that convergence times are between one to two orders of magnitude faster than existing distributed optimization methods. A connection with recent developments that use consensus iterations to compute approximate Newton directions is also presented.

Affiliated with

Also associated with

No associations

Rating

Accelerated Dual Descent for Network Optimization does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Accelerated Dual Descent for Network Optimization, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Accelerated Dual Descent for Network Optimization will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-418456