Authors: Antonio Frangioni Enrico Gorgone
Publish Date: 2013/02/12
Volume: 145, Issue: 1-2, Pages: 133-161
Abstract
We propose a version of the bundle scheme for convex nondifferentiable optimization suitable for the case of a sumfunction where some of the components are “easy” that is they are Lagrangian functions of explicitly known compact convex programs This corresponds to a stabilized partial Dantzig–Wolfe decomposition where suitably modified representations of the “easy” convex subproblems are inserted in the master problem as an alternative to iteratively innerapproximating them by extreme points thus providing the algorithm with exact information about a part of the dual objective function The resulting master problems are potentially larger and less wellstructured than the standard ones ruling out the available specialized techniques and requiring the use of generalpurpose solvers for their solution this strongly favors piecewiselinear stabilizing terms as opposed to the more usual quadratic ones which in turn may have an adverse effect on the convergence speed of the algorithm so that the overall performance may depend on appropriate tuning of all these aspects Yet very good computational results are obtained in at least one relevant application the computation of tight lower bounds for FixedCharge Multicommodity MinCost Flow problemsWe are grateful to the anonymous Referees and to the Editor for their insightful comments The first author gratefully acknowledges financial support of the Italian Ministry of Education University and Research MIUR under grant PRIN 2009XN4ZRR The second author thanks the financial support of European Commission through the European Social Fund and of the Regione Calabria under grant POR Calabria FSE 2007/2013
Keywords: