Distributed Algorithms to Convex Optimization Problems

This dissertation studies first a distributed algorithm to solve general convex optimizationproblems and then designs distributed algorithms to solve special optimization problemsrelated to a system of linear equations.First, a wider selection of step sizes is explored for the distributed subgradientalgorithm for multi-agent optimization problems with time-varying and balanced commu-nication topologies. The square summable requirement of the step sizes commonly adoptedin the literature is removed. The step sizes are only required to be positive, vanishingand non-summable, which provides the possibility for better convergence rates. Both un-constrained and constrained optimization problems are considered. It is proved that theagents’ estimates reach a consensus and converge to the minimizer of the global objectivefunction with the more general choice of step sizes. The best convergence rate is shown tobe the reciprocal of the square root of iterations for the best record of the function value atthe average of the agents’ estimates for the unconstrained case with the wider selection ofstep sizes.Then we design a distributed algorithm for a special optimization problem to findthe solution of the linear equations Ax = b with minimum energy, i.e. the minimum weightednorm associated with the weighted inner product. We first prove that for a special casewhen the norm is two-norm, the algorithm can make multiple agents reach the minimumtwo-norm solution of the global linear equations Ax = b if the agents are initialized atthe minimum two-norm solutions of their local equations. We then prove that if there arebounded initialization errors, the final convergence of the algorithm is also bounded awayfrom the minimum two-norm solution of the global linear equations. Next, we prove thecase with the two-norm replaced with a weighted norm associated with the weighted innerproduct.Next, we solve a system of linear equations Ax = b in a distributed way motivatedby a special subgradient algorithm. A discrete-time distributed algorithm to solve a systemof linear equations Ax = b is proposed. The algorithm can find a solution of Ax = b fromarbitrary initializations at a geometric rate when Ax = b has either unique or multiplesolutions. When Ax = b has a unique solution, the geometric convergence rate of thealgorithm is proved by analyzing the mixed norm of homogeneous M-Fejer type mappingsfrom the subgradient update. Then when Ax = b has multiple solutions, the geometricconvergence rate is proved through orthogonal decompositions of the agents’ estimates ontothe row space and null space of A, and the relationship between the initializations and thefinal convergence point is also specified. Quantitative upper bounds of the convergence ratefor two special cases are given.Finally, we investigate communication efficient distributed algorithm to solve Ax =b for matrices with a similar sparsity structure to that of the Laplacian matrix of communi-cation topology. We propose the algorithm based on gradient descent method with constantstep size and prove the convergence in finite time or at a linear rate. We also provide a wayto select the step sizes in a distributed way