P0线性互补问题的新同伦方法

姜兴武，王秀玉

(1.吉林工商学院基础部，长春130062;2.长春工业大学基础科学学院，长春130012)

互补问题与数学规划、对策论、不动点理论和极大极小问题等密切相关，在工程、力学、经济及交通等许多实际问题中应用广泛.线性互补问题是互补问题的一个重要分支，即考虑问题(LCP(M，q)):求x≥0，使得y=Mx+q≥0且xTy=0，其中M为一个n阶方阵.

目前，求解互补问题的方法很多，其中同伦方法由于具有大范围收敛性而成为求解互补问题的重要工具.本文通过构造与文献［1-7］不同的同伦方程，对P0线性互补问题进行求解，获得了理想的结果.x≥0(x＞0)表示向量x的每个分量为非负(正数);w=(x，y)表示向量w=(xT，yT)T，xi表示向量x的第i个分量.

引理1［8］令M∈ℝn×n为任意矩阵，则下列情况等价:

1)M∈ℝn×n是 P0矩阵;

2)M的所有主子式均为非负数;

3)对于任意的正数ε＞0，M+εE为P矩阵，其中E是n阶单位矩阵.

引理2［8］M∈ℝn×n为P矩阵的充分必要条件是:M的全部主子式均为正值.

假设条件:

(H1)M∈ℝn×n是 P0矩阵;

(H2)互补问题LCP(M，0)只有零解，即y=Mx，x≥0，y≥0，xTy=0只有零解.

记w=(x，y)，任取 y(0)＞0 及 x(0)=(M+E)-1(y(0)-q)，w=(x(0)，y(0))，构造如下同伦方程H:ℝn×ℝn→ℝ2n:

当μ=1时，式(1)为

证明:将y(0)视为变量，以w(0)，w，μ为自变量的同伦方程记为Hw(0)(w，μ)，它的Jacobian矩阵记为

证明:Γw(0)的存在性由定理1可得.若Γw(0)无界，则必存在子列{(x(k)，y(k)，μk)}∈Γw(0)，使得当k→∞时，有‖(x(k)，y(k)，μk)‖→∞，由同伦方程(1)的第二个等式得

由式(2)及 μ∈(0，1］可知

将式(2)改写为

则由同伦方程(1)的第一个等式得

情形1)μ*∈［0，1).

可断定μ*≠0，否则若μ*=0，则由式(7)得y(*)=Mx(*).而由式(4)可知，对任意的i=1，2，…，n，有

x(*)≥0，y(*)≥0，(x(*))Ty(*)=0，与假设条件(H2)矛盾.由引理1知，M+μ*E为P矩阵，式(7)与M+μ*E为P矩阵矛盾.

情形2)μ*=1.

① 若{(1-μk)x(k)}仍为无界序列，则式(5)两边同乘1-μk得

令

式(10)与M+E为P矩阵矛盾.

式(12)与{x(k)}的无界性矛盾.

将式(8)两边取极限得

式(14)与M+E是P矩阵矛盾.

证明:由定理1和定理2易知Γw(0)为有界曲线.由一维流形分类定理知，Γw(0)微分同胚于单位圆周或单位区间(0，1］(证明与文献［6］的定理2.1类似).由

是非奇异的知，Γw(0)不能微分同胚于单位圆周，只能微分同胚于单位区间.记(w(*)，μ*)为Γw(0)的极限点，则只可能发生下列3种情形:

综上可见，本文通过构造新同伦方程，得到了P0线性互补问题 LCP(M，q)有解与互补问题LCP(M，0)只有零解的关系.

［1］Kojima M，Megiddo N，Mizuno M.A General Framework of Continuation Methods for Complementarity Problems［J］.Math Oper Res，1993，18(4):945-963.

［2］YU Qian，HUANG Chong-chao，WANG Xian-jia.A Combined Homotopy Interior Point Method for the Linear Complementarity Problem［J］.Applied Mathematics and Computation，2006，179(2):696-701.

［3］XU Qing，DANG Chuang-yin.A New Homotopy Method for Solving Non-linear Complementarity Problems［J］.Optimization，2008，57(5):681-689.

［4］ZHAO Yun-bin，LI Gong-nong.Properties of a Homotopy Solution Path for Complementarity Problems with Quasimonotone Mappings［J］.Applied Mathematics and Computation，2004，148(1):93-104.

［5］LI Gong-nong.Analysis for a Homotopy Path of Complementarity Problems Based on μ-Exceptional Family［J］.Applied Mathematics and Computation，2005，169(1):657-670.

［6］DING Jun-di，YIN Hong-yan.A New Homotopy Method for Nonlinear Comolementarity Problems［J］.Numericla Mathematics A Journal of Chinese Universities:English Series，2007，16(2):155-163.

［7］WANG Xiu-yu，JIANG Xing-wu，LIU Qing-huai.New Homotopy Method for Solving Nonlinear Complementarity Problems［J］.Journal of Jilin University:Science Edition，2012，50(3):494-498.(王秀玉，姜兴武，刘庆怀.求解互补问题的新同伦算法［J］.吉林大学学报:理学版，2012，50(3):494-498.)

［8］韩继业，修乃华，戚厚铎.非线性互补理论与算法［M］.上海:上海科学技术出版社，2006.