Incremental-like Bundle Methods with Application to Energy Planning

Grégory Emiel (gemielimpa.br)
Claudia Sagastizábal (sagastizimpa.br)

Abstract: An important field of application of non-smooth optimization refers to decomposition of large-scale or complex problems by Lagrangian duality. In this setting, the dual problem consists in maximizing a concave non-smooth function that is defined as the sum of sub-functions. The evaluation of each sub-function requires solving a specific optimization sub-problem, with specific computational complexity. Typically, some sub-functions are hard to evaluate, while others are practically straightforward. When applying a bundle method to maximize this type of dual functions, the computational burden of solving sub-problems is preponderant in the whole iterative process. We propose to take full advantage of such separable structure by making a dual bundle iteration after having evaluated only a subset of the dual sub-functions, instead of all of them. This type of incremental approach has already been applied for subgradient algorithms. In this work we use instead a specialized variant of bundle methods and show that such an approach is related to bundle methods with inexact linearizations. We analyze the convergence properties of two incremental-like bundle methods. We apply the incremental approach to a generation planning problem over an horizon of one to three years. This is a large scale stochastic program, unsolvable by a direct frontal approach. For a real-life application on the French power mix, we obtain encouraging numerical results, achieving a significant improvement in speed without losing accuracy.

Keywords: Non-smooth optimization, Generation planning, Incremental methods, Large scale stochastic programming

Category 1: Convex and Nonsmooth Optimization (Nonsmooth Optimization )

Category 2: Stochastic Programming

Category 3: Applications -- OR and Management Sciences (Production and Logistics )

Citation: Computational Optimization and Applications. This report corrects and expands Sections 5 and 6 in DOI 10.1007/s10589-009-9288-8.

Download: [PDF]

Entry Submitted: 11/18/2008
Entry Accepted: 11/18/2008
Entry Last Modified: 10/01/2009

Modify/Update this entry