Font Size: a A A

Parallel And Distributed Optimization In-Network: Algorithms And Applications

Posted on:2014-11-03Degree:DoctorType:Dissertation
Country:ChinaCandidate:H FengFull Text:PDF
GTID:1108330464955568Subject:Circuits and Systems
Abstract/Summary:PDF Full Text Request
A conventional information processing system consists of four individual proce-dures, which are data collection, transfer, processing, and feedback control. The data collected by sensors are usually transferred to a data center by networks, where the center analyzes the data and sends out necessary control command to frond end ex-ecutive devices by the network again. However, this mode suffers from three main deficiencies, which are the end-to-end capacity bound of a network, the long delay of a multi-hop link, and the lack of robustness as a system.The information processing in-network aims to integrate the four procedures into a network, where the network is not only the source and storage of the data, but also acts as the transfer, processor and the executants for control commands. This mode can overcome the three deficiencies mentioned above effectively. The optimization in-network attracts widely interests recently, since the optimization problem is the fundamental form of many research areas, such as signal processing, pattern recogni-tion, machine learning and communication theory. Meanwhile, it is natural to be for-mulized as optimization problems for the collaboration, transfer, and energy con-straints in a network.We will investigate the parallel and distributed optimization methods in-network this dissertation. There are mainly two issues to consider for an in-network solver. One is how to decouple a centralized optimization problem in a parallel or distributed way. The other is to design a feasible and proper information exchanging strategy, which can reduce the communication cost in computation as much as possible.The classic optimization theory is the foundation of our works, which is briefly introduced in Chapter 2, including the general solution to unconstrained and con-strained optimization problems. We also give a brief survey on parallel and distributed optimization methods by decomposition. In the end of Chapter 2, we provides two equivalent transformation cases from a constrained optimization problem to an un-constrained form, as the latter is easier to be processed in a parallel or distributed way.There are mainly three communication strategies for an in-network optimization, which are local fusion, point-to-point relay, and local broadcast. Most algorithms via local fusion treat the variables in the same way, while the variables introduced in de-coupling are with different levels of calculation difficulties. In view of this point, we propose two kinds of hybrid algorithms for various cases in Chapter 3 and Chapter 4, which treats the variables in a different way alternatively. The objective solved in Chapter 3 is a general bi-variables function, while the objective solved in Chapter 3 is a sum of non-differential convex functions with local feasible sets. In both chapters, the multiple processing nodes communicate with each other by local fusion, which avoids the global information exchanging and then reduce the communication cost. The simulation results show that the proposed algorithms have advantages both on computational and communicational complexity.Although the local fusion way does not need the global information exchanging, each node still needs the data from all its neighbors to update its own data, which is not efficient enough in communication. The recently developed incremental subgra-dient algorithms are introduced in Chapter 5, which use the point-to-point relay mode in communication in contrast to the local fusion way in the first two chapters. The al-gorithm is applied to various distributed signal estimation tasks in-network, where the results show that the relay mode is more efficient in communication.In order to improve the parallelism degree while maintaining a low communica-tion cost, we propose a distributed optimization algorithm via random broadcast. Each node diffuses its data to neighbors by collisional random broadcast, and the success-fully received nodes do local calculation.Various applications are presented as examples in all chapters, while the algo-rithms proposed in this dissertation are not developed for specific applications. In fact, they can be used to solve any proper practical problems with similar mathematic forms. The future works on optimization in-network can be developed in several as-pects, such as introducing the transmission delay, the switching topology, and the quantization before transmission.
Keywords/Search Tags:Parallel Optimization, Distributed Optimization, Computation in-Network, Collaborative Signal Processing, Method of Multipliers, Incremental Subgradient, Consensus, Random Broadcast Gossip
PDF Full Text Request
Related items