Solving convex program via Lagrangian decomposition
Kybernetika (2004)
- Volume: 40, Issue: 5, page [595]-610
- ISSN: 0023-5954
Access Full Article
top
Abstract
topHow to cite
topKnobloch, Matthias. "Solving convex program via Lagrangian decomposition." Kybernetika 40.5 (2004): [595]-610. <http://eudml.org/doc/33722>.
@article{Knobloch2004,
abstract = {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.},
author = {Knobloch, Matthias},
journal = {Kybernetika},
keywords = {level method; cutting-plane methods; decomposition methods; convex programming; nonsmooth programming; level method; cutting-plane method; decomposition method; nonsmooth programming},
language = {eng},
number = {5},
pages = {[595]-610},
publisher = {Institute of Information Theory and Automation AS CR},
title = {Solving convex program via Lagrangian decomposition},
url = {http://eudml.org/doc/33722},
volume = {40},
year = {2004},
}
TY - JOUR
AU - Knobloch, Matthias
TI - Solving convex program via Lagrangian decomposition
JO - Kybernetika
PY - 2004
PB - Institute of Information Theory and Automation AS CR
VL - 40
IS - 5
SP - [595]
EP - 610
AB - 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.
LA - eng
KW - level method; cutting-plane methods; decomposition methods; convex programming; nonsmooth programming; level method; cutting-plane method; decomposition method; nonsmooth programming
UR - http://eudml.org/doc/33722
ER -
References
top- Auslender A., 10.1007/PL00011377, Math. Programming 88 (2001), 45–59 Zbl0980.90063MR1765892DOI10.1007/PL00011377
- Beer K., Gol’stejn E. G., Sokolov N. A., 10.1080/0233193021000066446, Optimization 51 (2002), 6, 819–840 Zbl1036.65050MR1941716DOI10.1080/0233193021000066446
- 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
- 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
- Belousov E. G., Introduction to Convex Analysis and Integer Programming (in Russian), Izdatel’stvo Moskovskogo Universiteta, Moskau 1977 MR0475840
- 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 (1976) Zbl0322.90046MR1727362
- Goffin J. L., Vial J. P., 10.1080/1055678021000060829a, Optimization Methods and Software 17 (2002), 5, 805–867 Zbl1065.90060MR1953822DOI10.1080/1055678021000060829a
- Kiwiel K. C., Methods of Descent for Nondifferentiable Optimization, (Lecture Notes in Mathematics 1133), Springer Verlag, Heidelberg 1985 Zbl0561.90059MR0797754
- Kiwiel K. C., 10.1007/BF01585554, Math. Programming 69B (1995), 89–105 (1995) Zbl0857.90101MR1354433DOI10.1007/BF01585554
- Lémarechal C., Nemirovskii, A., Nesterov Y., 10.1007/BF01585555, Math. Programming 69 (1995), 111–147 (1995) MR1354434DOI10.1007/BF01585555
- Nožička F., Guddat J., Hollatz, H., Bank B., Theorie der linearen parametrischen Optimierung, Akademie Verlag, Berlin 1974 Zbl0284.90053
- Mifflin R., 10.1287/moor.2.2.191, Math. Oper. Res. 2 (1997), 2, 191–207 (1997) MR0474815DOI10.1287/moor.2.2.191
- Richter K., Lösungsverfahren für konvexe Optimierungsaufgaben mit Umrandungsstruktur auf der Grundlage gleichzeitiger primal-dualer Dekomposition, Dissertation, TU Chemnitz 2000 Zbl1130.90300MR1870565
- Shor N. Z., Minimization Methods for Non-differentiable Functions, Springer Verlag, Berlin 1985 Zbl0561.90058MR0775136
- Tuy H., Convex Analysis and Global Optimization, Kluwer, Dordrecht 1998 Zbl0904.90156MR1615096
- Unger T., Erweiterungen der Levelmethode zur Lösung konvexer Optimierungsaufgaben, Dissertation, Shaker Verlag, Aachen 2003
NotesEmbed ?
topYou must be logged in to post comments.
To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.