Inexact Bundle Methods for Two-Stage Stochastic Programming
Welington Oliveira (wlocos.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
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|