In this talk we present randomized block coordinate descent methods for minimizing convex optimization problems with linearly coupled constraints over networks and show that they obtain in expectation an ε-accurate solution in at most O(N/ε) iterations, where N is the number of nodes in the network. However, the computational complexity per iteration of these methods is much simpler than the one of a method based on full gradient information and each iteration can be computed in a distributed way. We focus on how to choose the probabilities to make these randomized algorithms to converge as fast as possible and we arrive at solving sparse SDPs. Analysis for rate of convergence in probability is also provided. For strongly convex functions we show that these distributed algorithms converge linearly. We also discuss the extension of these algorithms to composite convex optimization and nonconvex optimization and show that similar results hold. Finally, we provide some numerical applications and comparisons with alternative strategies from the literature.
Current 2019 2018 2017 2016 2015 2014 2013 2012 2011 2010 2009 2008 2007 2006 2005 2004 2003 2002 2001 2000 1999 1998 1997 1996
