Bundle-based decomposition for large-scale convex optimization: Error estimate and application to block-angular linear programs
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.
scientific article; zbMATH DE number 695778
scientific article