Stochastic Lipschitz Dynamic Programming
Date:
We propose the usage of non-convex approximations for the value functions in multistage stochastic mixed-integer optimization problems. A core idea is using non-convex building blocks to approximate the value functions, generalizing the classical SDDP algorithm that uses cuts and only builds convex approximations. We explore several possibilities for obtaining such approximations, including generalized augmented duality cuts and direct Lipschitz constant estimates. We also prove that the resulting algorithm, called Stochastic Lipschitz Dynamic Programming (SLDP), converges to epsilon-optimal solutions under very reasonable assumptions.
More details and paper