Abstract
This paper presents a decomposition method for solving convex minimization problems. At each iteration, the algorithm computes two proximal steps in the dual variables and one proximal step in the primal variables. We derive this algorithm from Rockafellar's proximal method of multipliers, which involves an augmented Lagrangian with an additional quadratic proximal term. The algorithm preserves the good features of the proximal method of multipliers, with the additional advantage that it leads to a decoupling of the constraints, and is thus suitable for parallel implementation. We allow for computing approximately the proximal minimization steps and we prove that under mild assumptions on the problem's data, the method is globally convergent and at a linear rate. The method is compared with alternating direction type methods and applied to the particular case of minimizing a convex function over a finite intersection of closed convex sets.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
A. Auslender, “Numerical methods for nondifferentiable convex optimization,”Mathematical Programming Study 30 (1987) 102–126.
D.P. Bertsekas,Constrained Optimization and Lagrangian Multipliers (Academic Press, New York, 1982).
D.P. Bertsekas and J.N. Tsitsiklis,Parallel and Distributed Computation: Numerical Methods (Prentice-Hall, Englewood Cliffs, NJ, 1989).
J. Eckstein and D.P. Bertsekas, “On the Douglas—Rachford splitting method and the proximal point algorithm for maximal monotone operators,”Mathematical Programming 55 (1992) 293–318.
W. Findeisen, F.N. Bailey, M. Brdys, K. Malinowski, P. Tatjewski and A. Wozniak,Control and Coordination in Hierarchical Systems (Wiley, New York, 1980).
M. Fortin and R. Glowinski,Augmented Lagrangian Methods: Applications to the Solution of Boundary-Valued Problems (North-Holland, Amsterdam, 1983).
M. Fukushima, “Application of the alternating direction method of multipliers to separable convex programming problems,”Computational Optimization and Applications 1 (1992) 93–111.
D. Gabay, “Applications of the method of multipliers to variational inequalities,” in: M. Fortin and R. Glowinski, eds.,Augmented Lagrangian Methods: Applications to the Solution of Boundary-Valued Problems (North-Holland, Amsterdam, 1983) pp. 299–331.
D. Gabay and B. Mercier, “A dual algorithm for the solution of nonlinear variational problems via finiteelement approximations,”Computors and Mathematics with Applications 2 (1976) 17–40.
R. Glowinski and P. Le Tallec, “Augmented lagrangian and operator-splitting methods in nonlinear mechanics,” in:SIAM Studies in Applied Mathematics (SIAM, Philadelphia, PA, 1989).
R. Glowinski and A. Marrocco, “Sur l'approximation par éléments finis d'ordre un, et la résolution par pénalisation-dualité d'une classe de problèmes de Dirichlet nonlinéaires,”Revue Française d'Automatique, Informatique et Recherche Opérationelle 2 (1975) 41–76.
O. Guler, “On the convergence of the proximal point algorithm for convex minimization,”SIAM Journal on Control and Optimization 29 (1991) 403–419.
S.P. Han and G. Lou, “A parallel algorithm for a class of convex programs,”SIAM Journal on Control and Optimization 26 (1988) 345–355.
S. Ibaraki, M. Fukushima and T. Ibaraki, “Primal—dual proximal point algorithm for linearly constrained convex programming problems,” Technical Report, No. 91016, Kyoto University (Kyoto, Japan, 1991).
A.N. Iusem and A.R. De Pierro, “On the convergence of Han's method for convex programming with quadratic objective,”Mathematical Programming 52 (1991) 265–284.
L.S. Lasdon,Optimization Theory for Large Systems (Macmillan, New York, 1970).
B. Lemaire, “The proximal algorithm,”International Series of Numerical Mathematics 87 (1989) 73–87.
P.L. Lions and B. Mercier, “Splitting algorithms for the sum of two nonlinear operators,”SIAM Journal on Numerical Analysis 16 (1979) 964–979.
K. Mouallif, V.H. Nguyen and J.J. Strodiot, “A perturbed parallel decomposition method for a class of nonsmooth convex minimization problems,”SIAM Journal on Control and Optimization 29 (1991) 829–847.
B.T. Polyak,Introduction to Optimization (Optimization Software, New York, 1987).
R.T. Rockafellar,Convex Analysis (Princeton University Press, Princeton, NJ, 1970).
R.T. Rockafellar, “Augmented lagrangians and applications of the proximal point algorithm in convex programming,”Mathematics of Operations Research 1 (1976) 97–116.
R.T. Rockafellar, “Monotone operators and the proximal point algorithm,”SIAM Journal on Control and Optimization 14 (1976) 877–898.
J.E. Spingarn, “Applications of the method of partial inverses to convex programming: decomposition,”Mathematical Programming 32 (1985) 199–223.
G. Stephanopoulos and A.W. Westerberg, “The use of Hestenes' method of multipliers to resolve dual gaps in engineering system optimization,”Journal of Optimization Theory and Applications 15 (1975) 285–309.
A. Tanikawa and H. Mukai, “A new technique for nonconvex primal—dual decomposition,”IEEE Transactions on Automatic Control AC-30 (1985) 133–143.
P. Tseng, “Applications of a splitting algorithm to decomposition in convex programming and variational inequalities,”SIAM Journal on Control and Optimization 29 (1991) 119–138.
H. Uzawa, “Iterative methods for concave programming,” in: K.J. Arrow, L. Hurwicz and H. Uzawa, eds.,Studies in Linear and Nonlinear Programming (Stanford University Press, Stanford, CA, 1958) pp. 154–165.
Author information
Authors and Affiliations
Additional information
Corresponding author. Partially supported by Air Force Office of Scientific Research Grant 91-0008 and National Science Foundation Grant DMS-9201297.
Rights and permissions
About this article
Cite this article
Chen, G., Teboulle, M. A proximal-based decomposition method for convex minimization problems. Mathematical Programming 64, 81–101 (1994). https://doi.org/10.1007/BF01582566
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01582566