Theory and Applications of Weighted Complementarity Problems

加权互补问题（wCP）是应用数学中的一个新范式，为分析和解决经济学、多体动力学、大气化学等科学技术领域的各种平衡问题提供了一个统一的框架。它代表了互补问题（CP）概念的一个深远的推广。一般来说，wCP包括寻找属于流形与锥的交点的一对向量，使得它们在某种代数中的乘积等于给定的权向量。当权向量为零时，wCP的理论变得比CP的理论更复杂。本课题的目的是研究wCP的解析性质和几何性质，并开发有效的算法来计算其解。重点寻找保证wCP解集凸性的充分条件，研究wCP的不同中心路径及其曲率与相应路径跟踪算法计算复杂度的关系，建立某些中心路径的可解析性。后一个性质对路径跟踪算法的超线性收敛性有影响。即使对于非负正交上的线性wCP，这些问题也不是微不足道的，但在非线性情况下和/或更一般的锥，如二阶锥或正半定矩阵的锥，它们变得非常困难。该项目的智力价值在于理解了wCP的理论性质和求解wCP的内点法的计算复杂性。这将现有的理论从CP扩展到更一般的一类问题。wCP的泛化是非平凡的，需要发明新的数学技术。近年来，科学界开始了一项持续的研究工作，以理解市场均衡的可计算性，部分原因是互联网上高利润市场的出现。将平衡问题表述为wCP打开了为其数值解设计高效算法的可能性。例如，费雪的竞争市场均衡模型可以表述为wCP，而阿罗-德布鲁竞争市场均衡问题（由诺贝尔奖得主肯尼斯·约瑟夫·阿罗和杰拉德·德布鲁提出）可以表述为自对偶wCP。Fisher和Arrow-Debreu平衡问题解存在性的最初证明是非建设性的。本项目的目标之一是将一大类市场均衡问题和博弈论问题作为可进行有效计算的wcp进行公式化。由于wCP的适用性超出了市场均衡问题，因此拟议研究的更广泛影响是显著的。在这个研究项目中，研究者的目标是确定科学和工程中的几类问题，这些问题可以被建模为wCP。研究wcp的理论特性并为其数值解开发强大的算法将为科学界提供新的建模和计算工具，这可能对美国经济产生积极影响。

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.