Stochastic Quadratic Dynamic Programming

2025/06/08 by Vincent Guigues, Guigues, Vincent, Adriana Washington +1
Computer Science · Decision Sciences · #FOS: Mathematics #Optimization and Control (math.OC) #Reinforcement Learning in Robotics #Risk and Portfolio Optimization #Stochastic Gradient Optimization Techniques

paper · pdf · doi:10.48550/arxiv.2506.07314

openalex publication_date 2025/06/08 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We introduce an algorithm called SQDP (Stochastic Quadratic Dynamic Programming) to solve some multistage stochastic optimization problems having strongly convex recourse functions. The algorithm extends the classical Stochastic Dual Dynamic Programming (SDDP) method replacing affine cuts by quadratic cuts. We provide conditions ensuring strong convexity of the recourse functions and prove the convergence of SQDP. In the special case of a single stage deterministic problem, we call QCSC (Quadratic Cuts for Strongly Convex optimization) the method and prove its complexity. Numerical experiments illustrate the performance and correctness of SQDP, with SQDP being much quicker than SDDP for large values of the constants of strong convexity both for a multistage problem and a two-stage assembly recourse model. We also present the results of numerical experiments on deterministic problems where QCSC is much quicker than several popular competing optimizers for solving 6 strongly convex optimization problems from the literature.

Citations

• Universal subgradient and proximal bundle methods for convex and strongly convex hybrid composite optimization
• Risk-Averse Stochastic Optimal Control: an efficiently computable statistical upper bound
• A unified analysis of a class of proximal bundle methods for solving hybrid convex composite optimization problems
• Inexact cuts in SDDP applied to multistage stochastic nondifferentiable problems
• Duality and sensitivity analysis of multistage linear stochastic programs
• Inexact cuts in Stochastic Dual Dynamic Programming
• Multistage stochastic programs with a random number of stages: dynamic\n programming equations, solution methods, and application to portfolio\n selection
• A Simple Nearly-Optimal Restart Scheme For Speeding-Up First Order\n Methods
• Regularized Stochastic Dual Dynamic Programming for convex nonlinear optimization problems
• Convergence analysis of sampling-based decomposition methods for\n risk-averse multistage stochastic convex programs

Related

• Bundle methods with quadratic cuts for deterministic and stochastic strongly convex optimization problems
• Stochastic Dynamic Cutting Plane for multistage stochastic convex\n programs
• A stochastic algorithm for deterministic multistage optimization problems
• Regularized Stochastic Dual Dynamic Programming for convex nonlinear optimization problems
• Inexact cuts in Stochastic Dual Dynamic Programming