Markov Decision Problem and Linear Programming

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

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.