# zbMATH — the first resource for mathematics

##### Examples
 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.

##### Operators
 a & b logic and a | b logic or !ab logic not abc* right wildcard "ab c" phrase (ab c) parentheses
##### Fields
 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)
Applications of the method of partial inverses to convex programming: Decomposition. (English) Zbl 0565.90058
A primal-dual decomposition method is presented to solve the separable convex programming problem. Convergence to a solution and Lagrange multiplier vector occurs from an arbitrary starting point. The method is equivalent to the proximal point algorithm applied to a certain maximal monotone multifunction. In the nonseparable case, it specializes to a known method, the proximal method of multipliers. Conditions are provided which guarantee linear convergence.

##### MSC:
 90C25 Convex programming 90C55 Methods of successive quadratic programming type 65K05 Mathematical programming (numerical methods) 90C06 Large-scale problems (mathematical programming)
##### References:
 [1] K.J. Arrow and L. Hurwicz, ”Decentralization and computation in resource allocation”, in: R.W. Pfouts, ed.,Essays in economics and econometrics, University of North Carolina Press, Chapel Hill, N.C.; also in K.J. Arrow and L. Hurwicz, eds.,Studies in resource allocation processes (Cambridge University Press, 1977). [2] D.P. Bertsekas, ”Convexification procedures and decomposition methods for nonconvex optimization problems”,Journal of Optimization Theory and Applications 29 (1979), 169–197. · Zbl 0389.90080 · doi:10.1007/BF00937167 [3] G. Cohen, ”Optimization by decomposition and coordination: A unified approach”, IEEE Transactions on Automatic Control, Vol. AC-23 (1978) 222–232. [4] G. Cohen, ”Auxiliary problem principle and decomposition of optimization problems”,Journal of Optimization Theory and Applications 32 (1980) 277–305. · Zbl 0417.49046 · doi:10.1007/BF00934554 [5] G.B. Dantzig and P. Wolfe, ”Decomposition principle for linear programs”,Operations Research 8 (1960) 101–111. · Zbl 0093.32806 · doi:10.1287/opre.8.1.101 [6] G.B. Dantzig,Linear programming and extensions (Princeton University Press, Princeton, NJ, 1963). [7] I. Ekeland and R. Temam, Convex analysis and variational problems (North-Holland, 1976). [8] H. Everett, ”Generalized Lagrange multiplier method for solving problems of optimum allocation of resources”,Operations Research 11 (1963) 399–417. · Zbl 0113.14202 · doi:10.1287/opre.11.3.399 [9] A.V. Fiacco, ”Sensitivity analysis for nonlinear programming using penalty methods”,Mathematical Programming 10 (1976) 287–311. · Zbl 0357.90064 · doi:10.1007/BF01580677 [10] W. Findeisen, F.N. Bailey, M. Brdyś, K. Malinowski, P. Tatjewski and A. Woźniak,Control and coordination in hierarchical systems (John Wiley & Sons, 1980). [11] M. Fortin and R. Glowinski, ”On decomposition-coordination methods using an augmented Lagrangian”, in: M. Fortin and R. Glowinski, eds.,Augmented Lagrangian methods: Applications to the numerical solution of boundary-value problems, Studies in Mathematics and its Applications 15 (North-Holland, 1983). [12] M. Frank and P. Wolfe, ”An algorithm for quadratic programming”,Naval Research Logistics Quarterly 3 (1956) 95–110. · doi:10.1002/nav.3800030109 [13] D. Gabay and B. Mercier, ”A dual algorithm for the solution of nonlinear variational problems via finite element approximation”,Computers and Mathematics with Applications 2 (1976) 17–40. · Zbl 0352.65034 · doi:10.1016/0898-1221(76)90003-1 [14] D. Gabay, ”Applications of the method of multipliers to variational inequalities”, in: M. Fortin and R. Glowinski, eds.,Augmented Lagrangian methods: Applications to the numerical solution of boundary-value problems (North-Holland, Amsterdam, 1983). [15] A.M. Geoffrion, ”Primal resource-directive approaches for optimizing nonlinear decomposable systems”,Operations Research 18 (1970) 375–403. · Zbl 0201.22301 · doi:10.1287/opre.18.3.375 [16] A. Geoffrion, ”Large-scale linear and nonlinear programming”, in: D.A. Wismer, ed.,Optimization methods for large-scale systems with applications (McGraw-Hill, New York, 1971). [17] M.R. Hestenes, ”Multiplier and gradient methods”,Journal of Optimization Theory and Applications (1969) 303–320. [18] L.S. Lasdon,Optimization theory for large systems (Macmillan, Toronto 1970). [19] L.S. Lasdon, ”Decomposition in resource allocation”, in: D.M. Himmelblau, ed.,Decomposition of large-scale problems (North-Holland, 1973) 207–231. [20] F.J.R. Luque, ”Asymptotic convergence analysis of the proximal point algorithm”,SIAM Journal of Control and Optimization 22 (1984) 277–293. · Zbl 0533.49028 · doi:10.1137/0322019 [21] B. Martinet, ”Determination approchée d’un point fixe d’une application pseudo-contractante. Cas de l’application prox”,Comptes Rendus des Séances de l’Académie des Sciences, Série A 274 (1972) 163–165. [22] G.J. Minty, ”Monotone (nonlinear) operators in Hilbert space”,Duke Mathematical Journal 29 (1962) 341–346. · Zbl 0111.31202 · doi:10.1215/S0012-7094-62-02933-2 [23] M.J.D. Powell, ”A method for nonlinear constraints in minimization problems”, in: R. Fletcher, ed.,Optimization (Academic Press, NY, 1969) 283–298. [24] S.M. Robinson, ”Perturbed Kuhn-Tucker points and rates of convergence for a class of nonlinear programming problems”,Mathematical Programming 7 (1974) 1–16. · Zbl 0294.90078 · doi:10.1007/BF01585500 [25] R.T. Rockafellar, ”On the maximal monotonicity of subdifferential mappings”,Pacific Journal of Mathematics 33 (1970) 209–216. [26] R.T. Rockafellar,Convex analysis (Princeton University Press, Princeton, N.J. 1970). [27] R.T. Rockafellar, ”The multiplier method of Hestenes and Powell applied to convex programming”,Journal of Optimization Theory and Applications 12 (1973) 555–562. · Zbl 0254.90045 · doi:10.1007/BF00934777 [28] R.T. Rockafellar, ”Augmented Lagrangians and applications of the proximal point algorithm in convex programming”,Mathematics of Operations Research 1 (1976) 97–116. · Zbl 0402.90076 · doi:10.1287/moor.1.2.97 [29] R.T. Rockafellar, ”Monotone operators and the proximal point algorithm”,SIAM Journal on Control and Optimization 14 (1976) 877–898. · Zbl 0358.90053 · doi:10.1137/0314056 [30] R.T. Rockafellar, ”Monotone operators and augmented Lagrangian methods in nonlinear programming”, in: O.L. Mangasarian et al., eds.,Nonlinear Programming $·$3 (Academic Press, NY, 1978) 21–25. [31] R.T. Rockafellar, ”Solving a nonlinear program by way of a dual problem”,Symposia Mathematica 19 (1976) 135–160. [32] J.E. Spingarn, ”Fixed and variable constraints in sensitivity analysis”, SIAM Journal on Control and Optimization 18 (1980) 297–310. · Zbl 0434.90085 · doi:10.1137/0318021 [33] J.E. Spingarn, ”A proximal algorithm for decomposable convex programming”, summary abstract of this paper in Abstracts of the American Mathematical Society 6, October 1982. [34] J.E. Spingarn, ”Partial inverse of a monotone operator”,Applied Mathematics and Optimization 10 (1983) 247–265. · Zbl 0524.90072 · doi:10.1007/BF01448388 [35] J.E. Spingarn, ”A primal-dual projection method for solving systems of linear inequalities”,Linear Algebra and its Applications 65 (1985) 45–62. · Zbl 0564.65044 · doi:10.1016/0024-3795(85)90086-2 [36] J.E. Spingarn, ”A projection method for least square solutions to overdetermined systems of linear inequalities”, to appear. [37] G. Stephanopoulos and 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. · Zbl 0278.49040 · doi:10.1007/BF00933339 [38] H. Uzawa, ”Iterative methods for concave programming”, in: K. Arrow, L. Hurwicz, and H. Uzawa, eds.,Studies in Linear and Nonlinear Programming (Stanford University Press, Stanford, Ca, 1958). [39] N. Watanabe, Y. Nishimura and M. Matsubara, ”Decomposition in large system optimization using the method of multipliers”,Journal of Optimization Theory and Applications 25 (1978) 181–193. · Zbl 0363.90105 · doi:10.1007/BF00933211