Asynchronous Projective Hedging for Stochastic Programming

Jonathan Eckstein(jecksteibusiness.rutgers.edu)
Jean-Paul Watson(jwatsonsandia.gov)
David L. Woodruff(dlwoodruffucdavis.edu)

Abstract: This paper proposes a decomposition algorithm for multistage stochastic programming that resembles the progressive hedging method of Rockafellar and Wets, but is capable of asynchronous parallel operation without sacrificing theoretical convergence in the convex case. Perhaps more importantly, each iteration of the decomposition method may process only a subset of the possible scenarios. The method is an application of a class of projective monotone operator splitting methods recently proposed by Combettes and Eckstein. We give a derivation and convergence proof of the method in the case that the problem is convex and the feasible set is compact, subject to some standard regularity conditions. We close by comparing the resulting algorithm to progressive hedging on some standard stochastic linear programming test problems.

Keywords: Stochastic programming; decomposition; asynchronous; operator splitting

Category 1: Stochastic Programming

Category 2: Convex and Nonsmooth Optimization (Convex Optimization )

Citation:

Download: [PDF]

Entry Submitted: 10/30/2018
Entry Accepted: 10/30/2018
Entry Last Modified: 10/30/2018

Modify/Update this entry