Bundle methods for sum-functions with easy components: applications to multicommodity network design

• 成果类型: Article
• 署名作者: Frangioni, Antonio; Gorgone, Enrico
• 署名单位: University of Pisa; University of Calabria
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-013-0642-3
• 发表日期: 2014
• 页码: 133-161
• 关键词: cutting plane method; cycle-based neighborhoods; cost flow problems; convex-optimization; subgradient methods; Column Generation; lagrangian-relaxation; unit commitment; algorithm; DECOMPOSITION

摘要

We propose a version of the bundle scheme for convex nondifferentiable optimization suitable for the case of a sum-function 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 inner-approximating 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 well-structured than the standard ones, ruling out the available specialized techniques and requiring the use of general-purpose solvers for their solution; this strongly favors piecewise-linear 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 Fixed-Charge Multicommodity Min-Cost Flow problems.