Orateur
Description
We develop a new stopping rule for the stochastic dual dynamic programming (SDDP) algorithm based on sequential testing. Traditional stopping rules are based on statistical tests that assess whether the optimality gap in a given iteration is smaller than a pre-defined precision. However, repeated use of such single-iteration tests invalidates the overall validity of the stopping rule, because the probabilities of false positives (i.e., stopping too early) of the individual tests compound. To overcome this problem, we use ideas from sequential hypothesis testing to construct a statistically valid stopping rule. This stopping rule is based on a hypothesis test that uses joint information from multiple iterations of the algorithm. Besides ensuring statistical validity, another benefit of this approach is that it can exploit the fact that "weak evidence" for convergence in several subsequent iterations amounts to strong overall evidence for convergence.
