Optimization Online


Inexact Bundle Methods for Two-Stage Stochastic Programming

Welington Oliveira (wlo***at***cos.ufrj.br)
Claudia Sagastizábal (sagastiz***at***impa.br)
Susana Scheimberg (susana***at***cos.ufrj.br)

Abstract: Stochastic programming problems arise in many practical situations. In general, the deterministic equivalents of these problems can be very large and may not be solvable directly by general-purpose optimization approaches. For the particular case of two-stage stochastic programs, we consider decomposition approaches akin to a regularized L-shaped method that can handle inexactness in the subproblem solution. From a nonsmooth optimization perspective, these variants amount to applying a proximal bundle method to an oracle that gives inaccurate values for the objective function and a subgradient. Rather than forcing early termination of the subproblems optimization to define inexact oracles, we select a small subset of scenarios for which the subproblem solution is exact, and replace the information for the remaining scenarios by a fast procedure that does not involve solving an optimization problem. The inaccurate oracle information creates inexact cuts in the master program, that are well handled by the recently introduced inexact bundle methods. The proposed approaches are validated by encouraging numerical results on several two-stage stochastic linear programs found in the literature.

Keywords: two-stage stochastic linear programs, bundle methods, inexact cuts.

Category 1: Stochastic Programming

Category 2: Nonlinear Optimization

Citation: Online version is available at the link: http://epubs.siam.org/siopt/resource/1/sjope8/v21/i2/p517_s1


Entry Submitted: 09/10/2010
Entry Accepted: 09/10/2010
Entry Last Modified: 04/02/2012

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 Optimization Society