On the Rate of Convergence of a Partially Asynchronous Gradient Projection Algorithm
SIAM Journal on OptimizationPublished 1 November 1991Open access
Paul Tseng
Citations70
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
The rate of convergence of a partially asynchronous implementation of the gradient projection algorithm of Goldstein and Levitin and Polyak for the problem of minimizing a differentiable function over a closed convex set is analyzed.
Abstract
Recently, Bertsekas and Tsitsiklis proposed a partially asynchronous implementation 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 (i) the isocost surfaces of the objective function, restricted to the solution set, are properly separated and (ii) a certain multifunction associated with the problem is locally upper Lipschitzian, then this algorithm attains a linear rate of convergence.
Keywords
Computer ScienceEngineering
IEEE Transactions on Automatic ControlDistributed asynchronous deterministic and stochastic gradient optimization algorithms
2,021 Citations1986John N. Tsitsiklis, Dimitri P. Bertsekas +1 more
PROBLEMS IN DECENTRALIZED DECISION MAKING AND COMPUTATION
1,360 Citations1984Ιωάννης Τσιτσικλής
A scheme whereby a set of decision makers (processors) exchange and update tentative decisions which minimize a common cost function, given information they possess is considered; it is shown that they are guaranteed to converge to consensus.
Bulletin of the American Mathematical SocietyConvex programming in Hilbert space
622 Citations1964A. A. Goldstein
SIAM Journal on Control and OptimizationProjected Newton Methods for Optimization Problems with Simple Constraints
622 Citations1982Dimitri P. Bertsekas
Mathematical ProgrammingProjected gradient methods for linearly constrained problems
590 Citations1987Paul H. Calamai, Jorge J. Morè
It is shown that it is possible to develop a finite terminating quadratic programming algorithm without non-degeneracy assumptions and to apply these results to algorithms for linearly constrained problems.
IEEE Transactions on Automatic ControlOn the Goldstein-Levitin-Polyak gradient projection method
572 Citations1976Dimitri P. Bertsekas
Mathematical programming studiesSome continuity properties of polyhedral multifunctions
510 Citations1981Stephen M. Robinson
Journal of Optimization Theory and ApplicationsOn the convergence of the coordinate descent method for convex differentiable minimization
510 Citations1992Z.-Q. Luo, P. Tseng
Mathematical programming studiesGeneralized equations and their solutions, part II: Applications to nonlinear programming
368 Citations1982Stephen M. Robinson
Mathematical programming studiesProjection methods for variational inequalities with application to the traffic assignment problem
338 Citations1982Dimitri P. Bertsekas, Eli Gafni
SIAM Journal on Control and OptimizationTwo-Metric Projection Methods for Constrained Optimization
239 Citations1984Eli Gafni, Dimitri P. Bertsekas
SIAM Journal on Control and OptimizationOn the Linear Convergence of Descent Methods for Convex Essentially Smooth Minimization
201 Citations1992Zhi‐Quan Luo, Paul Tseng
The linear convergence of both the gradient projection algorithm of Goldstein and Levitin and Polyak, and a matrix splitting algorithm using regular splitting, is established, which does not require that the cost function be strongly convex or that the optimal solution set be bounded.
SIAM Journal on OptimizationError Bound and Convergence Analysis of Matrix Splitting Algorithms for the Affine Variational Inequality Problem
171 Citations1992Zhi‐Quan Luo, Paul Tseng
It is shown that the distance to a feasible point near the solution set can be bounded by the norm of a natural residual at that point, and this bound is used to prove linear convergence of a matrix splitting algorithm for solving the symmetric case of the affine variational inequality problem.
Mathematics of Operations ResearchA Posteriori Error Bounds for the Linearly-Constrained Variational Inequality Problem
165 Citations1987Jong‐Shi Pang
A posteriori error bound of an approximate solution to a linearly-constrained variational inequality problem is derived from three measures of error depending on a particular characterization of an exact solution and related to a certain class of iterative methods.
IEEE Transactions on Automatic ControlDistributed asynchronous optimal routing in data networks
142 Citations1986John N. Tsitsiklis, Dimitri P. Bertsekas
This work proves convergence of a distributed gradient projection method for optimal routing in a data communication network and takes into account the possibility of transients caused by updates in the routing strategy being used.
SIAM Journal on Control and OptimizationGlobal and Asymptotic Convergence Rate Estimates for a Class of Projected Gradient Processes
129 Citations1981J. C. Dunn
Journal of Optimization Theory and ApplicationsOn the convergence of projected gradient processes to singular critical points
102 Citations1987J. C. Dunn
Journal of Optimization Theory and ApplicationsOn the gradient-projection method for solving the nonsymmetric linear complementarity problem
39 Citations1984Yongling Cheng
GRADIENT PROJECTION TECHNIQUES FOR LARGE-SCALE OPTIMIZATION PROBLEMS
13 Citations1989Jorge J. Mor�