Interior Point Methods for Complementarity Problems

University Of Maryland Baltimore County, Baltimore MD

Investigators

Abstract

A wide range of practical problems in the natural sciences, economics, and engineering are modeled as complementarity problems. This project involves a three-year research effort on several fundamental theoretical and computational issues related to the development, analysis, and implementation of novel interior point method for complementarity problems. The intellectual merit of this research consists in the development of interior point algorithm with polynomial complexity and superlinear convergence for solving complementarity problems in a rather general setting. The broader impacts will be reflected in the applicability of the theoretical results and the resulting software packages to several important areas of natural sciences, economics, and technology, such as: simulation of multibody systems with contact and friction, robotics, hybrid systems, option pricing in mathematical finance, equilibrium problems in energy markets, etc. Another impact of the proposal is the training of students in a vital, cutting edge area. The project is expected to contribute in tangible ways to elucidate some important problems that are still open about the behavior of interior point methods for solving linear complementarity problems over symmetric cones. Particular attention will be given to the analyticity and the curvature of different weighted central paths and the complexity of the corresponding interior point methods. New classes of nonlinear complementarity problems over symmetric cones that are solvable in polynomial time, either in the worst case scenario or in terms of the expected value of the number of iterations, will be identified. Furthermore, new interior point methods with polynomial complexity and superlinear convergence over a class nonsymmetric cones will be developed.