Solving Stochastic Programming Problems by Operator Splitting. Jonathan Eckstein, Rutgers Business School.

Solving Stochastic Programming Problems

by Operator Splitting
A B S T R A C T

This talk describes the solution of convex optimization problems that include uncertainty modeled by a finite but potentially very large multi-stage scenario tree. In 1991, Rockafellar and Wets proposed the progressive hedging (PH) algorithm to solve such problems. This method has some advantages over other standard methods such as Benders decomposition, especially for problems with large numbers of decision stages. The talk will open by showing that PH is an application of the Alternating Direction Method of Multipliers (ADMM). The equivalence of PH to the ADMM has long been known but not explicitly published. The ADMM is an example of “operator splitting” method, and in particular of a principle called “Douglas-Rachford splitting”. I will briefly explain what is meant by an “operator splitting method”. Next, the talk will apply a different, more recent operator splitting method called “projective splitting” to the same problem. The resulting method is called “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 up to 2,400 processor cores to solve 2-stage and 4-stage test problem instances with as many as 1,000,000 scenarios. Portions of the work described in this talk are joint with Patrick Combettes (North Carolina State University), Jean-Paul Watson (Lawrence Livermore National Laboratory, USA), and David Woodruff (University of California, Davis).

B I O G R A P H Y

Jonathan Eckstein is a Professor in the department of Management Science and Information Systems at Rutgers University. His principle research interestsare in numerical optimization algorithms, both continuous and discrete, and especially their implementation on parallel computing platforms. Areas of particular focus include augmented Lagrangian/proximal methods (including the ADMM and related splitting methods) and branch-and-bound algorithms. He has also worked on stochastic programming, risk-averse optimization modeling, and on applying O.R. techniques to managing information systems. He completed his Ph.D. in Operations Research at M.I.T. in 1989, and then taught at Harvard Business School for two years. He then spent four years in the Mathematical Sciences Research Group of Thinking Machines, Inc. (a pioneer of highly parallel computing systems) before joining Rutgers. At Rutgers, he led an effort establishing a new undergraduate major in Business Analytics and Information Technology (“BAIT”). In 2014, he was elected a fellow of INFORMS (the Institute for Operations Research and Management Science). In 2019, he became editor-in-chief of the journal Mathematical Programming Computation.