基于凸組合的列文伯格-馬夸爾特算法

王貴峰

(亳州職業(yè)技術(shù)學(xué)院，安徽 亳州 236800)

0 引 言

非光滑約束方程組問題在實(shí)際經(jīng)濟(jì)、工程領(lǐng)域中有著廣泛的應(yīng)用.如在經(jīng)濟(jì)學(xué)中供應(yīng)鏈問題、工程中最優(yōu)控制及交通平衡等非線性互補(bǔ)問題均可以通過一定的方法轉(zhuǎn)化非光滑約束方程組問題. 非精確列文伯格-馬夸爾特算法是一種有效的求解非光滑(連續(xù)可微)約束方程組的算法.在局部誤差界條件下，文獻(xiàn)[1-4]證明了非精確列文伯格-馬夸爾特算法超線性收斂.針對(duì)非光滑約束方程組的求解問題，文獻(xiàn)[5]給出一種精確光滑化列文伯格-馬夸爾特算法，該算法具有較好的計(jì)算效果.但是，由于該算法在求解約束方程組受初始點(diǎn)和單一形式的步長(zhǎng)影響的問題，本文采取凸組合技術(shù)(convex combination skill)，將L1范數(shù)和L2范數(shù)并聯(lián)使用，同時(shí)為了進(jìn)一步改善L-M算法的性能，對(duì)已有的步長(zhǎng)做出改進(jìn)，提出一種新的CMLM算法，該算法每步迭代中，可以根據(jù)實(shí)際情況調(diào)整步長(zhǎng)，并只需求解一個(gè)線性方程組.該算法全局收斂，并在局部誤差界條件下，局部二次收斂.實(shí)驗(yàn)數(shù)據(jù)表明，該算法具有良好的計(jì)算效果.

1 模型和光滑化函數(shù)

考慮非光滑約束方程組

F(x)=0s.t.x∈X，

(1)

其中X={x∈Rn|h(x)≤0}，F(xiàn):X→Rp和h:Rn→Rm均為局部L—連續(xù)函數(shù).

題(1)可等價(jià)轉(zhuǎn)化成如下無約束方程組

(2)

考慮下列方程組

(3)

有復(fù)合函數(shù)性質(zhì)知，H(·)在R+×Rn上局部L—連續(xù)且強(qiáng)半光滑.

z=(t,x)|‖(t,x)-(0,x*)‖≤b2,t≥0

，使得對(duì)任意z∈N((0,x*),b2)，有c1‖H(z)‖≥dist(z,Z*).

2 一個(gè)光滑化的列文伯格-馬夸爾特算法

β0=β(z0)∶=γmin
1,‖▽?duì)穤0‖2

(4)

和

(5)

可知，數(shù)列{βk}單調(diào)遞減，且對(duì)任意的z0∈R++×Rn，均有>β0.為了使tk>0恒成立，令.求下列方程的解

(6)

算法

步驟 2 如‖H(zk)‖≤10-6，則終止程序.否則，令αk=min{1,tk/|▽tΨ(zk)|}，并由(4)-(5)計(jì)算βk.

步驟5 如果‖H(zk)‖2>‖H(zk)‖，令δ=0.1+rand*0.1；否則，令δ=0.9+rand*0.1.

對(duì)于算法1，有如下定理.

定理1 對(duì)任何正整數(shù)k≥0，若tk∈R++滿足tk≥βk成立，則算法1產(chǎn)生的序列{zk=(tk,xk)}，且滿足tk∈R++和tk≥βk.

3 收斂性結(jié)果

本節(jié)將對(duì)算法1的收斂性進(jìn)行分析，設(shè)對(duì)任意正整數(shù)k，均有‖▽?duì)?zk)‖≠0.則算法1 產(chǎn)生無窮序列{zk}.下面給出算法1的收斂性.

現(xiàn)在，我們對(duì)算法1的局部收斂性質(zhì)進(jìn)行研究.設(shè)z*∈Z*是{zk}的一個(gè)聚點(diǎn).有以下定理：

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

我們用該算法解帶約束非線性互補(bǔ)問題以驗(yàn)證算法1的實(shí)用性.非線性互補(bǔ)問題的形式如：求x*∈X={x∈Rn|h(x)≤0}，使得x*≥0,P(x*)≥0,(x*)TP(x*)=0，其中P(x)和h(x)函數(shù)如以下各問題

我們采用 Matlab 2010b語言編寫該算法的程序，并在惠普臺(tái)式電腦(pentium(r) dual-core、3.19GHz、2G)上運(yùn)行程序.所有的數(shù)值試驗(yàn)結(jié)果見表1和表2.在表1中，“x0”表示迭代初始點(diǎn)，“x*”表示例題的解.表2給出了算法1在求解例題1-4的最后三步迭代中的相關(guān)數(shù)據(jù)，其中“‖H(zk)‖”表示‖H(z)‖在最后三次迭代點(diǎn)處的值，“‖xk-x*‖”表示算法最后三步產(chǎn)生的迭代點(diǎn)與原例題解的距離，表2中的“0”意義為算法所得到的解和原例題真解的距離低于計(jì)算機(jī)精度，從表2中可看出，該算法確實(shí)超線性(局部二次)收斂.

表1：例題1-4的數(shù)值試驗(yàn)結(jié)果

表2 ：?jiǎn)栴}1-4最后三步迭代的相關(guān)數(shù)據(jù)