On Lipschitz regularization and Lagrangian cuts in multistage stochastic mixed-integer linear programming

We provide new theoretical insight on the generation of linear and non-convex cuts for value functions of multistage stochastic mixed-integer programs based on Lagrangian duality. First, we analyze in detail the impact that the introduction of copy constraints, and especially, the choice of the accompanying constraint set for the copy variable have on the properties of the Lagrangian dual and the obtained cuts. We show that the well-known tightness result for Lagrangian cuts in stochastic dual dynamic programming (SDDiP) crucially depends on this choice, and not on the introduction of copy constraints in itself. Afterwards, we generalize our results to the case where a Lipschitz regularization is applied to the value functions. In particular, we show a deep relation between norm-bounded Lagrangian dual problems and the closed convex envelope of the regularized value functions. For linear Lagrangian cuts, using an appropriate regularization, this result can be used to enhance the tightness result from SDDiP to the regularized case. For the generation of non-convex cuts, we pick up on the lift-and-project idea proposed by Füllner and Rebennack in their non-convex nested Benders decomposition (NC-NBD) method. We generalize this cut generation idea to the stochastic case. We then show that by careful choice of the norm used for regularization in the lifted space, Lipschitz continuity of the obtained non-convex cuts can be guaranteed. By that, we resolve an open theoretical question from the original NC-NBD paper. We highlight all our results by simple illustrative examples. Our work allows for a profound understanding of how and to which effect copy constraints and regularization may be used in decomposition methods in stochastic mixed-integer programming.

Article

Download

View PDF