一致P-函数非线性互补问题的宽邻域不可行内点算法及其计算复杂性.pdfVIP

2007~ 12月 高 等 学 校 计 算 数 学 学 报 第29卷第4期 一致P一函数非线性互补问题的宽邻域 不可行内点算法及其计算复杂性 王浚岭 (三峡大学理学院数学系，宜昌443002) A W IDE．NEIGHB oRHo oD INFEASIBLE—INTERIoR．PoINT ALGoRITHM S FoR UNIFoRM P．FUNCTIoN NoNLINEAR COMPLEMENTARY PRoBLEM S AND ITS CoMPUTATIoNAL CoMPLEXITY Wang Junling (College of Science，China Three Gorges University,Yichang 443002) Abstract In this paper，a new wide-neighborhood infeasible-interior．point algo- rithm for uniform P—function nonlinear complementary problems is presented and ， its convergence and computational complexity are discussed．The results indicate that the algorithm is a polynomial—time one，If the initial point is a feasible-interior point，then the algorithm reduces to a wide—neighborhood feasible-interior．point algorithm． Key words nonlinear complementary problem，wide-neighborhood infeasible- interior—point algorithms ，computational complexity,uniform P-function ． AMS(2000)subject classifications 90C33 中图法分类号 O221．2 湖北省教育厅重点科研项目(D2006l3009) 收稿日期：2005-09-17。 · 312· 王浚岭：一致P一函数非线性互补问题的宽邻域不可行内点算法及其计算复杂性 第4期 1引言与记号 单调线性互补问题和线性规期问题的原始一对偶路径跟踪算法，1989年的文献【1、2】 分别首先提出．以后又出现了一些改进的算法．早期的原始一对偶路径跟踪算法及其改进 算法的迭代点列大都是在包含中心路径C的一个2．范数的窄邻域里，这种可行内点算法 通常理论上具有最好的迭代复杂性D( )，但是由于窄邻域极大地限制了迭代步长，实 际的数值计算结果并不理想，因此原始一对偶路径跟踪算法在实际计算时产生了各种宽邻 域(包括大邻域、最大步长等)的修正算法．尽管宽邻域可行内点算法的迭代复杂性理论 上证明一般仅为O(nL)，但由于数值计算结果的有效性，文献[3]指出，在实际应用中的内 点算法大多使用宽邻域，并列出了一些有关这两类算法的参考文献．使用幂级数算法(或 称为高阶算法)，可使迭代复杂性界减少，并且当阶数趋于无穷时，可使后者的迭代复杂性 上界趋于前者． 然而求解非单调互补问题的内点算法(特别是多项式时间算法)成果甚少．文献[4】讨 论了当f(x)是一致P_函数时下面问题(1)的中心路径的存在唯一性；文献【5】给出求解 一 类非单调线性互补问题的内点算法的一般框架；