Interior Point Methods for Complementarity Problems

自然科学、经济学和工程学中广泛的实际问题被建模为互补问题。本项目历时三年，主要研究互补问题的新型内点法的发展、分析和实现等几个基本理论和计算问题。本研究的智力优势在于开发了具有多项式复杂度和超线性收敛的内点算法，用于解决一般情况下的互补问题。更广泛的影响将反映在理论结果和由此产生的软件包对自然科学，经济学和技术的几个重要领域的适用性上，例如：具有接触和摩擦的多体系统的模拟，机器人技术，混合系统，数学金融中的期权定价，能源市场的均衡问题等。该提案的另一个影响是在一个至关重要的前沿领域培养学生。该项目预计将以切实的方式有助于阐明一些重要的问题，这些问题仍然是关于解决对称锥上线性互补问题的内点法的行为的开放问题。特别注意不同加权中心路径的解析性和曲率，以及相应的内点法的复杂性。在最坏的情况下或根据迭代次数的期望值，将确定对称锥上的非线性互补问题的新类别，这些问题在多项式时间内可解。在此基础上，提出了一类非对称锥上具有多项式复杂度和超线性收敛性的内点法。

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 meritof 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 ofdifferent weighted central paths and the complexity of the corresponding interior point methods. New classes of nonlinear complementarity problems over symmetric cones that are solvable inpolynomial 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.