Projected Primal-Dual Gradient Flow of Augmented Lagrangian with Application to Distributed Maximization of the Algebraic Connectivity of a Networ

Han Zhang, Jieqiang Wei, Peng Yi, Xiaoming Hu

Published 2017-01-25Version 1

In this paper, a projected primal-dual gradient flow of augmented Lagrangian is presented to solve convex optimization problems that are not necessarily strictly convex. The optimization variables are restricted by a simple convex set as well as equality constraints. Instead of choosing to project the negative gradient flow of the objective function onto the tangent cone of the entire feasible set of the convex optimization problem, we choose to use the projected primal-dual gradient flow of augmented Lagrangian so that the dynamics only projects the negative gradient flow of the primal variables onto the tangent cone of the simple convex set. Hence the complexity of calculating the tangent cone is decreased. We show that the projected dynamical system converges to one of the optimal solutions. We further explain the connection and difference between the continuous-time algorithm and proximal gradient method. Moreover, the problem of distributedly maximizing the algebraic connectivity of an undirected graph by optimizing the edge weights (communication gains for each channel) of each nodes is considered. The original semi-definite programming (SDP) problem is relaxed into a nonlinear programming (NP) problem that will be solved by the aforementioned projected dynamical system. Numerical examples show the convergence of the aforementioned algorithm to one of the optimal solution.