zbMATH — the first resource for mathematics

Geometry Search for the term Geometry in any field. Queries are case-independent.
Funct* Wildcard queries are specified by * (e.g. functions, functorial, etc.). Otherwise the search is exact.
"Topological group" Phrases (multi-words) should be set in "straight quotation marks".
au: Bourbaki & ti: Algebra Search for author and title. The and-operator & is default and can be omitted.
Chebyshev | Tschebyscheff The or-operator | allows to search for Chebyshev or Tschebyscheff.
"Quasi* map*" py: 1989 The resulting documents have publication year 1989.
so: Eur* J* Mat* Soc* cc: 14 Search for publications in a particular source with a Mathematics Subject Classification code (cc) in 14.
"Partial diff* eq*" ! elliptic The not-operator ! eliminates all results containing the word elliptic.
dt: b & au: Hilbert The document type is set to books; alternatively: j for journal articles, a for book articles.
py: 2000-2015 cc: (94A | 11T) Number ranges are accepted. Terms can be grouped within (parentheses).
la: chinese Find documents in a given language. ISO 639-1 language codes can also be used.

a & b logic and
a | b logic or
!ab logic not
abc* right wildcard
"ab c" phrase
(ab c) parentheses
any anywhere an internal document identifier
au author, editor ai internal author identifier
ti title la language
so source ab review, abstract
py publication year rv reviewer
cc MSC code ut uncontrolled term
dt document type (j: journal article; b: book; a: book article)
Parallel alternating direction multiplier decomposition of convex programs. (English) Zbl 0797.90075
Summary: This paper describes two specializations of the alternating direction method of multipliers: the alternating step method and the epigraphic projection method. The alternating step method applies to monotropic programs, while the epigraphic method applies to general block-separable convex programs, including monotropic programs as a special case. The epigraphic method resembles an earlier parallel method due to Spingarn, but solves a larger number of simpler subproblems at each iteration. This paper gives convergence results for both the alternating step and epigraphic methods, and compares their performance on random dense separable quadratic programs.

90C25Convex programming
65Y05Parallel computation (numerical methods)
Full Text: DOI
[1] Bertsekas, D. P.,Constrained Optimization and Lagrange Multiplier Methods, Academic Press, New York, New York, 1982. · Zbl 0572.90067
[2] Glowinski, R., andMarroco, A.,Sur l’Approximation, par Elements Finis d’Ordre Un, et la Resolution, par Penalisation-Dualité, d’une Classe de Problèmes de Dirichlet Nonlineares, Revue Française d’Automatique, Informatique et Recherche Opérationelle, Series R, Vol. 9, pp. 41--76 1975.
[3] Gabay, D., andMercier, B.,A Dual Algorithm for the Solution of Nonlinear Variational Problems via Finite Element Approximations, Computers and Mathematics with Applications, Vol. 2, pp. 17--40, 1976. · Zbl 0352.65034 · doi:10.1016/0898-1221(76)90003-1
[4] Fortin, M., andGlowinski, R.,On Decomposition-Coordination Methods Using an Augmented Lagrangian, Augmented Lagrangian Methods: Applications to the Solution of Boundary-Value Problems, Edited by M. Fortin and R. Glowinski, North-Holland, Amsterdam, Holland, pp. 97--145, 1983.
[5] Gabay, D.,Applications of the Method of Multipliers to Variational Inequalities, Augmented Lagrangian Methods: Applications to the Solution of Boundary-Value Problems, Edited by M. Fortin and R. Glowinski, North-Holland, Amsterdam, Holland, pp. 299--331, 1983.
[6] Lions, P. L., andMercier, B.,Splitting Algorithms for the Sum of Two Nonlinear Operators, SIAM Journal on Numerical Analysis, Vol. 16, pp. 964--979, 1979. · Zbl 0426.65050 · doi:10.1137/0716071
[7] Eckstein, J., andBertsekas, D. P.,On the Douglas-Rachford Splitting Method and the Proximal Point Algorithm for Maximal Monotone Operators, Mathematical Programming, Vol. 55, pp. 293--318, 1992. · Zbl 0765.90073 · doi:10.1007/BF01581204
[8] Glowinski, R., andLe Tallec, P.,Augmented Lagrangian Methods for the Solution of Variational Problems, MRC Technical Summary Report No. 2965, University of Wisconsin, 1987.
[9] Bertsekas, D. P., andTsitsiklis, J.,Parallel and Distributed Computation: Numerical Methods, Prentice-Hall, Englewood Cliffs, New Jersey, 1989. · Zbl 0743.65107
[10] Rockafellar, R. T.,Network Flows and Monotropic Optimization, John Wiley, New York, New York, 1984. · Zbl 0596.90055
[11] Eckstein, J.,Splitting Methods for Monotone Operators with Applications to Parallel Optimization, PhD Thesis, Massachusetts Institute of Technology, 1989.
[12] Spingarn, J. E.,Application of the Method of Partial Inverses to Convex Programming: Decomposition, Mathematical Programming, Vol. 32, pp. 199--233, 1985. · Zbl 0565.90058 · doi:10.1007/BF01586091
[13] Rockafellar, R. T.,Convex Analysis, Princeton University Press, Princeton, New Jersey, 1970. · Zbl 0193.18401
[14] Eckstein, J.,The Alternating Step Method for Monotropic Programming on the Connection Machine CM-2, ORSA Journal on Computing, Vol. 5, pp. 84--96, 1993. · Zbl 0773.90055
[15] Nielsen, S. S., andZenios, S. A.,Massively Parallel Algorithms for Singly Constrained Nonlinear Programs, ORSA Journal on Computing, Vol. 4, pp. 166--1981, 1992.
[16] Zenios, S. A., andCensor, Y.,Massively Parallel Row Action Algorithms for Some Nonlinear Transportation Problems, SIAM Journal on Optimization, Vol. 3, pp. 373--400, 1991. · Zbl 0754.90057 · doi:10.1137/0801024
[17] Eckstein, J., andFerris, M. C.,Operator Splitting Methods for Monotone Linear Complementarity Problems, Technical Report TMC-239, Thinking Machines Corporation, 1992.
[18] Eckstein, J., andBertsekas, D. P.,An Alternating Direction Method for Linear Programming, Working Paper 90-063, Harvard Business School, 1990.
[19] Klingman, D., Napier, A., andStutz, J.,NETGEN: A Program for Generating Large-Scale Uncapacitated Assignment, Transportation, and Minimum Cost Network Problems, Management Science, Vol. 20, pp. 814--822, 1974. · Zbl 0303.90042 · doi:10.1287/mnsc.20.5.814
[20] Rockafellar, R. T.,Augmented Lagrangians and Applications of the Proximal Point Algorithm in Convex Programming, Mathematics of Operations Research, Vol. 1, pp. 97--116, 1976. · Zbl 0402.90076 · doi:10.1287/moor.1.2.97
[21] Spingarn, J. E.,Partial Inverse of a Monotone Operator, Applied Mathematics and Optimization, Vol. 10, pp. 247--265, 1983. · Zbl 0524.90072 · doi:10.1007/BF01448388