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.
