Theory and Applications of Weighted Complementarity Problems

加权互补问题的理论与应用

• 批准号: 1311923
• 负责人: Florian Potra
• 金额: $ 18万
• 依托单位: University of Maryland Baltimore County
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2013
• 资助国家: 美国
• 起止时间: 2013-08-15 至 2017-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1311923&HistoricalAwards=false
• 关键词: Theory; Applications; Weighted; Complementarity; Problems

The weighted complementarity problem (wCP) is a new paradigm in applied mathematics that provides a unifying framework for analyzing and solving a variety of equilibrium problems in economics, multibody dynamics, atmospheric chemistry and other areas in science and technology. It represents a far reaching generalization of the notion of a complementarity problem (CP). Generally speaking, wCP consists in finding a pair of vectors belonging to the intersection of a manifold with a cone, such that their product in a some algebra equals a given weight vector. When the weight vector is equal to zero wCP reduces to CP. With nonzero weight vectors the theory of wCP becomes more complicated than the theory of CP. The aim of this project is to investigate the analytic and geometric properties of wCP and to develop efficient algorithms for computing its solution. The investigator focuses on finding sufficient conditions ensuring the convexity of the solution set of wCP, on studying different central paths for wCP and the relationship between their curvatures and the computational complexity of the corresponding path-following algorithms, and on establishing the analyticity of certain central paths. The latter property has implications on the superlinear convergence of the path-following algorithms. These questions are not trivial even for linear wCP over the non-negative orthant, but they become very difficult in the nonlinear case and/or for more general cones such as the second order cone or the cone of positive semidefinite matrices. The intellectual merit of the project lies in understanding the theoretical properties of wCP and the computational complexity of interior point methods for solving wCP. This extends existing theory from CP to a more general class of problems. The generalization for wCP is highly nontrivial and requires invention of new mathematical techniques.In recent years the scientific community has embarked on a sustained research effort for understanding computability of market equilibria, motivated in part by the emergence of highly lucrative markets on the internet. Formulating an equilibrium problem as a wCP opens the possibility of devising highly efficient algorithms for its numerical solution. For example, Fisher's competitive market equilibrium model can be formulated as a wCP, while the Arrow-Debreu competitive market equilibrium problem (due to Nobel prize laureates Kenneth Joseph Arrow and Gerard Debreu) can be formulated as a self-dual wCP. The original proofs of existence of solutions to the Fisher and Arrow-Debreu equilibrium problems were nonconstructive. One of the objectives of the present project is to formulate a large class of market equilibrium problems and game-theoretical problems as wCPs that are amenable to efficient computation. The broader impacts of the proposed research are significant because the applicability of wCP extends beyond market equilibrium problems. In this research program, the investigator aims at identifying several classes of problems in science and engineering that can be modeled as wCP. Studying theoretical properties of wCPs and developing robust algorithms for their numerical solution will provide the scientific community with new modeling and computational tools that are likely to have a positive impact on the US economy.

加权互补问题(WCP)是应用数学中的一种新范式，它为分析和解决经济学、多体动力学、大气化学等科学技术领域的各种平衡问题提供了一个统一的框架。它代表了互补性问题(CP)这一概念的深远概括。一般说来，WCP就是找到一对属于流形和锥的交集的向量，使得它们在某个代数中的乘积等于一个给定权向量。当权向量等于零时，WCP简化为Cp。有了非零权向量，WCP理论变得比CP理论更复杂。这个项目的目的是研究WCP的解析和几何性质，并开发有效的算法来计算它的解。研究WCP问题解集凸性的充分条件，研究WCP问题的不同中心路径及其曲率与相应路径跟踪算法的计算复杂性之间的关系，以及建立某些中心路径的解析性。后一性质对路径跟踪算法的超线性收敛有一定的影响。即使对于非负正交上的线性WCP，这些问题也不是微不足道的，但在非线性情况下和/或对于更一般的锥，如二阶锥或正半定矩阵的锥，这些问题变得非常困难。该项目的智力优势在于了解了WCP的理论性质和求解WCP的内点法的计算复杂性。这将现有的理论从CP扩展到更一般的问题类。WCP的泛化是非常不平凡的，需要发明新的数学技术。近年来，科学界开始了一项持续的研究努力，以了解市场均衡的可计算性，部分原因是互联网上出现了利润丰厚的市场。将均衡问题描述为WCP，为设计高效的数值解算法提供了可能。例如，Fisher的竞争市场均衡模型可以被描述为WCP，而Arrow-Debreu竞争市场均衡问题(由于诺贝尔奖获得者Kenneth Joseph Arrow和Gerard Debreu)可以被描述为自我双重WCP。关于Fisher和Arrow-Debreu均衡问题解的存在性的原始证明是非建设性的。本项目的目标之一是将一大类市场均衡问题和博弈论问题表述为易于有效计算的WCP。拟议研究的更广泛的影响是显著的，因为WCP的适用范围超出了市场均衡问题。在这个研究项目中，研究人员的目标是确定科学和工程中的几类问题，这些问题可以被建模为WCP。研究WCP的理论性质并为其数值解开发稳健的算法，将为科学界提供新的建模和计算工具，这些工具可能对美国经济产生积极影响。