王秀玉, 姜興武, 李 琳

(1. 長春工業(yè)大學(xué) 基礎(chǔ)科學(xué)學(xué)院, 長春 130012; 2. 吉林工商學(xué)院 基礎(chǔ)部, 長春 130062)

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

(1)

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

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

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

1 變形凝聚函數(shù)

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為常數(shù),φ(a,b)稱為變形凝聚函數(shù). 顯然有

φ(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),

因而有

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

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

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

2 互補(bǔ)問題的變形凝聚同倫算法

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

(2)

其中

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

(3)

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

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

(4)

解式(4)得

由式(5)得

(6)

(7)

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

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

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

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

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

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

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

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

證明: 由

得

(8)

其中

從而有

例1

經(jīng)簡單計(jì)算易知f為E0-映射且顯然條件1成立. 計(jì)算結(jié)果列于表1.

表1 例1的計(jì)算結(jié)果

例2

表2 例2的計(jì)算結(jié)果

由表1和表2可見, 本文算法的計(jì)算速度和精度均優(yōu)于文獻(xiàn)[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. (朱德通, 蔡力. 線性不等式約束的廣義非線性互補(bǔ)問題的仿射內(nèi)點(diǎn)信賴域方法 [J]. 數(shù)學(xué)年刊, 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. (屈彪, 王長鈺, 張樹霞. 一種求解非線性互補(bǔ)問題的方法及其收斂性 [J]. 計(jì)算數(shù)學(xué), 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. (宋岱才, 林正華, 劉國新. 凝聚函數(shù)的若干性質(zhì) [J]. 吉林大學(xué)自然科學(xué)學(xué)報(bào), 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. (王秀玉, 姜興武, 劉慶懷. 非線性互補(bǔ)問題的組合同倫算法 [J]. 應(yīng)用數(shù)學(xué)學(xué)報(bào), 2012, 29(2): 430-440.)