pith. sign in

arxiv: 2506.07314 · v2 · pith:YKQZ5EMGnew · submitted 2025-06-08 · 🧮 math.OC

Stochastic Quadratic Dynamic Programming

Vincent Guigues , Adriana Washington This is my paper

Pith reviewed 2026-05-22 00:20 UTC · model grok-4.3

classification 🧮 math.OC
keywords stochastic optimizationdynamic programmingquadratic cutsstrong convexitymultistage problemsconvergence analysiscutting-plane methods
0
0 comments X

The pith

Replacing affine cuts with quadratic cuts yields a convergent and faster algorithm for multistage stochastic optimization when recourse functions are strongly convex.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper presents SQDP as an extension of classical stochastic dual dynamic programming that substitutes quadratic cuts for affine ones to handle multistage problems whose recourse functions satisfy strong convexity. It supplies conditions that guarantee the recourse functions remain strongly convex and then proves that the resulting algorithm converges to an optimal solution. In the deterministic single-stage special case the method is called QCSC and its computational complexity is established. Numerical tests on both multistage and two-stage models show that SQDP runs substantially quicker than SDDP once the strong-convexity constant grows large, and that QCSC outperforms several standard solvers on deterministic strongly convex test problems.

Core claim

SQDP solves multistage stochastic optimization problems possessing strongly convex recourse functions by generating quadratic cuts rather than affine cuts inside a dynamic-programming decomposition; under explicit conditions that ensure strong convexity the algorithm converges, and the single-stage deterministic specialization QCSC possesses a proven complexity bound while delivering faster run times than competing methods on strongly convex instances.

What carries the argument

Quadratic cuts that locally approximate the strongly convex recourse functions inside the forward and backward passes of the dynamic programming recursion.

If this is right

  • Convergence holds for any multistage stochastic problem whose recourse functions meet the stated strong-convexity conditions.
  • Runtime advantage over SDDP grows with the magnitude of the strong-convexity constant.
  • QCSC gives a provably efficient alternative for single-stage strongly convex deterministic programs.
  • The same quadratic-cut replacement can be inserted into other cutting-plane schemes that already assume strong convexity.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Similar quadratic-cut accelerations may transfer to decomposition methods outside dynamic programming whenever strong convexity is already present.
  • Applications that naturally produce large convexity constants, such as certain energy or inventory models, become practical targets for the approach.
  • If the convexity constant can be estimated cheaply, an adaptive switch between affine and quadratic cuts could be designed without changing the convergence theory.

Load-bearing premise

The recourse functions must be strongly convex with a constant large enough that quadratic cuts remain valid and strictly improving approximations.

What would settle it

Run SQDP on a multistage instance whose recourse functions are known to be strongly convex with a large constant and observe that the algorithm either diverges or fails to produce faster run times than SDDP.

Figures

Figures reproduced from arXiv: 2506.07314 by Adriana Washington, Vincent Guigues.

Figure 1
Figure 1. Figure 1: Two iterations of QCSC. 2.2 A reformulation of QCSC In this section, we provide a reformulation of QCSC in terms of affine (instead of quadratic in the original QCSC formulation) cuts plus a quadratic term (µ/2)∥ · ∥2 independent on the trial points. We first write the original problem (1) under the form min x∈Rn ˜f(x) + h˜(x) (4) where h˜(x) = δX(x) is the indicator function of set X. We then define funct… view at source ↗
read the original 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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The manuscript introduces the SQDP algorithm as an extension of SDDP for multistage stochastic optimization problems whose recourse functions are strongly convex. It supplies conditions guaranteeing strong convexity of the recourse functions, proves convergence of SQDP, and, in the deterministic single-stage case, defines the QCSC method and establishes its complexity. Numerical experiments compare SQDP with SDDP on multistage and two-stage assembly problems and compare QCSC with standard solvers on six deterministic strongly convex test problems, reporting faster run times for large strong-convexity constants.

Significance. If the convergence result is valid under the stated conditions, the work provides a theoretically grounded way to replace linear cuts with quadratic cuts in SDDP-type algorithms, potentially yielding substantial speed-ups when the strong-convexity modulus is large. The complexity analysis for QCSC supplies a concrete theoretical contribution for the deterministic case. The numerical evidence of improved performance is consistent with the claimed benefit but remains illustrative rather than exhaustive.

major comments (2)
  1. [§3] §3 (convergence theorem for SQDP): the proof that quadratic cuts remain valid lower bounds and tighten monotonically relies on the recourse functions being strongly convex with a modulus that is uniform across stages and realizations. Because the stage-t recourse function is itself an expectation over later stages, it is not shown that the supplied conditions on the terminal stage or on the transition kernels automatically propagate a uniform modulus to earlier stages; without this, the quadratic cuts added to the master problem at stage t-1 may cease to be valid or improving.
  2. [§4] §4 (QCSC complexity result): the complexity bound is derived for a single-stage deterministic problem whose master problem remains a convex quadratic program. The manuscript does not address whether the same bound, or even convexity of the master problems, continues to hold once quadratic cuts generated from multiple stages are present in the multistage SQDP setting.
minor comments (2)
  1. Notation for the strong-convexity modulus should be introduced once and used consistently; currently the same symbol appears to be reused for both the terminal-stage constant and the induced constants at earlier stages.
  2. In the numerical section, the tables reporting CPU times versus strong-convexity constant would benefit from an additional column showing the number of iterations or cuts added, to make the source of the observed speed-up transparent.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and constructive comments. We address each major comment below and indicate the revisions that will be incorporated.

read point-by-point responses

  1. Referee: [§3] §3 (convergence theorem for SQDP): the proof that quadratic cuts remain valid lower bounds and tighten monotonically relies on the recourse functions being strongly convex with a modulus that is uniform across stages and realizations. Because the stage-t recourse function is itself an expectation over later stages, it is not shown that the supplied conditions on the terminal stage or on the transition kernels automatically propagate a uniform modulus to earlier stages; without this, the quadratic cuts added to the master problem at stage t-1 may cease to be valid or improving.

    Authors: We thank the referee for this observation. The manuscript supplies conditions ensuring strong convexity of the recourse functions, but we agree that an explicit argument showing propagation of a uniform modulus through the expectation operator is needed to fully justify validity of the quadratic cuts at every stage. In the revised version we will insert a supporting lemma in Section 3 that proves the given terminal-stage and kernel conditions imply a uniform strong-convexity modulus for all recourse functions. This lemma will directly confirm that the quadratic cuts remain valid lower bounds and tighten monotonically, thereby closing the gap in the convergence argument. revision: yes

  2. Referee: [§4] §4 (QCSC complexity result): the complexity bound is derived for a single-stage deterministic problem whose master problem remains a convex quadratic program. The manuscript does not address whether the same bound, or even convexity of the master problems, continues to hold once quadratic cuts generated from multiple stages are present in the multistage SQDP setting.

    Authors: The complexity analysis is stated only for the single-stage deterministic QCSC method; the multistage SQDP result is a convergence theorem, not a complexity bound. Each master problem in SQDP remains a convex quadratic program because every quadratic cut is a valid lower approximation to a strongly convex recourse function and therefore preserves convexity. We will add a short clarifying remark in Section 4 that explicitly delineates the scope of the complexity result and notes the convexity preservation property for the multistage case. revision: partial

Circularity Check

0 steps flagged

No circularity: convergence follows from explicit conditions and independent proof

full rationale

The paper states conditions ensuring strong convexity of recourse functions and then proves convergence of SQDP (and complexity of QCSC in the deterministic case). This structure is a standard mathematical derivation resting on stated assumptions and a proof, not on any self-definitional loop, fitted parameter renamed as prediction, or load-bearing self-citation. The multistage extension is justified by the same convexity conditions applied recursively; no equation reduces to its own input by construction. The numerical experiments are presented as illustration, not as the source of the claimed convergence.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claims rest on the domain assumption that recourse functions are strongly convex and on standard results from convex analysis and stochastic programming; no free parameters or invented entities are introduced in the abstract.

axioms (1)
  • domain assumption Recourse functions are strongly convex
    Invoked to justify quadratic cuts and to obtain the stated convergence and speed-up.

pith-pipeline@v0.9.0 · 5667 in / 1202 out tokens · 39169 ms · 2026-05-22T00:20:47.607711+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

25 extracted references · 25 canonical work pages

  1. [1]

    J.R. Birge. Decomposition and partitioning methods for multistage stochastic linear programs. Oper. Res., 33:989–1007, 1985

    work page 1985

  2. [2]

    Birge and C

    J.R. Birge and C. J. Donohue. The Abridged Nested Decomposition Method for Multistage Stochastic Linear Programs with Relatively Complete Recourse. Algorithmic of Operations Research, 1:20–30, 2001

    work page 2001

  3. [3]

    Chen and W.B

    Z.L. Chen and W.B. Powell. Convergent Cutting-Plane and Partial-Sampling Algorithm for Multistage Stochastic Linear Programs with Recourse. J. Optim. Theory Appl. , 102:497–524, 1999

    work page 1999

  4. [4]

    Girardeau, V

    P. Girardeau, V. Leclere, and A.B. Philpott. On the convergence of decomposition methods for multistage stochastic convex programs. Mathematics of Operations Research, 40:130–145, 2015

    work page 2015

  5. [5]

    V. Guigues. SDDP for some interstage dependent risk-averse problems and application to hydro-thermal planning. Computational Optimization and Applications , 57:167–203, 2014

    work page 2014

  6. [6]

    V. Guigues. Convergence analysis of sampling-based decomposition methods for risk-averse multistage stochastic convex programs. SIAM Journal on Optimization , 26:2468–2494, 2016

    work page 2016

  7. [7]

    V. Guigues. Inexact cuts in Stochastic Dual Dynamic Programming. Siam Journal on Opti- mization, 30:407–438, 2020

    work page 2020

  8. [8]

    V. Guigues. Inexact cuts in SDDP applied to multistage stochastic nondifferentiable problems. Siam Journal on Optimization , 31:2084–2110, 2021

    work page 2084

  9. [9]

    V. Guigues. Multistage stochastic programs with a random number of stages: dynamic pro- gramming equations, solution methods, and application to portfolio selection. Optimization Methods & Software, 36:211–236, 2021

    work page 2021

  10. [10]

    Guigues and W

    V. Guigues and W. R¨ omisch. Sampling-based decomposition methods for multistage stochastic programs based on extended polyhedral risk measures. SIAM J. Optim. , 22:286–312, 2012

    work page 2012

  11. [11]

    Guigues and W

    V. Guigues and W. R¨ omisch. SDDP for multistage stochastic linear programs based on spectral risk measures. Operations Research Letters, 40:313–318, 2012. 22

    work page 2012

  12. [12]

    Guigues, A

    V. Guigues, A. Shapiro, and Y. Cheng. Risk-Averse Stochastic Optimal Control: an efficiently computable statistical upper bound. Operations Research Letters, 51:393–400, 2023

    work page 2023

  13. [13]

    Guigues, W

    V. Guigues, W. Tekaya, and M. Lejeune. Regularized stochastic dual dynamic programming for convex nonlinear optimization problems. Optimization and Engineering , 21:1133–1165, 2020

    work page 2020

  14. [14]

    Hindsberger and A

    M. Hindsberger and A. B. Philpott. Resa: A method for solving multi-stage stochastic linear programs. SPIX Stochastic Programming Symposium, 2001

    work page 2001

  15. [15]

    The cutting-plane method for solving convex programs

    Kelley J.E. The cutting-plane method for solving convex programs. Journal of the Society for Industrial and Applied Mathematics , 8(4):703–712, 1960

    work page 1960

  16. [16]

    Kozmik and D.P

    V. Kozmik and D.P. Morton. Evaluating policies in risk-averse multi-stage stochastic pro- gramming. Mathematical Programming, 152:275–300, 2015

    work page 2015

  17. [17]

    Liang and R

    J. Liang and R. Monteiro. A unified analysis of a class of proximal bundle methods for solving hybrid convex composite optimization problems. Mathematics of Operations Research, 49:832–855, 2023

    work page 2023

  18. [18]

    Liang and R

    J. Liang and R. D. C. Monteiro. A unified analysis of a class of proximal bundle methods for solving hybrid convex composite optimization problems. Mathematics of Operations Research, 49(2):832–855, 2024

    work page 2024

  19. [19]

    Pereira and L.M.V.G Pinto

    M.V.F. Pereira and L.M.V.G Pinto. Multi-stage stochastic optimization applied to energy planning. Math. Program., 52:359–375, 1991

    work page 1991

  20. [20]

    Philpott and V

    A. Philpott and V. de Matos. Dynamic sampling algorithms for multi-stage stochastic programs with risk aversion. European Journal of Operational Research, 218:470–483, 2012

    work page 2012

  21. [21]

    A. B. Philpott and Z. Guan. On the convergence of stochastic dual dynamic programming and related methods. Oper. Res. Lett., 36:450–455, 2008

    work page 2008

  22. [22]

    R. Schultz. Strong convexity in stochastic programs with complete recourse. Journal of Computational and Applied Mathematics , 56:3–22, 1994

    work page 1994

  23. [23]

    A. Shapiro. Analysis of stochastic dual dynamic programming method. European Journal of Operational Research, 209:63–72, 2011

    work page 2011

  24. [24]

    Shapiro, D

    A. Shapiro, D. Dentcheva, and A. Ruszczy´ nski.Lectures on Stochastic Programming: Modeling and Theory. SIAM, Philadelphia, 2009

    work page 2009

  25. [25]

    Y. Cheng V. Guigues, A. Shapiro. Duality and sensitivity analysis of multistage linear stochas- tic programs. European journal of Operational Research, 308(2):752–767, 2023. 23

    work page 2023