A new convergent hybrid learning algorithm for two-stage stochastic programs

Shaorui Zhou, Hui Zhang, Ning Shi, Zhou Xu, Fan Wang

Research output: Journal article publicationJournal articleAcademic researchpeer-review

1 Citation (Scopus)

Abstract

This study proposes a new hybrid learning algorithm to approximate the expected recourse function for two-stage stochastic programs. The proposed algorithm, which is called projected stochastic hybrid learning algorithm, is a hybrid of piecewise linear approximation and stochastic subgradient methods. Piecewise linear approximations are updated adaptively by using stochastic subgradient and sample information on the objective function itself. In order to achieve a global optimum, a projection step that implements the stochastic subgradient method is performed to jump out from a local optimum. For general two-stage stochastic programs, we prove the convergence of the algorithm. Furthermore, the algorithm can drop the projection steps for two-stage stochastic programs with network recourse. Therefore, the pure piecewise linear approximation method is convergent when the initial piecewise linear functions are properly constructed. Computational results indicate that the algorithm exhibits rapid convergence.

Original languageEnglish
Pages (from-to)33-46
Number of pages14
JournalEuropean Journal of Operational Research
Volume283
Issue number1
DOIs
Publication statusPublished - 16 May 2020

Keywords

  • Network
  • Optimization
  • Piecewise linear approximation
  • Stochastic programming

ASJC Scopus subject areas

  • Computer Science(all)
  • Modelling and Simulation
  • Management Science and Operations Research
  • Information Systems and Management

Cite this