论文标题
关于一类框架不确定性集的一类强大优化问题的最佳线性决策规则的稀疏性
On the Sparsity of Optimal Linear Decision Rules for a Class of Robust Optimization Problems with Box Uncertainty Sets
论文作者
论文摘要
我们考虑了Ben-Tal等人的开创性工作中的一类生产问题的问题。 （2004年）对可靠优化的线性决策规则。我们证明，对于此类问题，始终存在最佳的线性决策规则，其中线性决策规则中的非零参数数量在时间段内线性增长。这是证明最佳线性决策规则在许多时间段内的一系列强大优化问题中稀疏的第一个结果。利用这种稀疏性保证，我们引入了一种重新制定技术，该技术允许强大的优化问题，例如生产涉及问题问题，即当线性决策规则的大多数参数被迫等于零时，可以将其作为紧凑的线性优化问题解决。我们还开发了一种活跃的集合方法，用于识别最优性时等于零的线性决策规则的参数。在数百个时间段的生产评估问题的数值实验中，我们发现我们的重新制定技术与主动设定方法相结合的计算线性决策规则中最先进的线性优化求解器的速度超过32倍，而最佳的1 \％\％oftimal of Optimal。我们的证明和算法基于对线性优化公式的极端分析的原则分析。
We consider a class of production-inventory problems with box uncertainty sets from the seminal work of Ben-Tal et al. (2004) on linear decision rules in robust optimization. We prove that there always exists an optimal linear decision rule for this class of problems 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, we introduce a reformulation technique that allows robust optimization problems such as production-inventory problems to be solved as a compact linear optimization problem when most of the parameters of the linear decision rules are forced to be equal to zero. We also develop an active set method for identifying the parameters of linear decision rules that are equal to zero at optimality. In numerical experiments on production-inventory problems with hundreds of time periods, we find that our reformulation technique coupled with the active set method yield more than a 32x speedup over state-of-the-art linear optimization solvers in computing linear decision rules that are within 1\% of optimal. Our proofs and algorithms are based on a principled analysis of extreme points of linear optimization formulations.
