Interior Point Methods for Complementarity Problems

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

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.