Optimization in an Uncertain World: A Unified Framework for Optimization Models Involving Adversaries

该项目涉及决策过程的建模和优化，这些决策过程会随着时间的推移而分阶段展开。将时间阶段明确地纳入复杂系统的模型是一种解释现实世界系统重要特征的方法——存在敌对实体，其未来潜在的有害行为可能会破坏当前制定的计划。这种对手的形式可以是难以预测的随机过程（如天气或经济状况），也可以是积极寻求破坏系统运行的直接竞争对手。从计算的角度来看，对这样的对手进行计算是一项挑战，因为它涉及到对给定行动可能导致未来发展的所有方式的隐性知识。这项工作是通过开发技术来理解和减轻这种复杂性的影响，通过使用复杂的数学技术来紧凑地表示不确定性的影响，例如，人们可以智能地确定一小组“重要”场景，这些场景的考虑仍然允许确定当前的最佳决策，隐含地考虑了所有可能的未来场景。本课题将研究的一类优化问题是那些变量可以被划分为子集的问题，这些子集的值必须分阶段固定。后阶段的约束既取决于前阶段固定的变量值，也取决于某些随机变量的实现值。总体框架的一个关键特征是，每个阶段的变量可能由具有不同目标函数的不同决策者控制。本课程包括两个重要且具有挑战性的特殊案例-有追索权的多阶段随机规划和多层次规划。这两个类的特点是互补的，通过开发统一的方法可以获得很多好处。本研究的总体目标是为这些模型开发计算方法，特别关注存在离散变量的情况。

This project involves the modeling and optimization of decision processes that unfold in stages over time. The explicit incorporation of time stages into models of complex systems is one approach to accounting for an important feature of real-world systems---the presence of adversarial entities whose potentially detrimental actions in the future may disrupt plans being made in the present. Such adversaries' can take the form of either difficult-to-predict random processes (such as the weather or economic conditions) or direct competitors who are actively seeking to disrupt operation of the system. Accounting for such adversaries is challenging from a computational standpoint because it involves implicit knowledge of all the ways in which the future might unfold as a result of a given action. This work is to understand and mitigate the impact of this complexity by developing techniques for compactly representing the effects of uncertainty using sophisticated mathematical techniques, with which, for example, one can intelligently determine a small set of "important'' scenarios whose consideration will still allow for determination of an optimal decision in the present that implicitly takes into account all possible future scenarios.The general class of optimization problems that will be studied in this project are those in which the variables can be partitioned into subsets whose values must be fixed in stages. The constraints of later stages depend both on the values of variables fixed in earlier stages and on the realized values of certain random variables. A key feature of the general framework is that the variables in each stage may be controlled by different decions-makers with different objective functions. This class includes two important and challenging special cases - multistage stochastic programming with recourse and multilevel programming. The features of these two classes are complimentary and there is much to be gained by development of a unified approach. The overall goal of this research is to develop computational methods for such models, focusing in particular on the case in which there are discrete variables.