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.