Stochastic dynamic cutting plane for multistage stochastic convex programs

DOI10.1007/S10957-021-01842-XzbMATH Open1470.90059arXiv1912.11946OpenAlexW3137164884MaRDI QIDQ2032005FDOQ2032005

Authors: Vincent Guigues, Renato D. C. Monteiro 

Publication date: 15 June 2021

Published in: Journal of Optimization Theory and Applications (Search for Journal in Brave)

Abstract: We introduce StoDCuP (Stochastic Dynamic Cutting Plane), an extension of the Stochastic Dual Dynamic Programming (SDDP) algorithm to solve multistage stochastic convex optimization problems. At each iteration, the algorithm builds lower affine functions not only for the cost-to-go functions, as SDDP does, but also for some or all nonlinear cost and constraint functions. We show the almost sure convergence of StoDCuP. We also introduce an inexact variant of StoDCuP where all subproblems are solved approximately (with bounded errors) and show the almost sure convergence of this variant for vanishing errors.

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

Recommendations

• Inexact cuts in stochastic dual dynamic programming
• Inexact cuts in stochastic dual dynamic programming applied to multistage stochastic nondifferentiable problems
• Stochastic dual dynamic programming for multistage stochastic mixed-integer nonlinear optimization
• Stochastic Lipschitz dynamic programming
• Stochastic dual dynamic integer programming

zbMATH Keywords

stochastic programmingSDDPinexact cuts for value functionsinexact SDDP

Mathematics Subject Classification ID

Convex programming (90C25) Stochastic programming (90C15)

Cites Work

• Partitioning procedures for solving mixed-variables programming problems
• An aggregate subgradient method for nonsmooth convex minimization
• Title not available (Why is that?)
• Title not available (Why is that?)
• Proximity control in bundle methods for convex nondifferentiable minimization
• On the convergence of stochastic dual dynamic programming and related methods
• Multi-stage stochastic optimization applied to energy planning
• New variants of bundle methods
• Sampling-based decomposition methods for multistage stochastic programs based on extended polyhedral risk measures
• Approximate dynamic programming. Solving the curses of dimensionality
• The Cutting-Plane Method for Solving Convex Programs
• Lectures on Stochastic Programming
• Dynamic sampling algorithms for multi-stage stochastic programs with risk aversion
• L-Shaped Linear Programs with Applications to Optimal Control and Stochastic Programming
• Handbook of semidefinite programming. Theory, algorithms, and applications
• Analysis of stochastic dual dynamic programming method
• Optimization of Convex Risk Functions
• SDDP for multistage stochastic linear programs based on spectral risk measures
• Convergence analysis of sampling-based decomposition methods for risk-averse multistage stochastic convex programs
• Decomposition and Partitioning Methods for Multistage Stochastic Linear Programs
• On the convergence of decomposition methods for multistage stochastic convex programs
• Conditional Risk Mappings
• Title not available (Why is that?)
• Improving the performance of stochastic dual dynamic programming
• Evaluating policies in risk-averse multi-stage stochastic programming
• Dual dynamic programming with cut selection: convergence proof and numerical experiments
• Inexact cuts in stochastic dual dynamic programming
• Regularized stochastic dual dynamic programming for convex nonlinear optimization problems
• Periodical multistage stochastic programs

Cited In (13)

• Exact converging bounds for stochastic dual dynamic programming via Fenchel duality
• Stochastic Lipschitz dynamic programming
• Inexact cuts in stochastic dual dynamic programming
• Complexity of stochastic dual dynamic programming
• Dynamic stochastic approximation for multi-stage stochastic optimization
• Stochastic dual dynamic integer programming
• Regularized stochastic dual dynamic programming for convex nonlinear optimization problems
• Stochastic dual dynamic programming for multistage stochastic mixed-integer nonlinear optimization
• StoDCuP
• Title not available (Why is that?)
• Inexact cuts in stochastic dual dynamic programming applied to multistage stochastic nondifferentiable problems
• Analysis of Sparse Cutting Planes for Sparse MILPs with Applications to Stochastic MILPs
• Inexact stochastic mirror descent for two-stage nonlinear stochastic programs

Uses Software

• Mosek
• MSPPy

This page was built for publication: Stochastic dynamic cutting plane for multistage stochastic convex programs

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