权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

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

职业：大规模随机控制：数学编程和离散优化透镜

基本信息

批准号：
1054034
负责人：
Vivek Farias
金额：
$ 40万
依托单位：
Massachusetts Institute of Technology
依托单位国家：
美国
项目类别：
Standard Grant
财政年份：
2011
资助国家：
美国
起止时间：
2011-02-15 至 2017-01-31
项目状态：
已结题

来源：
https://www.nsf.gov/awardsearch/showAward?AWD_ID=1054034&HistoricalAwards=false
关键词：
CAREER Large Scale Stochastic Control

项目摘要

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.

该学院早期职业发展（CAREER）项目的研究目标旨在为大规模随机控制提供新的近似方法，这些方法很容易实现“开箱即用”，很少或没有专家调整。在高层次上，该研究将利用为确定性优化问题开发的算法技术和分析模式，设计大规模随机控制算法。该项目包括两个相辅相成的重点。第一个问题是通过最优控制的非标准特征来推导近似动态规划（ADP）的新数学规划公式。ADP算法构成了大规模控制的一般方法。这些新的数学编程公式承诺简单性和鲁棒性，同时可能承认强大的理论性能保证。第二个推力涉及识别类随机控制问题，其中一个可以打击不确定性与频繁的重新优化和有限的“lookahead”。一个途径将包括开发一个抽象的建模框架，一类随机控制问题类似于拟阵上的离散优化问题-一个非常好的研究和相对容易处理的一类离散优化问题。第二条途径将包括分析动态的“分配”或“包装”问题，其确定性的类似物是简单的线性程序;这种模型出现在不同的设置，如收入管理，医疗保健和医疗保健。我们的目标是追求分析和开发非常简单，易于实现，基于重新优化的方案。促进这一分析的工具将包括对这些问题的“基础变化”动态的描述，上述研究议程植根于真实的世界应用。ADP算法已被证明是从石油勘探到期权定价等领域的宝贵工具;上述议程将有可能使这些计划更接近于“技术”。所提到的类matroid框架捕获了在关键的医疗保健提供设置以及其他应用中普遍存在的非标准处理系统的特征。我们关注的动态分配问题形成了在线广告系统，收入管理系统甚至互联网交换机中决策的核心计算程序，通常在毫秒级的时间尺度上。因此，作为本研究的一部分开发的算法将有可能部署在几个制造业，医疗保健和电子商务相关的环境中。总之，如果成功的话，这项研究将提供基本的和实际相关的新工具，随机控制的“通用”和“高度suctured”的问题频谱的两端。