Value function gradient learning for large-scale multistage stochastic programming problems

DOI10.1016/J.EJOR.2022.10.011MaRDI QIDQ6167416zbMATH OpenOpenAlexFDO

Authors Jinkyu Lee, Woo Chang Kim, Yongjae Lee

Publication date 10 July 2023

Published in European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2205.08934

zbMATH Keywords

decision processeslarge-scale optimizationmultistage stochastic programmingstagewise decompositionvalue function approximation

Mathematics Subject Classification ID

Operations research and management science (90Bxx)

Abstract: A stagewise decomposition algorithm called value function gradient learning (VFGL) is proposed for large-scale multistage stochastic convex programs. VFGL finds the parameter values that best fit the gradient of the value function within a given parametric family. Widely used decomposition algorithms for multistage stochastic programming, such as stochastic dual dynamic programming (SDDP), approximate the value function by adding linear subgradient cuts at each iteration. Although this approach has been successful for linear problems, nonlinear problems may suffer from the increasing size of each subproblem as the iteration proceeds. On the other hand, VFGL has a fixed number of parameters; thus, the size of the subproblems remains constant throughout the iteration. Furthermore, VFGL can learn the parameters by means of stochastic gradient descent, which means that it can be easily parallelized and does not require a scenario tree approximation of the underlying uncertainties. VFGL was compared with a deterministic equivalent formulation of the multistage stochastic programming problem and SDDP approaches for three illustrative examples: production planning, hydrothermal generation, and the lifetime financial planning problem. Numerical examples show that VFGL generates high-quality solutions and is computationally efficient.

Cites work

• A heuristic for moment-matching scenario generation
• A moment-matching method to generate arbitrage-free scenarios
• A note on upper Lipschitz stability, error bounds, and critical multipliers for Lipschitz-continuous KKT systems
• A Stochastic Approximation Method
• A unified framework for stochastic optimization
• An algorithm for moment-matching scenario generation with application to financial portfolio optimisation
• Analysis of stochastic dual dynamic programming method
• Convergence analysis of sampling-based decomposition methods for risk-averse multistage stochastic convex programs
• Convergent cutting-plane and partial-sampling algorithm for multistage stochastic linear programs with recourse
• CVXPY: a Python-embedded modeling language for convex optimization
• Dual decomposition in stochastic integer programming
• Dynamic version of the economic lot size model
• Efficiency of Multivariate Control Variates in Monte Carlo Simulation
• scientific article; zbMATH DE number 3119649 (Why is no real title available?)
• scientific article; zbMATH DE number 3067835 (Why is no real title available?)
• Importance sampling in the Monte Carlo study of sequential tests
• Karush-Kuhn-Tucker systems: regularity conditions, error bounds and a class of Newton-type methods
• Lectures on Stochastic Programming
• Multi-stage stochastic optimization applied to energy planning
• Multistage stochastic programming model for electric power capacity expansion problem
• On the convergence of decomposition methods for multistage stochastic convex programs
• On the convergence of stochastic dual dynamic programming and related methods
• Progressive hedging innovations for a class of stochastic mixed-integer resource allocation problems
• Sampling-based decomposition methods for multistage stochastic programs based on extended polyhedral risk measures
• Scenario tree generation for multiperiod financial optimization of optimal discretization
• Scenario tree modeling for multistage stochastic programs
• Scenarios and Policy Aggregation in Optimization Under Uncertainty
• SDDP for some interstage dependent risk-averse problems and application to hydro-thermal planning
• Short-term hydropower production planning by stochastic programming
• Simulation and optimization approaches to scenario tree generation
• The voice of optimization

Cited in

(1)

• Large-scale financial planning via a partially observable stochastic dual dynamic programming framework

This page was built for publication: Value function gradient learning for large-scale multistage stochastic programming problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6167416)