非線性互補(bǔ)問題的一個廣義模式搜索算法

[摘要]本文主要是給出了非線性互補(bǔ)問題的一個新解法。首先通過引入一個隱式的拉格朗日函數(shù)把非線性互補(bǔ)問題轉(zhuǎn)化為一個等價的無約束最優(yōu)化問題，然后用廣義模式搜索法來解決，并給出了此算法的收斂性。

[關(guān)鍵詞]廣義模式搜索 非線性互補(bǔ) 無約束最優(yōu)化 收斂性

一、引言

經(jīng)典的非線性互補(bǔ)問題NCP(F)的模型如下：

求解x∈Rn，使得x≥0，F(xiàn)(x)≥0，＜x，F(xiàn)(x)＞=0（1.1）

其中F∶Rn→Rn連續(xù)可微，＜#8226;，#8226;＞表示普通意義上的內(nèi)積。

假設(shè)問題（1.1）的解集S≠Φ，在F(﹒)是仿射函數(shù)的情況下，（1.1）就退化成了線性互補(bǔ)問題。

二、原始非線性互補(bǔ)問題的轉(zhuǎn)化

眾所周知，NCP(F)可以看作求下面這個隱式拉格朗日函數(shù)的最小值問題：

其中α＞1是一個參數(shù)，(﹒)+表示在 Rn+上的正交投影。

特別地，在 Rn上，Mα(x)是非負(fù)的，假設(shè)在問題NCP(F)的解處Mα(x)取值為0。這樣求解問題NCP(F)就可以轉(zhuǎn)化為求解下面的無約束最優(yōu)化問題：

可見若F(﹒)連續(xù)可微，則Mα(x)也是連續(xù)可微的。這里假設(shè)F(﹒)連續(xù)可微。

三、無約束最優(yōu)化問題的廣義模式搜索算法

1.搜索步和Poll步

在無約束最小化問題的模式搜索算法中的每一次迭代，都在一張網(wǎng)（下面所定義的Rn的一個離散集）上的有限個點處對目標(biāo)函數(shù)進(jìn)行估計，試圖產(chǎn)生一個迭代點，使得該點的目標(biāo)函數(shù)值比當(dāng)前解處對應(yīng)的目標(biāo)函數(shù)值更小。這個過程稱為搜索步。如果在搜索步失敗，就進(jìn)行Poll步，如果在這個過程中也沒有找到改進(jìn)的網(wǎng)點，則xk稱為一個網(wǎng)格局部最優(yōu)值。網(wǎng)格大小和迭代的更新規(guī)則見表3.1。首先給出[5]中的一些定義，當(dāng)前網(wǎng)格定義如下：

其中Δk∈R+是網(wǎng)格大小的參數(shù)，nD是個有限數(shù)，表示矩陣D的列數(shù)，矩陣D的列看成Rn中的向量構(gòu)成了Rn的一個正生成集。同時還要求D中的每個列向量都可以表示成一個可逆矩陣和一個整向量的乘積。Poll集以xk為中心，定義為Pk={xk+Δkd，d∈Dk}。（表示Dk的列選自D）是一個正生成矩陣。

假設(shè)3 .1 對d∈Dk都有βmin≤‖d‖≤βmax。

假設(shè)3.2 若min{Mα（xk+Δkd）｜d∈Dk}＜Mα(xk)，則必存在一個網(wǎng)格點xk+1，xk+1≠xk，使得Mα(xk+1)＜Mα(kx)，k=0，1，2，Λ.

算法3.1 設(shè)x0∈Rn，給定Δ0＞0.

a.計算Mα(xk)。

b.通過一種探測移動算法決定一個迭代點x+k.

c.計算ρk=Mα(xk)-Mα(x+k).

d.若ρk＞0，則令xk+1；否則，令xk+1=xk.

e.更新Dk和Δk.

2.參數(shù)更新規(guī)則

如果發(fā)現(xiàn)一個改進(jìn)的網(wǎng)點，即：Mα(xk+1)＜Mα(xk)，則令Δk+1=λkΔk，λk∈(1，+∞)；

否則，即：若xk是網(wǎng)格局部最優(yōu)值，則令Δk+1=θkΔk， θk∈(0，1).設(shè)，不依賴于.

引理3.1 對于k≥0，都存在一個rk∈Z，使得Δk=ιrkΔ0.

如[4]中所述，下述定理顯然成立。

定理3.1由算法3.1產(chǎn)生的每一個迭代點XN都可以寫成如下形式：

其中x0∈Rn是初始值，，α和β是互質(zhì)的自然數(shù)，ι如Δk的更新規(guī)則中定義，Δ0是步長控制參數(shù)的初始值，D如當(dāng)前網(wǎng)中定義。Zk∈Zn，k=0，Λ，N-1.

四、收斂結(jié)果

由算法3.1可以得到下面兩個關(guān)于收斂結(jié)果的定理。

定理4.1 設(shè)Mα（x）是Rn上的連續(xù)可微函數(shù)，Mα（x）在Rn上利普希茲連續(xù)，常數(shù)為L，水平集LMα(x)(x0)是緊集。則GPS算法3.1產(chǎn)生的迭代滿足

這個定理表明算法3.1產(chǎn)生的迭代序列至少有一個聚點是問題（1 .1）的穩(wěn)定點。如果把條件加強(qiáng)就會得到下面定理4.2中更強(qiáng)的收斂結(jié)果。

假設(shè)4.1: 1.對于每一個網(wǎng)點

定理4.2假設(shè)上面三個條件成立， Mα(x)是Rn上的連續(xù)可微函數(shù)，Mα（x）在Rn上利普希茲連續(xù)，常數(shù)為L，水平集LMa(x)(x0)是緊集。則GPS算法3.1產(chǎn)生的迭代滿足

參考文獻(xiàn)：

[1]Cottle，R.，Giannessi，F(xiàn).， and Lions，J.L.， Variational Inequalities and complementarity problems: Theory and Applications. Wiley. New York，New York，1980.

[2]Pang，J.s.， complementarity problems， Handbook of Global Optimization， Edited by R.Horst and P.pardalos. Kluwer Academic Publishers， Boston， Massachusetts， 1995.271-338.

[3]Cottle， R.，Pang，J.S.， and Stone，R.， The Linear Complementarity problem， Academic Press， New York， New York， 1992.

[4]V.Torczon，On the convergence of pattern search algorithms，SIAM J.Optim. 1997，（7）：1-25.

[5]T.G.Kolda，A.R.M.Lewis and V.Torczon，Optimization by direct search :a new perspectives on some classical and modern methods，SIAM REVIEW. 2003，（45）：，385-482.

（作者單位：天津科技大學(xué)理學(xué)院）