Distributed Newton-type algorithms for network resource allocation
Thesis (S.M.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2010.
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Language: | eng |
| Published: |
Massachusetts Institute of Technology
2011
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/1721.1/60822 |
| _version_ | 1826200383292178432 |
|---|---|
| author | Wei, Ermin |
| author2 | Asuman Ozdaglar. |
| author_facet | Asuman Ozdaglar. Wei, Ermin |
| author_sort | Wei, Ermin |
| collection | MIT |
| description | Thesis (S.M.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2010. |
| first_indexed | 2024-09-23T11:35:33Z |
| format | Thesis |
| id | mit-1721.1/60822 |
| institution | Massachusetts Institute of Technology |
| language | eng |
| last_indexed | 2024-09-23T11:35:33Z |
| publishDate | 2011 |
| publisher | Massachusetts Institute of Technology |
| record_format | dspace |
| spelling | mit-1721.1/608222019-04-11T04:48:23Z Distributed Newton-type algorithms for network resource allocation Wei, Ermin Asuman Ozdaglar. Massachusetts Institute of Technology. Dept. of Electrical Engineering and Computer Science. Massachusetts Institute of Technology. Dept. of Electrical Engineering and Computer Science. Electrical Engineering and Computer Science. Thesis (S.M.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2010. Cataloged from PDF version of thesis. Includes bibliographical references (p. 99-101). Most of today's communication networks are large-scale and comprise of agents with local information and heterogeneous preferences, making centralized control and coordination impractical. This motivated much interest in developing and studying distributed algorithms for network resource allocation problems, such as Internet routing, data collection and processing in sensor networks, and cross-layer communication network design. Existing works on network resource allocation problems rely on using dual decomposition and first-order (gradient or subgradient) methods, which involve simple computations and can be implemented in a distributed manner, yet suffer from slow rate of convergence. Second-order methods are faster, but their direct implementation requires computation intensive matrix inversion operations, which couple information across the network, hence cannot be implemented in a decentralized way. This thesis develops and analyzes Newton-type (second-order) distributed methods for network resource allocation problems. In particular, we focus on two general formulations: Network Utility Maximization (NUM), and network flow cost minimization problems. For NUM problems, we develop a distributed Newton-type fast converging algorithm using the properties of self-concordant utility functions. Our algorithm utilizes novel matrix splitting techniques, which enable both primal and dual Newton steps to be computed using iterative schemes in a decentralized manner with limited information exchange. Moreover, the step-size used in our method can be obtained via an iterative consensus-based averaging scheme. We show that even when the Newton direction and the step-size in our method are computed within some error (due to finite truncation of the iterative schemes), the resulting objective function value still converges superlinearly to an explicitly characterized error neighborhood. Simulation results demonstrate significant convergence rate improvement of our algorithm relative to the existing subgradient methods based on dual decomposition. The second part of the thesis presents a distributed approach based on a Newtontype method for solving network flow cost minimization problems. The key component of our method is to represent the dual Newton direction as the limit of an iterative procedure involving the graph Laplacian, which can be implemented based only on local information. Using standard Lipschitz conditions, we provide analysis for the convergence properties of our algorithm and show that the method converges superlinearly to an explicitly characterized error neighborhood, even when the iterative schemes used for computing the Newton direction and the stepsize are truncated. We also present some simulation results to illustrate the significant performance gains of this method over the subgradient methods currently used. by Ermin Wei. S.M. 2011-01-26T14:30:17Z 2011-01-26T14:30:17Z 2010 2010 Thesis http://hdl.handle.net/1721.1/60822 696814695 eng M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission. http://dspace.mit.edu/handle/1721.1/7582 101 p. application/pdf Massachusetts Institute of Technology |
| spellingShingle | Electrical Engineering and Computer Science. Wei, Ermin Distributed Newton-type algorithms for network resource allocation |
| title | Distributed Newton-type algorithms for network resource allocation |
| title_full | Distributed Newton-type algorithms for network resource allocation |
| title_fullStr | Distributed Newton-type algorithms for network resource allocation |
| title_full_unstemmed | Distributed Newton-type algorithms for network resource allocation |
| title_short | Distributed Newton-type algorithms for network resource allocation |
| title_sort | distributed newton type algorithms for network resource allocation |
| topic | Electrical Engineering and Computer Science. |
| url | http://hdl.handle.net/1721.1/60822 |
| work_keys_str_mv | AT weiermin distributednewtontypealgorithmsfornetworkresourceallocation |