Previous |  Up |  Next


Title: Solving convex program via Lagrangian decomposition (English)
Author: Knobloch, Matthias
Language: English
Journal: Kybernetika
ISSN: 0023-5954
Volume: 40
Issue: 5
Year: 2004
Pages: [595]-610
Summary lang: English
Category: math
Summary: We consider general convex large-scale optimization problems in finite dimensions. Under usual assumptions concerning the structure of the constraint functions, the considered problems are suitable for decomposition approaches. Lagrangian-dual problems are formulated and solved by applying a well-known cutting-plane method of level-type. The proposed method is capable to handle infinite function values. Therefore it is no longer necessary to demand the feasible set with respect to the non-dualized constraints to be bounded. The paper primarily deals with the description of an appropriate oracle. We first discuss the realization of the oracle under appropriate assumptions for generic convex problems. Afterwards we show that for convex quadratic programs the algorithm of the oracle is universally applicable. (English)
Keyword: level method
Keyword: cutting-plane methods
Keyword: decomposition methods
Keyword: convex programming
Keyword: nonsmooth programming
MSC: 65K05
MSC: 90C06
MSC: 90C25
MSC: 90C30
idZBL: Zbl 1249.90198
idMR: MR2120999
Date available: 2009-09-24T20:04:10Z
Last updated: 2015-03-23
Stable URL:
Reference: [1] Auslender A.: Existence of optimal solutions and duality results under weak conditions.Math. Programming 88 (2001), 45–59 Zbl 0980.90063, MR 1765892, 10.1007/PL00011377
Reference: [2] Beer K., Gol’stejn E. G., Sokolov N. A.: Minimization of a nondifferentiable, convex function, defined not everywhere.Optimization 51 (2002), 6, 819–840 Zbl 1036.65050, MR 1941716, 10.1080/0233193021000066446
Reference: [3] Beer K., Gol’stejn E. G., Sokolov N. A.: Utilization of the Level-method for Primal Decomposition in Linear Programming Problems.Preprint 2000–13, Faculty of Mathematics, University of Technology, Chemnitz 2000
Reference: [4] Beer K., Knobloch M.: Utilization of the Level Method for Dual Decomposition in Convex Quadratic Programming.Preprint 2002-4, Faculty of Mathematics, University of Technology, Chemnitz 2002
Reference: [5] Belousov E. G.: Introduction to Convex Analysis and Integer Programming (in Russian).Izdatel’stvo Moskovskogo Universiteta, Moskau 1977 MR 0475840
Reference: [6] Ekeland I., Témam R.: Convex analysis and variational problems.Unabridged, corrected republication of the 1976 English original. Society for Industrial and Applied Mathematics (SIAM), Philadelphia 1999 Zbl 0322.90046, MR 1727362
Reference: [7] Goffin J. L., Vial J. P.: Convex nondifferentiable optimization: a survey focused on the analytic center cutting plane method.Optimization Methods and Software 17 (2002), 5, 805–867 Zbl 1065.90060, MR 1953822, 10.1080/1055678021000060829a
Reference: [8] Kiwiel K. C.: Methods of Descent for Nondifferentiable Optimization.(Lecture Notes in Mathematics 1133), Springer Verlag, Heidelberg 1985 Zbl 0561.90059, MR 0797754
Reference: [9] Kiwiel K. C.: Proximal level bundle methods for convex nondifferentiable optimization, saddle-point problems and variational inequalities.Math. Programming 69B (1995), 89–105 Zbl 0857.90101, MR 1354433, 10.1007/BF01585554
Reference: [10] Lémarechal C., Nemirovskii, A., Nesterov Y.: New variants of bundle methods.Math. Programming 69 (1995), 111–147 MR 1354434, 10.1007/BF01585555
Reference: [11] Nožička F., Guddat J., Hollatz, H., Bank B.: Theorie der linearen parametrischen Optimierung.Akademie Verlag, Berlin 1974 Zbl 0284.90053
Reference: [12] Mifflin R.: An algorithm for constrained optimization with semi-smooth functions.Math. Oper. Res. 2 (1997), 2, 191–207 MR 0474815, 10.1287/moor.2.2.191
Reference: [13] Richter K.: Lösungsverfahren für konvexe Optimierungsaufgaben mit Umrandungsstruktur auf der Grundlage gleichzeitiger primal-dualer Dekomposition.Dissertation, TU Chemnitz 2000 Zbl 1130.90300, MR 1870565
Reference: [14] Shor N. Z.: Minimization Methods for Non-differentiable Functions.Springer Verlag, Berlin 1985 Zbl 0561.90058, MR 0775136
Reference: [15] Tuy H.: Convex Analysis and Global Optimization.Kluwer, Dordrecht 1998 Zbl 0904.90156, MR 1615096
Reference: [16] Unger T.: Erweiterungen der Levelmethode zur Lösung konvexer Optimierungsaufgaben.Dissertation, Shaker Verlag, Aachen 2003


Files Size Format View
Kybernetika_40-2004-5_6.pdf 1.550Mb application/pdf View/Open
Back to standard record
Partner of
EuDML logo