SGER: Linear Optimization vs. Nonlinear Equilibrium

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

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.