Continuous local search
Continuous local search
复制标题
持续本地搜索
DOI：
--
复制
发表时间：
2011
期刊：
影响因子：
--
通讯作者：
C. Papadimitriou
中科院分区：
文献类型：
--
作者：
C. Daskalakis;C. Papadimitriou
我们引入CLS（连续局部搜索），它是一类多项式时间可检验的全函数，位于PPAD和PLS的交集之中，并且涵盖了一种特别温和的局部优化类型，其中定义域是连续的（与组合的相对），所涉及的函数也是连续的。我们表明这个类别包含几个众所周知的有趣问题，这些问题此前已知位于PLS和PPAD的交集中，但在其他方面无法分类：寻找收缩映射的不动点、P矩阵的线性互补问题、寻找一个低次多项式目标的驻点、沙普利和康登的简单随机博弈，以及在拥塞、隐式拥塞和网络协调博弈中寻找混合纳什均衡。最后四个问题属于CCLS（凸CLS），它是PPAD ∩ PLS的另一个子类，寻求一个按分量凸函数的按分量局部最小值。这些问题中的任何一个或全部对于相应的类别是否是完全的，这仍然是未解决的问题。
We introduce CLS, for continuous local search, a class of polynomial-time checkable total functions that lies at the intersection of PPAD and PLS, and captures a particularly benign kind of local optimization in which the domain is continuous, as opposed to combinatorial, and the functions involved are continuous. We show that this class contains several well known intriguing problems which were heretofore known to lie in the intersection of PLS and PPAD but were otherwise unclassifiable: Finding fixpoints of contraction maps, the linear complementarity problem for P matrices, finding a stationary point of a low-degree polynomial objective, the simple stochastic games of Shapley and Condon, and finding a mixed Nash equilibrium in congestion, implicit congestion, and network coordination games. The last four problems belong to CCLS, for convex CLS, another subclass of PPAD ∩ PLS seeking the componentwise local minimum of a componentwise convex function. It is open whether any or all of these problems are complete for the corresponding classes.