絕對(duì)值方程的非單調(diào)光滑算法

董 麗

(信陽師范學(xué)院 數(shù)學(xué)與統(tǒng)計(jì)學(xué)院, 河南 信陽 464000)

0 引言

考慮絕對(duì)值方程(AVE):

Ax+B|x|=b,

(1)

其中:A∈Rn×n,B∈Rn×n,B≠0,b∈Rn,|x|表示對(duì)x的各個(gè)分量取絕對(duì)值.絕對(duì)值方程(1)由Rohn提出[1].許多優(yōu)化問題,比如線性互補(bǔ)問題、線性規(guī)劃問題、凸二次規(guī)劃問題等,都可以轉(zhuǎn)化成絕對(duì)值方程(1)進(jìn)行求解[2].因此,絕對(duì)值方程(1)具有重要的研究意義.

目前,求解絕對(duì)值方程的算法主要針對(duì)如下形式的絕對(duì)值方程:

Ax-|x|=b.

(2)

文獻(xiàn)[3]給出了一個(gè)求解AVE(2)的Levenberg-Marquard方法，討論了算法的收斂性質(zhì).文獻(xiàn)[4]給出了求解AVE(2)的一個(gè)松弛非線性PHSS型迭代方法，證明了算法的收斂性.文獻(xiàn)[5]給出了求解AVE(2)的一個(gè)混合算法,在適當(dāng)條件下證明了算法有限步終止.光滑牛頓法是近年來求解優(yōu)化問題的一類新方法[6,7].最近,文獻(xiàn)[8]提出了一個(gè)求解AVE(1)的光滑牛頓法,在假設(shè)條件矩陣A最小的奇異值嚴(yán)格大于矩陣B最大的奇異值下,證明了算法具有全局和局部二次收斂性質(zhì).

本文給出了一個(gè)求解AVE(1)的非單調(diào)光滑算法,在文獻(xiàn)[8]假設(shè)條件下證明了算法具有全局和局部二次收斂性質(zhì).與文獻(xiàn)[8]中的光滑算法相比,本文算法采用一種新的非單調(diào)線性搜索技術(shù),其包含文獻(xiàn)[8]所采用的單調(diào)線性搜索以及文獻(xiàn)[9,10]所研究的非單調(diào)線性搜索.

1 算法設(shè)計(jì)

對(duì)任意的(μ,x)∈R1+n,定義H:R1+n→R1+n如下:

(i)H(μ,x)=0當(dāng)且僅當(dāng)x為(1)的解.

(ii)H(μ,x)在R1+n{(0,0)}上連續(xù)可微,其雅克比矩陣為

這里

(iii)H在R1+n上強(qiáng)半光滑.

為建立算法,本文采用文獻(xiàn)[8]中的假設(shè)條件.

假設(shè)1 矩陣A最小的奇異值嚴(yán)格大于矩陣B最大的奇異值.

在假設(shè)1下,下面結(jié)論成立,其證明見文獻(xiàn)[8]中的推論2.3.

引理1 如果假設(shè)1成立,則對(duì)任意的b∈Rn,絕對(duì)值方程(1)唯一可解.

為簡(jiǎn)單,記z=(μ,x)∈R1+n,并定義價(jià)值函數(shù)f(z)=‖H(z)‖2.下面給出算法.

算法(A)(一個(gè)非單調(diào)光滑算法)

(C1) 對(duì)任意的k≥0有ξk≥1;

令k=0.

步驟1 若‖H(zk)‖=0,則停止迭代.否則,計(jì)算

(3)

步驟2 通過求解方程組

(4)

得搜索方向Δzk=(Δμk,Δxk)∈R×Rn.

步驟3 令αk為1,λ,λ2,…中使得下式成立的最大值

f(zk+αkΔzk)≤[1-2σ(1-γ)αk]Λk.

(5)

步驟4 令zk+1=zk+αkΔzk.令

(6)

令k=k+1.轉(zhuǎn)步驟1.

注在步驟0中,需要選取數(shù)列{ξk}?R++滿足條件(C1)和(C2).事實(shí)上,有很多數(shù)列滿足上述要求,比如

(i)ξk=ξ,其中ξ≥1為常數(shù);

?如果選取ξk=1,則對(duì)任意的k≥0有Λk=f(zk).在這種情況下,步驟3即為傳統(tǒng)的單調(diào)線性搜索[8].

?如果選取ξk=ξ,其中ξ≥1為常數(shù),則步驟3即為文獻(xiàn)[9]所討論的非單調(diào)線性搜索.

?文獻(xiàn)[10]提出了一種非單調(diào)線搜索準(zhǔn)則,其定義如下:令ξ0=1,選取ηmin和ηmax使得0≤ηmin<ηmax<1,并選取ηk∈[ηmin,ηmax].然后,令

ξk+1=ηkξk+1,

為證明算法(A)有好的定義,需要如下兩個(gè)引理,其中引理2的證明見文獻(xiàn)[8]中的定理3.2.

引理2 如果假設(shè)1成立,則對(duì)任意的μ>0有H′(z)可逆.

引理3 假設(shè){Λk}和{zk}由算法(A)產(chǎn)生,則下列結(jié)論成立：

(i){Λk}單調(diào)下降有下界,因此收斂.

(iii)對(duì)任意的k≥0有f(zk)≤Λk.

證明由步驟3和步驟4可知

(7)

(8)

在不等式(8)兩邊同時(shí)取極限可得

進(jìn)而再由Λ*>0可知

f(zk+1)=ξk+1Λk+1-(ξk+1-1)Λk≤

ξk+1Λk+1-(ξk+1-1)Λk+1=Λk+1,

其中不等式利用了結(jié)論(i)以及ξk≥1.注意到Λ0=f(z0).因此,結(jié)論(iii)成立.證畢.

定理1 如果假設(shè)1成立,則算法(A)有好的定義,并產(chǎn)生無窮點(diǎn)列{zk=(μk,xk)}.此外,對(duì)任意的k≥0都有μk>0.

證明假設(shè)對(duì)于某個(gè)k有μk>0,比如k=0.由引理2可知矩陣H′(zk)非奇異,故步驟2在第k次迭代有好的定義.對(duì)任意的α∈(0,1],定義

Fk(α)=f(zk+αΔzk)-f(zk)-αf′(zk)Δzk.

(9)

因?yàn)閒在任意的z∈R++×Rn處連續(xù)可微,故由式(9)可知Fk(α)=o(α).由ωk的定義可知

ωk≤γmin{1,f(zk)}=

γmin{1,‖H(zk)‖2}≤γ‖H(zk)‖.

(10)

因此,由式(4),(9)和(10)可知,對(duì)任意的α∈(0,1]有

f(zk+αΔzk)=f(zk)+αf′(zk)Δzk+Fk(α)=

f(zk)+2αHT(zk)H′(zk)Δzk+o(α)=

(1-2α)f(zk)+2α‖H(zk)‖ωk+o(α)≤

(1-2α)f(zk)+2αγf(zk)+o(α)≤

[1-2(1-γ)α]f(zk)+o(α).

f(zk+αΔzk)≤[1-2σ(1-γ)α]f(zk)≤

[1-2σ(1-γ)α]Λk.

這里第2個(gè)不等式利用了引理3(iii).因此,步驟3在第k次迭代時(shí)有好的定義,并產(chǎn)生步長αk∈(0,1].由式(4)可知Δμk=-μk+ωk,故

μk+1=μk+αkΔμk=(1-αk)μk+αkωk>0.

(11)

因此,由μ0>0以及上面的證明過程可知算法(A)有好的定義,并產(chǎn)生無窮點(diǎn)列{zk=(μk,xk)}.此外,對(duì)任意的k≥0都有μk>0.證畢.

2 算法收斂性分析

本節(jié)分析算法(A)的收斂性質(zhì).為此,需要如下引理.

引理4 設(shè){zk=(μk,xk)}為算法(A)產(chǎn)生的迭代點(diǎn)列,則對(duì)任意的k≥0有μk≥ωk和μk≥μk+1.

證明由步驟0和式(3)可知μ0≥γ≥ω0,并且{ωk}單調(diào)下降.假設(shè)對(duì)于某個(gè)k有μk≥ωk.由式(11)可知

μk+1≥(1-αk)ωk+αkωk=ωk≥ωk+1,

故由數(shù)學(xué)歸納法可知對(duì)任意的k≥0有μk≥ωk.進(jìn)一步,由式(11)可知，對(duì)任意的k≥0,有μk+1≤(1-αk)μk+αkμk=μk.證畢.

定理2 如果假設(shè)1成立,則算法(A)產(chǎn)生的迭代點(diǎn)列{zk=(μk,xk)}有如下兩個(gè)性質(zhì):

(i){zk}有界;

(ii){zk}的任意聚點(diǎn)z*=(μ*,x*)都滿足方程H(z)=0.

下面假設(shè)ω*>0.因?yàn)閧ωk}單調(diào)下降,故由引理4可知

μk≥ωk≥ω*>0.

(12)

此外,由引理3可得

(13)

由式(12)和式(13)可知

Λ*≥f(z*)≥(μ*)2≥(ω*)2>0.

因此

(14)

因?yàn)棣?≥ω*>0,故f(z)在z*處連續(xù)可微.此外,由引理2可知H′(zk)可逆,故由式(4)可知{Δzk}k∈I收斂,記

利用式(10),在不等式(14)兩邊同時(shí)取極限可得

-2σ(1-γ)f(z*)≤2HT(z*)H′(z*)Δz*=

2[-f(z*)+‖H(z*)‖ω*]≤

2[-f(z*)+‖H(z*)‖ω*]≤

-2(1-γ)f(z*).

由式(6)可知

令kn→,則有

設(shè)z*為{zk}的任意聚點(diǎn),則由文獻(xiàn)[8]中的引理4.3可知,所有的V∈?H(z*)都是非奇異的.利用這個(gè)結(jié)論,類似于文獻(xiàn)[11]中定理5.3的證明過程,我們可以得到算法(A)的局部收斂性質(zhì).

定理3 設(shè){zk}為算法(A)產(chǎn)生的迭代點(diǎn)列,并且z*為{zk}的任意聚點(diǎn),則{zk}收斂到z*.此外,當(dāng)k充分大時(shí)有‖zk+1-z*‖=O(‖zk-z*‖2).

3 數(shù)值試驗(yàn)

為檢驗(yàn)算法(A)的實(shí)際計(jì)算效果,本節(jié)用MATLAB R2012b編程,在Intel(R) Core(TM) i7-790 CPU 3.60 GHz, 8.00 GB內(nèi)存, Windows XP操作系統(tǒng)的電腦上做數(shù)值試驗(yàn).利用算法(A)去求解AVE(2).在測(cè)試過程中,初始點(diǎn)選為x0=rand(n,1),參數(shù)選為μ0=10-2,σ=0.2,λ=0.8,γ=10-3,ξk=1/2k+10,終止準(zhǔn)則為‖Axk-|x|-b‖≤10-8.

問題1 選取A∈Rn×n,其對(duì)角線上的元素為500,而非對(duì)角線上的元素在區(qū)間[1,2]上任意選取.然后令b=(A-I)e,這里I為單位矩陣,e=(1,…,1)T.易知,問題1有精確解x=(1,…,1)T.首先我們利用算法(A)求解1次問題1,圖1顯示了算法(A)的收斂性,其中橫軸為迭代次數(shù)k,縱軸為lg(‖Axk-|xk|-b‖).然后,利用算法(A)求解10次問題1.數(shù)值結(jié)果列于表1,其中MIT表示求解10次問題1所需迭代次數(shù)的最小值,AIT表示求解10次問題1所需迭代次數(shù)的平均值,ACPU表示求解10次問題1所需的CUP時(shí)間(單位：s),AV表示求解10次問題1的‖Axk-|xk|-b‖的平均值.

圖1 算法(A)求解1次問題1(n=1000)時(shí)的收斂性Fig. 1 Convergence of algorithm (A) for solving one problem 1 (n=1000)

nMITAITACPU/sAV 100066.00.384.1827E-011200066.02.451.5341E-010300066.06.843.6166E-010400066.014.486.0066E-010500066.026.158.3216E-010

問題2 選取A∈Rn×n,其中

aii=4n,ai,i+1=ai+1,i=n,aij=0.5,i=1,2,…,n.

然后令b=(A-I)e.易知,問題2有精確解x=(1,…,1)T.同樣利用算法(A)求解10次問題2.數(shù)值結(jié)果列于表2.

表2 算法(A)求解問題2的結(jié)果Tab. 2 Numerical results of algorithm (A) for problem 2