线性互补问题解的存在性

杨泰山，姜兴武，王秀玉

（1.吉林大学 数学学院，长春130012；2.吉林工商学院 基础部，长春130062；3.长春工业大学 基础科学学院，长春130012）

线性互补问题是：求x≥0，使得y＝Mx＋q≥0且有xTy＝0，其中M为一个n阶方阵，该互补问题记为LCP（M，q），称为非齐次互补问题.当q＝0时，记为LCP（M，0），称为齐次互补问题.线性互补问题是互补问题的一个重要组成部分，并且二次规划的K－K－T方程也为线性互补问题.

同伦方法由于具有大范围收敛性，目前已成为求解数学问题的一个重要工具.文献［1］构造了一类同伦方程求解互补问题；文献［2－6］对文献［1］的同伦方程给出了不同条件下同伦路径的存在性；文献［7］建立了与文献［1］完全不同的同伦方程，获得了互补问题的可解性，但文献［7］的同伦方程当参数为零时不能回到原互补问题，也未给出具体条件；文献［8］改进了文献［7］的结果，利用同伦方法对互补问题进行求解.本文运用文献［1］的同伦方程给出半单调线性互补问题同伦路径的存在性、有界性及收敛性，并给出LCP（M，q）有解与LCP（M，0）只有零解的关系.

本文用x≥0或x∈ℝn＋（x＞0或x∈ℝn＋＋）表示向量x的每个分量为非负（正数），用w＝（x，y）表示向量w＝（xT，yT）T.

1 预备知识

定义1［9］如果对任意的x≥0，x≠0，存在一个分量xk＞0，使得（Mx）k≥0，则n阶方阵M∈ℝn×n称为半单调矩阵.

当M为半单调矩阵时，互补问题LCP（M，q）称为半单调线性互补问题.

假设条件：

（H1）M∈ℝn×n是半单调矩阵；

（H2）y＝Mx，x≥0，y≥0，xTy＝0只有零解；

（H3）存在u∈ℝn＋＋，使得v＝Mu＋q＞0；

（H4）存在常数τ≥0，α≥0，1＜β＜2，使得对任意的x∈ℝn，y∈ℝn，下式成立：

例1

则M显然为半单调矩阵.令

则M不是P0矩阵.

只有零解.M 满足假设条件（H1），（H2）.

2 主要结果

记w＝（x，y），任取x（0）＞0，y（0）＞0及w＝（x（0），y（0）），构造如下同伦方程：

其中X＝diag（x）.同伦方程（1）也记为Hw（0）（w，μ），并记

证明：Γw（0）的存在性由定理1可得.Γw（0）⊆ℝn＋×ℝn＋×（0，1］显然成立.若Γw（0）无界，则必存在子列（x（k），y（k），μk）∈Γw（0），使得当k→∞时，有‖（x（k），y（k），μk）‖→∞，由同伦方程（1）的第二个等式得

由式（2）可知

由同伦方程（1）的第一个等式得

情形1）μ＊∈［0，1）.

由式（2）及x（＊），y（＊）的定义，对任意的i＝1，2，…，n，得

又由式（6）知（x（＊），y（＊））为齐次互补问题LCP（M，0）的非零解，与假设（H2）矛盾.

情形2）μ＊＝1.分两种情形论证.

令

而由式（2）可知，对任意的i＝1，2，…，n，有

因而由式（2），（9）得

式（10）与｛x（k）｝无界性矛盾.

式（4）两边取极限得

再由式（2）得

由式（4）－式（13），得

将式（2）代入式（14）的分量形式，对所有的i＝1，2，…，n，得

由式（15）可知

由式（16）可知，当x（k）i→∞时，有

且对所有的i＝1，2，…，n，有

由于｛x（k）｝为无穷序列，因而存在整数s，p，使得

显然有

由式（18），（19）可知，对充分大的k，有

由条件（H3）知下式成立：

整理式（21）得

证明：由定理1～定理3易知Γw（0）为有界曲线.由一维流形分类定理知，Γw（0）微分同胚于单位圆周或单位区间（0，1］（证明与文献［7］的定理2.1类似）.注意到

是非奇异的，得Γw（0）不能微分同胚于单位圆周，而只能微分同胚于单位区间.记（w（＊），μ＊）为Γw（0）的极限点，则只有下列4种情形可能发生：

［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］XU Qing，DANG Chang－yin.A New Homotopy Method for Solving Non－linear Complementarity Problems［J］.Optimization，2008，57：681－689.

［3］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.

［4］ZHAO Yun－bin，LI Gong－nong.Properties of a Homotopy Solution Path for Complementarity Problems with Quasi－monotone Mappings［J］.Applied Mathematics and Computation，2004，148：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］WANG Xiu－yu，JIANG Xing－wu， LIU Qing－huai.The Combined Homotopy Method for Nonlinear Complementarity Problems［J］.Acta Mathematicae Applicatae Sinica，2012，35（3）：430－440.（王秀玉，姜兴武，刘庆怀.非线性互补问题的组合同伦算法 ［J］.应用数学学报，2012，35（3）：430－440.）

［7］DING Jun－di，YIN Hong－you.A New Homotopy Method for Nonlinear Complementarity Problems ［J］.Numericla Mathematics，A Journal of Chinese Universities：English Series，2007，16（2）：155－163.

［8］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.）

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