Communication and Computation in Large-Scale Distributed Optimization

Last decades have witnessed a surge of interest in developing distributed algorithms for solving large-scale optimization problems with multi-agent systems. The development of a standard distributed optimization algorithm can be typically summarized as two fundamental stages – communication and computation. Whereas the communication stage enables agents to collect the desired information from the entire network, the computation stage updates each agent’s local state towards the optimizer of the objective function. This dissertation focuses on the two key aspects of distributed optimization, develops a suite of new provable distributed algorithms for solving both deterministic and stochastic optimization problems, and further explores the opportunities of applying the distributed optimization techniques into real-world applications especially with multi-UAV systems. First, starting from the perspective of communication, a DGDx algorithm is proposed by incorporating multiple communication iterations into the consensus step. Second, observing that the standard DGD algorithm is a special case where the linear approximation is applied for the local objective functions, we develop a NetProx algorithm which generalizes the choice of approx- imation function for each agent and thus provides flexibility in the aspect of computation. The two proposed algorithms both offer great potential to balance the communication and computation in distributed optimization. In addition, we consider the issue of network communication attacks and devise a resilient algorithm for solving the specific distributed min-max problem. Two-stage stochastic programs are also studied and a DistPH algorithm is developed by adapting the classical PH method under a peer-to-peer multi-agent network. At last, two real-wold applications – distributed data fusion and distributed source tracking, both involved with the multi-UAV system, are investigated to demonstrate the superiority of the distributed optimization techniques. Theoretical analysis and numerical results are provided to validate the effectiveness of all proposed algorithms.