Title: Stochastic Programming, Progressive Hedging, and Projective Splitting Methods

Speaker: Jonathan Eckstein, MSIS Department and RUTCOR, Rutgers University (on sabbatical at ORFE Department, Princeton University)

Date/Time: Thursday, June 5, 2008 at 10:00am (previously scheduled at 9am)

Location: CSRI Building, Room 90 (Sandia NM)

Brief Abstract: This talk has two main parts: a tutorial and a description of some recent research results.
The tutorial uses a simple stochastic programming problem to motivate investigation of splitting algorithms for monotone set-valued operators. In particular, we see that Rockafellar and Wets’ well-known progressive hedging method is an application of a standard splitting algorithm.  The tutorial includes the fundamental concepts of monotone operators and splitting; I will assume no prior knowledge of these topics.

In the second section of the talk, I will present a new family of “projective” splitting algorithms for sums of n monotone operators.  The key idea is to formulate a certain “extended solution” set in a higher-dimensional space, decomposably construct separating hyperplanes between the current solution estimate and this set, and then project onto or through these hyperplanes.   In this way, we construct an unprecedentedly large and flexible family of splitting methods which can be shown to contain prior algorithms as special cases.  Some very rudimentary computational testing suggests that algorithms in the new class have the potential to converge much faster than prior standard splitting methods.

Finally, I will also briefly examine how projective splitting might apply to stochastic programming, producing a family of hedging algorithms more general than Rockafellar and Wets’ method.

Joint work with Benar F. Svaiter, IMPA, Rio de Janeiro, Brazil

CSRI POC: Jean-Paul Watson, 845-8887