Bundle-based decomposition for large-scale convex optimization: Error estimate and application to block-angular linear programs
type: Item
instance of: scholarly article
title: Bundle-based decomposition for large-scale convex optimization: Error estimate and application to block-angular linear programs
zbMATH Open document ID: 0830.90120
DOI: 10.1007/BF01581138
author: Deepankar Medhi
published in: Mathematical Programming. Series A. Series B
publication date: 1996-01-30T00:00:00Z
review text: The author studies the convex optimization problem \[ \text{(CP):}\qquad \text{Inf } \sum^N_{i= 1} f_i(x_i)\text{ s.t. } \sum^N_{i= 1} A_i x_i= a_i,\;x_i\geq 0\quad (i= 1,\dots, N), \] where each \(f_i\) is a closed proper convex function taking values in \((- \infty, \infty]\). The dual of (CP) is a nonsmooth concave problem which is solved using the bundle method proposed by \textit{C. Lemaréchal}, \textit{J. J. Strodiot} and \textit{A. Bihain} [Nonlinear programming 4, Proc. Symp., Madison/Wis. 1980, 245-282 (1981; Zbl 0533.49023)] from which an approximate primal feasible solution is easily determined. A posteriori error estimate on the approximate primal optimal solution and on the duality gap is given. A special class of (CP) namely a block-angular linear programming problem is studied and for this class the author claims the method to be promising on the basis of computational experience. The author states that the method is competitive with MINOS and an advanced implementation of the Dantzig- Wolfe decomposition method.
Mathematics Subject Classification ID: 90C25
Mathematics Subject Classification ID: 90C06
Mathematics Subject Classification ID: 90C05
zbMATH DE Number: 695778
zbMATH Keywords: convex optimization
zbMATH Keywords: nonsmooth concave problem
zbMATH Keywords: bundle method
zbMATH Keywords: error estimate
zbMATH Keywords: duality gap
reviewed by: R. N. Kaul
describes a project that uses: MINOS
describes a project that uses: IMSL Numerical Libraries
MaRDI profile type: Publication
cites work: Decomposition Principle for Linear Programs
cites work: Q3666564
cites work: Q4739659
cites work: Validation of subgradient optimization
cites work: An advanced implementation of the Dantzig—Wolfe decomposition algorithm for linear programming
cites work: Computational experience with advanced implementation of decomposition algorithms for linear programming
cites work: Computational aspects of DYNAMICO : a model of trade and development in the world economy
cites work: DECOMP: an implementation of Dantzig-Wolfe decomposition for linear programming
cites work: Q3316093
cites work: Parallel bundle-based decomposition for large-scale structured mathematical programming problems
cites work: A stable method for solving certain constrained least squares problems
cites work: Q3741418
cites work: Convex Analysis
cites work: Q4050397
cites work: Monotone Operators and the Proximal Point Algorithm
description: scientific article; zbMATH DE number 695778