text: We present a data-driven framework for incorporating side information in dynamic optimization under uncertainty. Specifically, our approach uses predictive machine learning methods (such as k-nearest neighbors, kernel regression, and random forests) to weight the relative importance of various data-driven uncertainty sets in a robust optimization formulation. Through a novel measure concentration result for local machine learning methods, we prove that the proposed framework is asymptotically optimal for stochastic dynamic optimization with covariates. We also describe a general-purpose approximation for the proposed framework, based on overlapping linear decision rules, which is computationally tractable and produces high-quality solutions for dynamic problems with many stages. Across a variety of examples in shipment planning, inventory management, and finance, our method achieves improvements of up to 15 over alternatives and requires less than one minute of computation time on problems with twelve stages.
  @cite_13: We investigate a data-driven approach to two-stage stochastic linear optimization in which an uncertainty set is constructed around each data point. We propose an approximation algorithm for these sample robust optimization problems by optimizing a separate linear decision rule for each uncertainty set. We show that the proposed algorithm combines the asymptotic optimality and scalability of the sample average approximation while simultaneously offering improved out-of-sample performance guarantees. The practical value of our method is demonstrated in network inventory management and hospital scheduling.
  @cite_1: Stochastic programming provides a versatile framework for decision-making under uncertainty, but the resulting optimization problems can be computationally demanding. It has recently been shown that primal and dual linear decision rule approximations can yield tractable upper and lower bounds on the optimal value of a stochastic program. Unfortunately, linear decision rules often provide crude approximations that result in loose bounds. To address this problem, we propose a lifting technique that maps a given stochastic program to an equivalent problem on a higher-dimensional probability space. We prove that solving the lifted problem in primal and dual linear decision rules provides tighter bounds than those obtained from applying linear decision rules to the original problem. We also show that there is a one-to-one correspondence between linear decision rules in the lifted problem and families of nonlinear decision rules in the original problem. Finally, we identify structured liftings that give rise to highly flexible piecewise linear and nonlinear decision rules, and we assess their performance in the context of a dynamic production planning problem.
summary: Several recent papers have focused on tractable approximations of two- and multi-stage and robust optimization. Many approaches are based around policy approximation schemes, including lifted linear decision rules , @math -adaptivity , and finite adaptability . Alternative approaches include tractable approximations of copositive formulations . Closest related to the approximation scheme in this paper are @cite_1 and @cite_13 , which address two-stage problems via overlapping decision rules. @cite_1 propose a modeling approach that leads to novel approximations of various distributionally robust applications, including two-stage distributionally robust optimization using Wasserstein ambiguity sets and expectations of piecewise convex objective functions in single-stage problems. Independently, @cite_13 investigate a of two-stage sample robust optimization by optimizing a separate linear decision rule for each uncertainty set and prove that this approximation gap converges to zero as the amount of data goes to infinity. In of this paper, we show how to extend similar techniques to dynamic problems with many stages for the first time.