E0互補問題的變形凝聚同倫算法

王秀玉, 姜興武, 李 琳

(1. 長春工業大學 基礎科學學院, 長春 130012; 2. 吉林工商學院 基礎部, 長春 130062)

考慮非線性互補問題: 求x≥0, 滿足f(x)≥0, 且有xTf(x)=0, 其中f(x)=(f1(x),f2(x),…,fn(x))T是向量值的光滑函數. 當f為線性函數時, 互補問題稱為線性互補問題. 當f為E0-映射時, 互補問題稱為E0互補問題. 求解互補問題等價于求解下列非線性非光滑方程組：

(1)

上述互補問題廣泛應用于經濟、 工程生產及各種均衡模型中, 目前, 已有許多求解互補問題的方法, 如信賴域法[1]、 迭代法[2]、 投影法[3]、 例外族法[4]和同倫方法[5-9]等. 其中同倫方法由于具有大范圍收斂性, 已成為求解非線性數學問題的重要工具之一. 文獻[5-6]系統地研究了利用同倫方法求解互補問題; 文獻[7]利用文獻[5]的同倫方程討論了半定線性互補問題的可解性; 文獻[8]推廣了文獻[7]的結論, 給出了一類非單調互補問題解的存在性; 文獻[9]建立了與文獻[5-8]不同的同倫方程, 但缺少互補問題解存在的條件.

文獻[10]研究了凝聚函數的性質, 給出g(x,μ)光滑逼近極大函數g(x). 本文利用凝聚函數的變形形式構造同倫方程, 對E0互補問題進行求解.

設x≥0(x>0)表示向量x的每個分量為非負(正)數;f′表示向量值函數f: Rn→Rn的Jacobi矩陣;h表示數量值函數h: Rn→R的梯度.

1 變形凝聚函數

1)g(x)≤g(x,μ)≤g(x)+μlnm;

1)c(x)-μlnm≤c(x,μ)≤c(x);

本文令

φ: R2→R,φ(a,b)=-μln(e-a/μ+(1-μ)ce-b/μ),

c>0為常數,φ(a,b)稱為變形凝聚函數. 顯然有

φ(a,b)=-μln(e-a/μ+eln(1-μ)ce-b/μ)=-μln(e-a/μ+e-(b-μln(1-μ)c)/μ).

又由引理2可知

min(a,b-μln(1-μ)c)-μln2≤φ(a,b)≤min(a,b-μln(1-μ)c),

因而有

利用凝聚同倫方法求解非線性互補問題, 做如下假設：

(H1)fi(x)(i∈M)是Cl(l≥2)函數;

定義1[11]如果對任意的x,y∈Rn, 且x-y≥0, 必存在指標i, 使得xi>yi, 且有fi(x)≥fi(y), 則映射f稱為E0-映射,E0-映射也稱為半單調映射.

2 互補問題的變形凝聚同倫算法

H(x,x(0),μ)=Φ(x)-μx(0)=0,

(2)

其中

對于給定的x(0), 式(2)也記為

(3)

證明: 將x(0)視為變量, 將以x(0),x,μ為自變量的同倫方程記為Hx(0)(x,μ), 其Jacobi矩陣記為

證明: 若Γx(0)是一條無界曲線, 則存在點列{(x(k),μk)∈Γx(0)}, 使得‖(x(k),μk)‖→∞, 由同倫方程(2)可得

(4)

解式(4)得

由式(5)得

(6)

(7)

與條件1矛盾, 因此,Γx(0)是一條光滑的有界曲線.

證明: 由定理1和定理2易知Γx(0)為有界曲線. 由一維流形分類定理知,Γx(0)微分同胚于單位圓周或單位區間(0,1](證明與文獻[9]的定理2.1類似). 注意到

是非奇異的, 得Γx(0)不能微分同胚于單位圓周, 而只能微分同胚于單位區間. 記(x(*),μ*)為Γx(0)的極限點, 則只可能發生以下4種情形:

1)μ*∈[0,1], ‖(x(*)‖→∞;

2)μ*=1, ‖x(*)‖<∞;

3) ‖x(*)‖<∞,μ*∈(0,1), 且x(*)∈?Θμ*;

下面利用預估-校正算法對同倫方程(2)產生的路徑進行跟蹤, 從而得到非線性互補問題的解, 算法步驟與文獻[12]相同.

命題1若Γx(0)為光滑曲線, 則在初始點x(0)處的正方向η(0)滿足

證明: 由

得

(8)

其中

從而有

例1

經簡單計算易知f為E0-映射且顯然條件1成立. 計算結果列于表1.

表1 例1的計算結果

例2

表2 例2的計算結果

由表1和表2可見, 本文算法的計算速度和精度均優于文獻[12].

[1] ZHU De-tong, CAI Li. Affine Scaling Interior Trust-Region Method for Solving Generalized Complementarity Problems with Linear inequality Constraints [J]. Chinese Annals of Mathematics, 2010, 31A(1)： 13-34. (朱德通, 蔡力. 線性不等式約束的廣義非線性互補問題的仿射內點信賴域方法 [J]. 數學年刊, 2010, 31A(1)： 13-34.)

[2] Buhmiler S, Krejic N. A New Smoothing Quasi-Newton Method for Nonlinear Complementarity Problems [J]. Journal of Computational and Applied Mathematics, 2008, 211(2): 141-155.

[3] QU Biao, WANG Chang-yu, ZHANG Shu-xia. A Method for Solving Nonlinear Complementarity Problem and Its Convergence Properties [J]. Mathematica Numerical Sinica, 2006, 28(3): 247-258. (屈彪, 王長鈺, 張樹霞. 一種求解非線性互補問題的方法及其收斂性 [J]. 計算數學, 2006, 28(3): 247-258.)

[4] ZHAO Yun-bin, Isac G. Quasi-P*,P(τ,α,β)-Maps, Exceptional Family of Element and Complementarity Problems [J]. Journal Optimization Theory and Applications, 2000, 105(1): 213-231.

[5] Kojima M, Megiddo N, Mizuno M. A General Framework of Continuation Methods for Complementarity Problems [J]. Math of Oper Res, 1993, 18(4): 945-963.

[6] Kojima M, Megiddo N, Noma T. Homotopy Continuation Methods for Nonlinear Complementarity Problems [J]. Mathematics of Operations Research, 1991, 16(4): 754-774.

[7] 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.

[8] XU Qing, DANG Chang-yin. A New Homotopy Method for Solving Non-linear Complementarity Problems [J]. Optimization, 2008, 57(5): 681-689.

[9] DING Jun-di, YIN Hong-you. A New Homotopy Method for Nonlinear Comolementarity Problems [J]. Numericla Mathematics, A Journal of Chinese Universities: English Series, 2007, 16(2): 155-163.

[10] SONG Dai-cai, LIN Zheng-hua, LIU Guo-xin. Some Properties of the Aggregate Tunction [J]. Acta Scientiarum Naturalium Universitatis Jilinensis, 2000(2): 1-4. (宋岱才, 林正華, 劉國新. 凝聚函數的若干性質 [J]. 吉林大學自然科學學報, 2000(2): 1-4.)

[11] ZHAO Yun-bin, LI Duan. On a New Homotopy Continuation Trajectory for Nonlinear Complementarity Problems [J]. Mathematics of Operations Research, 2001, 26(1): 119-146.

[12] WANG Xiu-yu, JIANG Xing-wu, LIU Qing-huai. The Combined Homotopy Method for Nonlinear Complementarity Problems [J]. Acta Mathemxticae Applicatae Scinica, 2012, 29(2): 430-440. (王秀玉, 姜興武, 劉慶懷. 非線性互補問題的組合同倫算法 [J]. 應用數學學報, 2012, 29(2): 430-440.)