یک رویکرد رگرسیون کارآمد برای حل مشکلات دوگانه برنامه های پویا *

In recent years, information relaxation and duality in dynamic programs have been studied extensively, and the resulted primal-dual approach has become a powerful procedure in solving dynamic programs by providing lower-upper bounds on the optimal value function. Theoretically, with the so called value-based optimal dual penalty, the optimal value function could be recovered exactly via strong duality; however, in practice, generating tight dual bounds usually requires good approximations of the optimal dual penalty, which could be time-consuming due to the conditional expectation terms that need to be estimated via nested simulation. In this paper, we will develop an efficient regression approach to approximating the optimal dual penalty in a non-nested manner, by exploring the structure of the feasible dual penalty space. The resulted approximation maintains to be a dual feasible penalty, leading to a valid dual bound on the optimal value function. We show that the proposed approach is computationally efficient, and the resulted dual penalty leads to a numerically tractable dual problem.