A Geometric Characterization of the Power of Finite Adaptability in Multistage Stochastic and Adaptive Optimization
A Geometric Characterization of the Power of Finite Adaptability in Multistage Stochastic and Adaptive Optimization
复制标题
多级随机和自适应优化中有限适应性能力的几何表征
DOI：
10.1287/moor.1110.0482
复制
发表时间：
2011
期刊：
影响因子：
--
通讯作者：
X. Sun
中科院分区：
文献类型：
--
作者：
D. Bertsimas;Vineet Goyal;X. Sun
在本文中，我们展示了一个显着的作用，几何性质的不确定性集，如对称性，在确定的权力，强大的和自适应的解决方案，在多级随机和自适应优化问题。我们考虑一类相当普遍的多级混合整数随机和自适应优化问题，并提出了一个很好的近似解决方案的政策，性能保证，取决于几何性质的不确定性集。特别是，我们证明了一类非适应性的解决方案是一个很好的逼近的多级随机和自适应优化问题。一个可自适应的解决方案概括了静态鲁棒解决方案的概念，并为每个阶段指定了一个小的解决方案集;解决方案策略根据过去阶段中不确定参数的实现，从给定的集合中实现最佳解决方案。因此，这是一个易于处理的近似的多阶段问题的完全适应性的解决方案。据我们所知，这些是多级问题的第一近似结果，在这样的一般性。此外，结果和证明技术是相当普遍的，也扩展到包括重要的约束，如完整性和线性圆锥约束。
In this paper, we show a significant role that geometric properties of uncertainty sets, such as symmetry, play in determining the power of robust and finitely adaptable solutions in multistage stochastic and adaptive optimization problems. We consider a fairly general class of multistage mixed integer stochastic and adaptive optimization problems and propose a good approximate solution policy with performance guarantees that depend on the geometric properties of the uncertainty sets. In particular, we show that a class of finitely adaptable solutions is a good approximation for both the multistage stochastic and the adaptive optimization problem. A finitely adaptable solution generalizes the notion of a static robust solution and specifies a small set of solutions for each stage; the solution policy implements the best solution from the given set, depending on the realization of the uncertain parameters in past stages. Therefore, it is a tractable approximation to a fully adaptable solution for the multistage problems. To the best of our knowledge, these are the first approximation results for the multistage problem in such generality. Moreover, the results and the proof techniques are quite general and also extend to include important constraints such as integrality and linear conic constraints.