求解絕對值線性互補(bǔ)問題的一種廣義牛頓法

包麗平，楊丹丹

( 內(nèi)蒙古民族大學(xué) 數(shù)學(xué)學(xué)院，內(nèi)蒙古 通遼028043)

取n=10 絕對值互補(bǔ)問題(AVLCP(A，b))的矩陣A 如下:

線性互補(bǔ)問題首先是由著名運(yùn)籌學(xué)家、數(shù)學(xué)規(guī)劃的創(chuàng)始人Dentzig 和他的學(xué)生Cottle 于1963 年提出的．次年，Cottle 在他的博士論文中第一次提出了求解它的數(shù)學(xué)規(guī)劃算法．線性互補(bǔ)問題不僅優(yōu)化問題、二次規(guī)劃和約束優(yōu)化問題的最優(yōu)性條件(KKT 條件)之間有著緊密的聯(lián)系，并且已經(jīng)發(fā)展成為運(yùn)籌學(xué)的一個(gè)重要分支．它們已經(jīng)廣泛應(yīng)用于力學(xué)、交通、經(jīng)濟(jì)、金融、控制等領(lǐng)域，因此，線性互補(bǔ)問題的理論與算法研究一直是應(yīng)用數(shù)學(xué)和計(jì)算數(shù)學(xué)領(lǐng)域中的一個(gè)熱點(diǎn)問題［1－4］．隨著對線性互補(bǔ)問題這一領(lǐng)域研究的不斷深入，線性互補(bǔ)問題已經(jīng)做出許多推廣，例如:廣義線性互補(bǔ)問題、垂直線性互補(bǔ)問題、水平線性互補(bǔ)問題、隱互補(bǔ)問題等．近期，作為線性互補(bǔ)問題的一種新的推廣，Noor 等人［5］于2012 年定義并研究了絕對值線性互補(bǔ)問題(簡記作AVLCP(A，b))，其定義如下:

給定A∈Rn×n，b∈Rn，求x=(x1，x2，…，xn)∈Rn，使得:

其中|x|=(|x1|，|x2|，…，|xn|)∈Rn，K是閉凸錐，K*={x∈Rn|〈x，y〉≥0，y∈K}為K的極錐．

文獻(xiàn)［5］構(gòu)造了如下絕對值互補(bǔ)問題(1)的等價(jià)的絕對值變分不等式:

令K是內(nèi)積空間Rn閉凸錐，求x=(x1，x2，…，xn)∈Rn，使得:

絕對值線性互補(bǔ)問題還與絕對值方程密切相關(guān)．當(dāng)K=Rn時(shí)，AVLCP(A，b)等價(jià)于如下絕對值方程組:

許多學(xué)者對該方程組的求解進(jìn)行了深入的研究，其中Mangasarian 等人給出了凹函數(shù)極小化方法及牛頓法等，并且Mangasarian 還證明了絕對值方程組等價(jià)于經(jīng)典的線性互補(bǔ)問題．自此也有許多學(xué)者對絕對值方程組的存在性理論與求解算法進(jìn)行了探討，許多實(shí)際問題可抽象為絕對值線性互補(bǔ)模型，需要設(shè)計(jì)高效的算法求解絕對值線性互補(bǔ)問題．目前只有Noor 等人提出絕對值線性互補(bǔ)問題的廣義AOR 迭代法，并且算法的收斂速度是線性的．因此，建立絕對值線性互補(bǔ)問題的解存在性理論和設(shè)計(jì)有效求解絕對值線性互補(bǔ)問題的新型的收斂速度更快的算法具有重要的理論意義和實(shí)際價(jià)值．基于此，本文建立求解絕對值互補(bǔ)問題的新型有效算法．

1 主要結(jié)果

定理1 若A－Dx正定，設(shè)，當(dāng)時(shí)，x*是AVLCP(A，b)的解．

其中D'是向量λx+(1－λ)x*∈K，λ∈(0，1］所對應(yīng)的對角陣，其中D″是向量Z*所對應(yīng)的對角陣．當(dāng)λ→0+，D'→D″，整理得:

當(dāng)λ→0+，有:(x－x*)T［(A－D)x*－b］≥0，?x∈K，所以x*是AVLCP(A，b)的一個(gè)解．

2 廣義牛頓算法

設(shè)目標(biāo)函數(shù)f(x)梯度為g(x)、Hesse 陣為H(x)，則:

求解二次極小化問題的廣義牛頓法的迭代格式如下:

下面給出本文所建立的廣義牛頓算法:

step 1:初始點(diǎn)x0，精度要求ε＞0，置k=0;

step 2:計(jì)算xk+1=［A－Dxk］;

step 3:若D(xk+1)=D(xk)且‖Axk－Dxkxk－b‖＜ε 停止，得到解x*=xk;否則置k=k+1，轉(zhuǎn)step 2．

3 收斂性分析

由文獻(xiàn)［6］的引理6 得到結(jié)論對任意的初始點(diǎn)，序列xk

{ }線性收斂到AVLCP(A，b)的唯一解．

4 數(shù)值實(shí)驗(yàn)

本節(jié)中，將通過數(shù)值例子來說明本文所建立的算法的有效性．運(yùn)用Matlab7．5 進(jìn)行計(jì)算，運(yùn)行環(huán)境為:CPU 為Intel(R)Core(TM)2×2．70 GHz，內(nèi)存為2．0 GB．計(jì)算進(jìn)度為1．0e－6

例1［5］考慮常微分方程:

取n=10 絕對值互補(bǔ)問題(AVLCP(A，b))的矩陣A如下:

令初始矩陣D分別為

通過廣義牛頓法分別迭代一次和二次得到相同的近似解:

通過這個(gè)例子看到經(jīng)過簡單步就得到精確解的近似值．

5 結(jié)語

本文建立了在絕對值互補(bǔ)問題的矩陣奇A－Dx正定的條件下一個(gè)絕對值互補(bǔ)問題的在一定條件下轉(zhuǎn)化為求凸二次函數(shù)極小值問題，在此轉(zhuǎn)化下提出一個(gè)求解絕對值互補(bǔ)問題的廣義牛頓法，證明了算法的全局收斂性，本算法具有格式簡單，存儲(chǔ)量小，迭代次數(shù)少和易于在計(jì)算機(jī)上實(shí)現(xiàn)等優(yōu)點(diǎn)，為此本文給出的迭代法可以作為求解絕對值互補(bǔ)問題的一個(gè)有效算法．

［1］ 韓繼業(yè)，修乃華，戚厚鐸．非線性互補(bǔ)理論與算法［M］．上海:上?？茖W(xué)技術(shù)出版社，2006．

［2］ 袁亞湘，孫文瑜．最優(yōu)化理論與方法［M］．北京:科學(xué)出版社，1997．

［3］ Mangasarian O L．Absolute value equations［J］．Linear Algebra Appl，2006，419:259－267．

［4］ Sun D F，Womersley R S，Qi H D．A feasible semi－smooth asymptotically Newton method for mixed complementarity problems［J］．Math Program A，2002，94:167－187．

［5］ Noor M A，Iqbal J，Noor K I，et al．Generalized AOR method for solving absolute complementarity problems［J］．Journal of Applied Mathematics，2012，Article ID 743861，14 pages，2012．

［6］ Mangasarian O L．A generalized Newton method for absolute value equations［J］．Optimization Letters，2009，3(1):101－108．