Abstract

Robinson has proposed the bundle-based decomposition algorithm to solve a class of structured large-scale convex optimization problems. In this method, the original problem is transformed (by dualization) to an unconstrained nonsmooth concave optimization problem which is in turn solved by using a modified bundle method. In this paper, we give {\it a posteriori\/} error estimates on the approximate primal optimal solution and on the duality gap. We describe implementation and present computational experience with a special case of this class of problems, namely, block-angular linear programming problems. We observe that the method is efficient in obtaining approximate optimal solution and compares favorably with MINOS and an advanced implementation of the Dantzig-Wolfe decomposition method.

Key words: Large-scale optimization, nonsmooth optimization, bundle method, decomposition, block-angular linear programming.

To obtain a post-script file of this paper, click here . This file is approx. 257K bytes.