Markov Decision Problem and Linear Programming

马尔可夫决策问题和线性规划

• 批准号: 0306611
• 负责人: Yinyu Ye
• 金额: $ 20.51万
• 依托单位: Stanford University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2003
• 资助国家: 美国
• 起止时间: 2003-08-15 至 2007-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0306611&HistoricalAwards=false
• 关键词: Markov; Decision; Problem; Linear; Programming

The aim of this proposal is to further develop the complexity theory of Linear Programming (LP), which continually plays a central role in complexity analysis. In particular, we analyze the Markov Decision Problem (MDP) with n states and m actions for each state, a special class of real-number linear programs with the Leontief matrix structure. The research objectives and activities include the following: 1) Develop a new class of algorithms, "combinatorial interior-point algorithms", for solving the MDP, with the best achievable complexity result and practical efficiency; and establish certain complexity lower bounds for the MDP, which may provide a "negative result" on the quest for whether or not there is a strongly polynomial time algorithm for LP. 2) Both undergraduate and graduate students will participate in the project, new course materials on the MDP will be produced, and the PI will also give presentations to the Stanford Summer Program for grades K-12 and community college students in the Bay Area. 3) Apply the new fast MDP algorithm to research activities in function areas such as Call Admission and Routing, Strategic Asset Allocation, Supply-Chain Management, Emissions Reductions, and Semiconductor Wafer Fabrication.Due to the relentless research effort in LP algorithms, a linear program can be solved today one million times faster than it was done twenty years ago. Businesses, large and small, use linear programming models to optimize communication systems, to schedule transportation networks, to control inventories, to plan investments, and to maximize productivity. Furthermore, LP has become a popular subject now taught in undergraduate, graduate, and MBA curriculums, advancing human knowledge and promoting scientific understanding. Recently, there has been a renewed and strong interest in the MDP (a special large-scale LP) due to its wide applications. With the rising demand in telecommunication network resources, effective management is as important as ever. Call Admission (deciding which calls to accept/reject) and routing (allocating links in the network to particular calls) are examples of decisions that must be made at any point in time. The objective is to make the "best" use of limited network resources. Such sequential decision problems can be addressed by a dynamic programming model and the MDP. Another application: the threat of global warming that may result from the accumulation of carbon dioxide and other "greenhouse gases" poses a serious dilemma. In particular, cuts in emission levels bear a detrimental short-term impact on economic growth. At the same time, a depleting environment can severely hurt the economy - especially the agricultural sector - in the longer term. To complicate the matter further, scientific evidence on the relationship between emission levels and global warming is inconclusive, leading to uncertainty about the benefits of various cuts. One systematic approach to considering these conflicting goals involves the formulation of a dynamic system and MDP model that describes our understanding of economic growth and environmental science, as is done by Nordhaus. However, these MDP problems are too complex to be solved by the current MDP solvers. A major objective of the project is to develop new Markov Decision Algorithms such that these models would be effectively analyzed to satisfaction. Progress in the area of developing efficient algorithms for solving large-scale stochastic decision problems will be of great significance in improving industrial competitiveness, scientific understanding, and technology learning.

该提案的目的是进一步发展线性规划（LP）的复杂性理论，该理论在复杂性分析中一直发挥着核心作用。 特别是，我们分析了马尔可夫决策问题（MDP）的n个国家和m个行动的每个国家，一类特殊的实数线性规划的Leontief矩阵结构。 研究目标和活动包括：1）开发一类新的算法，“组合邻域点算法”，用于求解MDP，具有最佳的可实现的复杂性结果和实际效率;并建立一定的复杂性下界MDP，这可能会提供一个“否定结果”的追求是否存在一个强多项式时间算法的LP。 2)本科生和研究生都将参与该项目，将制作关于MDP的新课程材料，PI还将为斯坦福大学的K-12年级和湾区社区大学学生的暑期项目做演讲。3)将新的快速MDP算法应用于功能领域的研究活动，如呼叫接纳和路由，战略资产分配，供应链管理，减排和半导体晶圆制造。由于LP算法的不懈研究，今天线性规划的求解速度比20年前快100万倍。企业，无论大小，都使用线性规划模型来优化通信系统，调度运输网络，控制库存，计划投资，并最大限度地提高生产力。 此外，LP已成为一个受欢迎的主题，现在在本科，研究生和MBA课程中教授，推进人类知识和促进科学理解。近年来，由于其广泛的应用，MDP（一种特殊的大规模线性规划）又重新引起了人们的浓厚兴趣。 随着电信网络资源需求的不断增长，有效的管理显得尤为重要.呼叫准入（决定接受/拒绝哪些呼叫）和路由（将网络中的链路分配给特定呼叫）是必须在任何时间点做出的决策的示例。目的是“最佳”利用有限的网络资源。 这样的顺序决策问题可以通过动态规划模型和MDP来解决。另一个应用：二氧化碳和其他“温室气体”的积累可能造成全球变暖的威胁，这是一个严重的两难问题。 特别是，减少排放量会对经济增长产生不利的短期影响。 与此同时，从长远来看，环境恶化会严重损害经济，特别是农业部门。使问题进一步复杂化的是，关于排放水平与全球变暖之间关系的科学证据尚无定论，导致各种削减的好处不确定。一个系统的方法来考虑这些相互冲突的目标涉及制定一个动态系统和MDP模型，描述了我们对经济增长和环境科学的理解，如诺德豪斯所做的。 然而，这些MDP问题是太复杂了，目前的MDP求解器解决。 该项目的一个主要目标是开发新的马尔可夫决策算法，使这些模型能够有效地分析，以满足。 在开发解决大规模随机决策问题的有效算法方面取得进展，将对提高产业竞争力、科学理解和技术学习具有重要意义。