SGER: Linear Optimization vs. Nonlinear Equilibrium

SGER：线性优化与非线性平衡

• 批准号: 0836338
• 负责人: Roman Polyak
• 金额: $ 14.48万
• 依托单位: George Mason University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2008
• 资助国家: 美国
• 起止时间: 2008-07-01 至 2010-12-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0836338&HistoricalAwards=false
• 关键词: SGER; Linear; Optimization; vs.; Nonlinear

Proposal: ID: CCF - 0836338 Title: SGER: Linear Optimization vs. Nonlinear Equilibrium PI: Polyak, Roman A.Inst: George Mason University ABSTRACT:An innovative idea for reformulating the standard linear programming problem by taking into account more realistic scenarios from market economics is being considered in this proposal. The standard linear programming formulation of resource allocation problem assumes that the cost of a commodity is independent of the level of production. As one knows this is not the case in reality. By making the cost a function of the production, the PI formulates the problem in more general terms. However, under some natural but simplifying assumptions (which are somewhat technical to describe) on the nature of the cost function, the solution complexity of the problem turns out to be lower than the worst case complexity of the solution to the standard linear programming problem. In fact, there are indications that an O(n^2) solution can be obtained in this nonstandard formulation by the PI. This is paradoxical in some sense (that a more general problem has a simpler solution!), but apparently not so because for the LP formulation the geometry of the feasible set is a polytope, whereas its is a much simpler region under the new formulation of the problem. Also, the new formulation has close ties with the theory of n- person games.

提案：身份证号：CCF - 0836338标题：SGER：线性优化与非线性均衡PI：Polyak，Roman A.Inst：乔治梅森大学摘要：本提案考虑了一个创新的想法，通过考虑市场经济学中更现实的场景来重新制定标准线性规划问题。资源配置问题的标准线性规划公式假设商品的成本与生产水平无关。正如人们所知道的那样，事实并非如此。通过使成本成为生产的函数，PI用更一般的术语来表述问题。然而，在一些自然但简化的假设下（描述起来有些技术性），这个问题的解决方案的复杂性比标准线性规划问题的解决方案的最坏情况的复杂性要低。实际上，有迹象表明PI可以在这个非标准公式中获得O（n^2）解。这在某种意义上是矛盾的（更一般的问题有更简单的解决方案！），但显然不是这样，因为对于LP公式化，可行集的几何形状是多面体，而在问题的新公式化下，它是一个简单得多的区域。同时，新的表述与多人对策理论有着密切的联系.