Partial Proximal Minimization Algorithms for Convex Pprogramming
Authors:
- Dimitri P. BertsekasDBDimitri P. Bertsekas
- Paul TsengPTPaul Tseng
- 1 August 1994
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Optimization
- Vol. 4 (3) , 551-572
Abstract
An extension of the proximal minimization algorithm is considered where only some of the minimization variables appear in the quadratic proximal term. The resulting iterates are interpreted in terms of the iterates of the standard algorithm, and a uniform descent property is shown that holds independently of the proximal terms used. This property is used to give simple convergence proofs of parallel algorithms where multiple processors simultaneously execute proximal iterations using different partial proximal terms. It is also shown that partial proximal minimization algorithms are dual to multiplier methods with partial elimination of constraints, and a relation is established between parallel proximal minimization algorithms and parallel constraint distribution algorithms.Keywords
This publication has 19 references indexed in Scilit:
- Convergence Analysis of a Proximal-Like Minimization Algorithm Using Bregman FunctionsSIAM Journal on Optimization, 1993
- Nonlinear Proximal Point Algorithms Using Bregman Functions, with Applications to Convex ProgrammingMathematics of Operations Research, 1993
- Proximal minimization algorithm withD-functionsJournal of Optimization Theory and Applications, 1992
- On the Douglas—Rachford splitting method and the proximal point algorithm for maximal monotone operatorsMathematical Programming, 1992
- Parallel Constraint DistributionSIAM Journal on Optimization, 1991
- Finite termination of the proximal point algorithmMathematical Programming, 1991
- On the Convergence of the Proximal Point Algorithm for Convex MinimizationSIAM Journal on Control and Optimization, 1991
- Two-Metric Projection Methods for Constrained OptimizationSIAM Journal on Control and Optimization, 1984
- Modified Lagrangians in convex programming and their generalizations1979
- Necessary and sufficient conditions for a penalty method to be exactMathematical Programming, 1975