CAREER: Large Scale Stochastic Control: A Math Programming and Discrete Optimization Lens

该学院早期职业发展(CALEAR)项目的研究目标是为大规模随机控制提供新的、近似的方法，这些方法易于“开箱即用”，只需很少或不需要专家调整。在更高的层面上，研究将利用为确定性优化问题开发的算法技术和分析模式，设计大规模随机控制的算法。该项目由两个互补的推进部分组成。第一个问题是通过最优控制的非标准特征推导出近似动态规划(ADP)的新的数学规划公式。ADP算法构成了大规模控制的一般方法。这些新的数学编程公式承诺了简单性和健壮性，同时潜在地承认了强大的理论性能保证。第二个重点涉及确定随机控制问题的类别，在这些问题中，人们可以通过频繁的重新优化和有限的“向前看”来对抗不确定性。一条途径将包括为一大类随机控制问题开发一个抽象的建模框架，类似于拟阵上的离散优化问题--这是一类研究得很好且相对容易处理的离散优化问题。第二种方法将包括分析动态的“分配”或“打包”问题，这些问题的确定性类似是简单的线性规划；这种模型出现在收入管理、医疗保健和排队等不同的环境中。目标是追求极其简单、易于实施、基于重新优化的方案的分析和开发。促进这一分析的工具将包括描述此类问题中“基础变化”的动态。上述研究议程植根于现实世界的应用。事实证明，ADP算法在从石油勘探到期权定价等领域都是有价值的工具；上述议程可能会使这些计划更接近成为“技术”。上面提到的拟阵框架捕获了非标准处理系统的功能，这些功能普遍出现在关键的医疗保健提供设置和其他应用程序中。我们关注的动态分配问题构成了在线广告系统、收入管理系统甚至互联网交换机决策的核心计算例程，通常是在亚毫秒级。因此，作为这项研究的一部分开发的算法可能会部署在几个与制造业、医疗保健和电子商务相关的环境中。总而言之，如果成功，这项研究将为问题谱的“一般”和“高度成功”两个方面的随机控制提供基本的和实际相关的新工具。

The research objective of this Faculty Early Career Development (CAREER) project seeks to deliver new, approximate approaches for large-scale stochastic control that are easy to implement `out of the box' with little or no expert tuning. At a high level, the research will leverage algorithmic techniques and modes of analysis developed for deterministic optimization problems, in the design of algorithms for large-scale stochastic control. The project consists of two complementary thrusts. The first concerns deriving new math programming formulations for Approximate Dynamic Programming (ADP) via non-standard characterizations of optimal control. ADP algorithms constitute a general approach to large-scale control. These new math programming formulations promise simplicity and robustness, while potentially admitting strong theoretical performance guarantees. The second thrust concerns identifying classes of stochastic control problems wherein one may combat uncertainty with frequent re-optimization and limited `lookahead'. One avenue will consist of developing an abstract modeling framework for a large class of stochastic control problems analogous to that for discrete optimization problems over matroids - an eminently well-studied and relatively tractable class of discrete optimization problems. A second avenue will consist of analyzing dynamic `allocation' or `packing' problems whose deterministic analogues are simple linear programs; such models arise in settings as diverse as revenue management, healthcare and queueing. The goal is to pursue the analysis and development of extremely simple, easy to implement, re-optimization based schemes. The tool facilitating this analysis will consist of a characterization of the dynamics of `basis changes' in such problems.The research agenda above is rooted in real world applications. ADP algorithms have proven to be valuable tools in areas as far ranging as oil exploration to option pricing; the agenda above will potentially bring these schemes closer to being `technologies'. The matroid-like framework mentioned captures features of non-standard processing systems that arise ubiquitously in critical healthcare delivery settings among other applications. The dynamic allocation problems we focus on form the core computational routine in decisions made in online advertising systems, revenue management system and even internet switches, frequently at sub milli-second timescales. As such, the algorithms developed as part of this research will potentially be deployed in several manufacturing, healthcare and e-commerce related settings. In summary, if successful, this research will provide fundamental and practically relevant new tools for stochastic control at both the `generic' and `highly suctured' ends of the problem spectrum.