×

Bundle-based decomposition: Conditions for convergence. (English) Zbl 0675.90068

Summary: Bundle-based decomposition is a recently proposed method for decentralized convex optimization. Computational tests indicate that it is very fast. In this paper we exhibit conditions for convergence of the method. In the process we study conditions for linearly-constrained approximate minimization of a convex function.

MSC:

90C25 Convex programming
65K05 Numerical mathematical programming methods
49M27 Decomposition methods

Software:

MINOS
PDFBibTeX XMLCite
Full Text: DOI Numdam EuDML

References:

[1] Ho, J. K.; Loute, E., An advanced implementation of the Dantzig-Wolfe decomposition algorithm for linear programming, (Dantzig, G. B.; Dempster, M. A.H.; Kallio, M., Large-Scale Linear Programming (1981), International Institute for Applied Systems Analysis: International Institute for Applied Systems Analysis Laxenburg, Austria), 425-460 · Zbl 0539.90063
[2] J. K. Ho and E. Loute, “DECOMP User’s Guide,” unpublished manuscript.
[3] Kato, T., Demicontinuity, hemicontinuity, and monotonicity II, Bull. Amer. Math. Soc., 70, 548-550 (1964) · Zbl 0123.10701
[4] Kato, T., Demicontinuity, hemicontinuity, and monotonicity. II, Bull. Amer. Math. Soc., 73, 886-889 (1967) · Zbl 0184.36504
[5] Lemaréchal, C.; Strodiot, J.-J.; Bihain, A., On a bundle algorithm for nonsmooth optimization, (Mangasarian, O. L.; Meyer, R. R.; Robinson, S. M., Nonlinear Programming 4 (1981), Academic Press: Academic Press New York), 245-282 · Zbl 0533.49023
[6] D. Medhi, “Decomposition of structured large scale optimization problems and parallel computing,” Dissertation, Computer Sciences Department, University of Wisconsin-Madison (Madison, WI 53706, 1987). See also two July 1988 manuscripts by this author: “Bundle-based decomposition for structured large-scale convex optimization problems: error estimate and computational experience,” and “Parallel bundle-based decomposition for large-scale structured mathematical programming problems,” AT&T Bell Laboratories, Holmdel, NJ 07733.
[7] Murtagh, B. A.; Saunders, M. A., MINOS 5.0 User’s Guide, Technical Report No. SOL 83-20 (December 1983), Systems optimization Laboratory, Department of Operations Research, Stanford University: Systems optimization Laboratory, Department of Operations Research, Stanford University Stanford, CA 94305
[8] Robinson, S. M., Bundle-based decomposition: Description and preliminary results, (Prékopa, A.; Szelezsán, J.; Strazicky, B., System Modelling and Optimization (1986), Springer-Verlag: Springer-Verlag Berlin), 751-756, Lecture Notes in Control and Information Sciences No. 84 · Zbl 0604.90098
[9] Rockafellar, R. T., Local boundedness of nonlinear, monotone operators, Michigan Mathematical Journal, 16, 397-407 (1969) · Zbl 0175.45002
[10] Strodiot, J.-J.; Nguyen, V. H.; Heukemes, N., ϵ- optimal solutions in nondifferentiable programming and some related questions, Math. Programming, 25, 307-328 (1983) · Zbl 0495.90067
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.