On the Sparsity of Optimal Linear Decision Rules for a Class of Robust Optimization Problems with Box Uncertainty Sets
Lu和Sturt证明，在一类鲁棒库存管理问题中，总存在一个最优线性决策规则，其非零参数数量随时间周期数线性增长，并据此开发了比现有线性规划求解器快32倍的新算法。
One of the major reasons for the popularity of robust optimization is that these problems are often amenable to efficient approximations in operational planning problems where decisions must be made over time under uncertainty. The most common approximation is based on restricting the control policies to “linear decision rules”, that is, linear functions of the information revealed up in the past. In the paper “On the Sparsity of Optimal Linear Decision Rules for a Class of Robust Optimization Problems with Box Uncertainty Sets,” Lu and Sturt prove for a class of robust inventory management problems that there always exists an optimal linear decision rule in which the number of nonzero parameters in the linear decision rule grows linearly in the number of time periods. This is the first result to prove that optimal linear decision rules are sparse in a widely studied class of robust optimization problems with many time periods. Harnessing this sparsity guarantee, the authors develop a novel reformulation technique and active set algorithm for computing optimal linear decision rules that yield a 32× speedup over state-of-the-art linear programming solvers in numerical experiments on production–inventory problems with hundreds of time periods.