Optimization Online


Incremental-like Bundle Methods with Application to Energy Planning

Grégory Emiel (gemiel***at***impa.br)
Claudia Sagastizábal (sagastiz***at***impa.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

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society