%0 PDF
%T Optimization over digraphs: Linear algorithms with linear convergence
%A Xin, Ran.
%D 2018-06-04T10:04:04.934-04:00
%8 2018-06-04
%R http://localhost/files/vm40z387t
%X Abstract: In this thesis, we study distributed optimization, where a network of agents, in- teracting over a directed graph, collaborates to minimize the average of locally- known convex functions. Most of the existing algorithms apply push-sum consen- sus, which utilizes column-stochastic weight matrices. Column-stochastic weights require each agent to know (at least) its out degree, which may be impractical in e.g., broadcast-based communication protocols. In contrast, we describe FROST (Fast Row-stochastic Optimization with uncoordinated STep-sizes), an optimization algo- rithm applicable to directed graphs with row-stochastic weights and non-identical step-sizes at the agents. Its implementation is straightforward as each agent locally decides the weights assigned to the incoming information and locally chooses a suit- able step-size. Furthermore, we propose a completely linear algorithm which avoids using push-sum (type) techniques and thus leads to less communication and com- putation over the network of agents. Under the assumptions that each local function is strongly-convex with Lipschitz-continuous gradients, we show that the proposed algorithms linearly converge to the global minimizer with sufficiently small step- sizes. We present numerical simulations to illustrate our theoretical results.; Thesis (M.S.)--Tufts University, 2018.; Submitted to the Dept. of Electrical Engineering.; Advisor: Usman Khan.; Committee: Brian Tracey, and Babak Moaveni.; Keyword: Mathematics.
%[ 2018-10-10
%9 Text
%~ Tufts Digital Library
%W Institution