Progressive Hedging and Asynchronous Projective Hedging for Convex Stochastic Programming

Abstract: Operator splitting methods for convex optimization and monotone inclusions have their roots in the solution of partial differential equations, and have since become popular in machine learning and image processing applications. Their application to "operations-research-style" optimization problems has been somewhat limited.

A notable exception is their application to stochastic programming. In a paper published in 1991, Rockafellar and Wets proposed the progressive hedging (PH) algorithm to solve large-scale convex stochastic programming problems. Although they proved the convergence of the method from first principles, it was already known to them that PH was an operator splitting method.

This talk will present a framework for convex stochastic programming and show that applying the ADMM (and thus Douglas-Rachford splitting) to it yields the PH algorithm. The equivalence of PH to ADMM has long been known but not explicitly published.

Next, the talk will apply the projective splitting framework of Combettes and Eckstein to the same formulation, yielding a method which is similar to PH but can be implemented in a partially aynchronous manner. We call this method "asynchronous projective hedging" (APH). Unlike most decomposition methods, it does not need to solve every subproblem at every iteration; instead, each iteration may solve just a single subproblem or a small subset of the available subproblems.

Finally, the talk will describe work integrating the APH algorithm into mpi-sppy, a Python package for modeling and distributed parallel solution of stochastic programming problems. Mpi-sppy uses the Pyomo Python-based optimization modeling sytem. Our experience includes using 8,000 processor cores to solve a test problem instance with 1,000,000 scenarios.

This talk presents joint research with Jean-Paul Watson (Lawrence Livermore National Laboratory, USA), and David Woodruff (University of California, Davis).

optimization and control

Audience: advanced learners

Comments: The address and password of the zoom room of the seminar are sent by e-mail on the mailinglist of the seminar one day before each talk

---

One World Optimization seminar

Series comments: Description: Online seminar on optimization and related areas

The address and password of the zoom room of the seminar are sent by e-mail on the mailinglist of the seminar one day before each talk

---