内点算法作为求解优化问题的有效算法之一,不仅具有多项式收敛性,还有良好的实际计算效果.自1984年第一个具有实用性的多项式内点算法——Karmarkar算法提出以来,经过二十多年的发展,内点算法的研究已取得了丰硕的成果.如今,内点算法已被成功地应用于求解线性规划、凸规划、互补问题、半定规划、二阶锥规划等众多优化问题.许多基于内点算法的优化软件包被开发并被广泛利用.　　本文主要研究P*(K)互补问题的Mehrotra型预估-校正算法.互补问题是一类应用广泛的数学问题,被应用于工程、经济分析、交通平衡及最优控制等众多领域.因此,对互补问题的研究有重要的理论价值和实际意义.本文的研究工作主要是对线性规划的Mehrotra型预估-校正算法的推广,将其应用于求解P*(K)线性互补问题和P*(K)非线性互补问题,并探讨新算法的多项式迭代复杂性.　　全文分为四章.第一章简要介绍相关基础知识及研究背景;第二章提出了一种P*(K)线性互补问题的Mehrotra型预估-校正算法,并给出了算法的多项式复杂性证明,还通过数值实验验证了算法的有效性;第三章针对单调非线性互补问题和P*(K)非线性互补问题,分别设计了基于“安全步策略”的Mehrotra型预估-校正算法,并在映射满足尺度化李普希茨条件(Scaled Lipschitz Condition)的假设下,证明了这两种算法的多项式迭代复杂性;第四章总结全文,并对后续工作进行了展望.