Rate of Convergence of a Partially Asynchronous Gradient Projection Algorithm

摘要

Recently, Bertsekas and Tsitsiklis proposed a partially asynchronousimplementation of the gradient projection algorithm of Goldstein and Levitin and Polyak for the problem of minimizing a differentiable function over a closed convex set. In this paper, the rate of convergence of this algorithm is analyzed. It is shown that if the standard assumptions hold (that is, the solution set is nonempty and the gradient of the function is Lipschitz continuous) and (1) the isocost surfaces of the objective function, restricted to the solution set, are properly separated and (2) a certain multifunction associated with the problem is locally upper Lipschitzian. then this algorithm attains a linear rate of convergence.