基于數(shù)值實驗的鄰近點算法收斂速度研究

王從徐

（滁州城市職業(yè)學院 教育系，安徽 滁州 239000）

0 引言

在數(shù)值計算中，往往需要考慮求解無約束優(yōu)化問題[1]：.如果使用迭代法求解此類問題，基本思想是先給定一個初始點，通過某種迭代規(guī)則產(chǎn)生一個迭代序列{xk}，使得如果該序列是收斂的，那么這個極限點就是問題的最小值[2].鄰近點算法是求解最優(yōu)化問題的迭代算法之一，特別適合求解具有特殊結(jié)構(gòu)的優(yōu)化問題[3].例如，在圖像處理中，問題規(guī)模（變量個數(shù)）往往在百萬以上，傳統(tǒng)算法基本無法處理，但如果使用鄰近點算法或與其緊密相關(guān)的迭代收縮閾值算法，可以快速有效地處理此類問題，而且輸出的結(jié)果精度較高[4，5]；在傳統(tǒng)壓縮感知問題中算法重構(gòu)質(zhì)量較差，時間復雜度大，通過引入閾值和正則化參數(shù)的鄰近點算法，逐步迭代恢復圖像信號，具有加快收斂速度和改善重構(gòu)質(zhì)量的效果[6].在實際應用中表明，鄰近點算法及其改進算法可以減少運算時間，加快收斂速度[7].本研究通過數(shù)值實驗研究和分析該算法在不同的參數(shù)設置、不同的實驗問題下收斂速度和計算時間的變化，獲得初步結(jié)論.

1 相關(guān)方法與原理概述

1.1 最優(yōu)化模型

最優(yōu)化問題，常見的數(shù)學規(guī)劃的數(shù)學模型為：

式中：f（x），hi（x）（i=1，…，l）以及gi（x）（i=1，…，m）都是定義在Rn上連續(xù)可微的多元實值函數(shù).記E={i：hi（x）=0}，I={i：gi（x）≥0}，若E∪I=?，稱之為無約束優(yōu)化問題，否則稱為約束優(yōu)化問題.其中f（x）稱為目標函數(shù)，hi（x），gi（x）稱為約束函數(shù).目標函數(shù)為二次函數(shù)而約束函數(shù)都是線性函數(shù)的優(yōu)化問題稱為二次規(guī)劃；而目標函數(shù)和約束函數(shù)都是線性函數(shù)的優(yōu)化問題稱為線性規(guī)劃.

1.2 鄰近點算法

其主要設計思路是在原目標函數(shù)上添加一個二次項[2]，鄰近點算法中添加的項叫做鄰近點（PPA）項，PPA 項可以取一般的范數(shù)，不一定要取歐式范數(shù)，在一定程度上可以降低難度.

1.3 鄰近點算法的收斂性分析

算法的收斂性是設計一個迭代算法的最起碼要求，關(guān)于收斂性，有局部收斂性和全局收斂性的概念[9，10].

定義1若算法只有當初始點x0充分接近極小點x*時，由算法產(chǎn)生的點列{xk}才收斂于x*，則稱該算法具有局部收斂性.若對于任意的初始點x0，由算法產(chǎn)生的點列{xk}都收斂于x*，則稱該算法具有全局收斂性.

算法的局部收斂速度是衡量一個算法好壞的重要指標，給出有關(guān)收斂速度的概念：設算法產(chǎn)生的點列{xk}收斂于極小點x*，且

若p=1 且0＜θ＜1，則稱該算法具有線性的收斂速度；若p=1 且θ=0，則稱該算法具有超線性收斂速度；若p=2且0＜θ＜∞，則稱該算法具有平方收斂速度；若p＞2 且0＜θ＜∞，則稱該算法具有p 階收斂速度.

2 數(shù)值實驗分析

2.1 鄰近點算法求解無約束二次規(guī)劃

二次規(guī)劃是指這種形式的優(yōu)化問題：

式中：H∈Rn×n為實對稱矩陣；x 為列向量.如果H 為半正定矩陣，則稱此規(guī)劃為凸二次規(guī)劃，否則為非凸二次規(guī)劃.對于非凸二次規(guī)劃，全局最優(yōu)解較難計算，所以只考慮凸二次規(guī)劃.

例1通過添加一個二次項，求解第k 個子問題.

在實際的計算中，xk+1可以通過求解線性方程組得到，根據(jù)已有的條件，其中r 的取值可能影響鄰近點算法的效率，分析r 的取值對整個算法的收斂性的影響.主要考慮在r 不同的取值情況下，算法的收斂速度的改變以及對收斂精度的影響.通過編制符合算法結(jié)構(gòu)的MATLAB 程序，然后對r 分別取0.1，0.5，1，1.5，2，分析r 的取值對算法的收斂速度以及誤差大小的影響.在維度為500，條件數(shù)隨機生成的情況下，MATLAB 計算的結(jié)果如表1 所示.

表1 維度為500 時計算結(jié)果

圖1 直觀地展示了r 取不同值時算法的收斂速度.從圖1 可以看出，當r=0.1 時算法的收斂速度最快，當r≤1 時，算法的收斂速度明顯下降，說明r 較大時會降低算法的收斂速度.另一方面，從計算的數(shù)據(jù)結(jié)果來看，當r=0.1 時，計算時間有著明顯的優(yōu)勢.綜上所述，當r 取值較小時，在目標函數(shù)為好條件時，即使r 取值較小，不能有效改善條件數(shù)，但是依然保證了較高的計算效率，可以以較快的運算速度得出結(jié)果；而當r 增加到1 時，運算的時間大大增加，而且收斂精度較低；當r 增加到2 時，運算時間和r=1 時基本相當，在相同步驟中收斂精度繼續(xù)下降.所以，在一定數(shù)量級之內(nèi)當r 增加時，雖然可以改善壞條件，但是不一定能改善算法的計算效率.

圖1 r 取值對收斂速度的影響

為了進一步研究r 取值的影響，設置不同的條件數(shù)以研究r 的取值與計算時間的關(guān)系.在維度為100 時，計算時間t 的結(jié)果與條件數(shù)、r 的關(guān)系見表2.在條件數(shù)不變的情況下，r 的變化會對計算時間造成較大的改變.比如當條件數(shù)＜107時，r 的增加會造成計算時間的增加，說明收斂速度變慢；但當條件數(shù)＞107時，r 的增加反而可以一定程度上減少計算時間，說明r 可能改善了條件數(shù)，從而提升了計算效率.

表2 條件數(shù)與r 的關(guān)系

在維度為100，條件數(shù)為108的情況下，r 分別取1，0.1，0.01，0.001，0.000 1，利用MATLAB進行計算，結(jié)果見圖2.

如圖2 所示，在有限的步數(shù)下，當條件數(shù)比較大的時候，對比不同的r 取值，r=0.001 的收斂速度超過了r=0.000 1 的收斂速度，說明r 的增加一定程度上可以改善條件數(shù)，提高計算效率，節(jié)約計算時間.另一個直觀的變化就是當r=0.1時，整個算法的收斂精度大幅下滑，最終的誤差大大高于r 取值較小時的結(jié)果，而且圖像趨于平滑，不再繼續(xù)收斂.在數(shù)值實驗中，常見的誤差主要有兩種，一種是觀測誤差和模型誤差，但是他們不屬于數(shù)值計算帶來的誤差，所以一般不做研究.另一種是數(shù)值計算中產(chǎn)生的誤差，主要有截斷誤差和舍入誤差.截斷誤差是指在計算機計算迭代算法的過程中，迭代計算不可能無限進行下去，當計算需要終止時，計算結(jié)果數(shù)值與理論值的差異.舍入誤差是指計算機在反復的計算過程中，因為存儲空間的限制，不得不放棄一部分精度，并且不斷地在計算過程中累積的誤差.根據(jù)之前的分析，當r 取值較大時，改善了目標函數(shù)的條件數(shù)，但是也會造成計算步驟增加，所以在計算迭代算法過程中截斷誤差和舍入誤差反復出現(xiàn)，并且在大量的計算步驟中逐漸累積，最終導致較大的誤差.而且當r 的取值與原來矩陣中的數(shù)不是處在同一數(shù)量級時，在矩陣的計算中可能出現(xiàn)大數(shù)吃小數(shù)的現(xiàn)象，而這是需要在算法的設計中盡量避免的.所以，在數(shù)值計算實驗的模型設計中，要考慮到相關(guān)的控制措施，避免誤差過大，才能使模型的應用范圍更廣，精度更高.

圖2 r 取值對算法收斂精度的影響

2.2 鄰近點算法求解基追蹤問題

考慮基追蹤降噪（BPDN）問題：

應用鄰近點算法的基本思路，添加一個鄰近點項，使得算法可以通過迭代法的方式，簡化原問題的難度，加快原問題的解決速度.例如求解0∈T（x）=?‖x‖1+β（x-xk），做相應變換得x，其解相當于對左端的xk做軟收縮，長度為，即

為了驗證步長對于算法收斂性的影響，所以利用MATLAB 來編制相關(guān)算法，來分析不同的步長在實際運算中的表現(xiàn)，將步長分別設置為2，1.5，1，0.5，0.1，其中步長與r 為倒數(shù)關(guān)系，在MATLAB 運算得到的結(jié)果如圖3 所示.

圖3 不同步長下算法收斂速度

從圖3 可以看到，當步長較小時，算法的收斂速度較慢，隨著步長的增加，算法的收斂速度不斷提高，這說明算法的收斂速度是與步長相關(guān)的.其中r 為步長的倒數(shù)，所以當r 減小時，算法的收斂速度提升.但是當將r 減小到一定值的時候，運算無法進行，說明r 的取值是有特定的取值范圍的，所以在理論分析中的想法得到了印證，即r＞βρ（A＇A）.但是在實際的應用中，已經(jīng)證明時，上述結(jié)論依然是成立的，這樣一來就大大放松了收斂條件，在實際運用中變得更加有效.

3 結(jié)論

通過對最優(yōu)模型定義與鄰近點算法的最優(yōu)化規(guī)則和收斂特性進行概述，利用MATLAB 軟件對求解無約束二次規(guī)劃優(yōu)化問題與使用迭代收縮閾值算法求解基追蹤問題進行收斂性能分析，得到結(jié)論如下：

1）在求解無約束二次規(guī)劃優(yōu)化問題中，在一定數(shù)量級之內(nèi)當r 增加時，雖然可以改善壞條件，但是不一定能改善算法的計算效率；

2）在求解無約束二次規(guī)劃優(yōu)化問題中，r 改善了目標函數(shù)的條件數(shù)，但是也會造成計算步驟的增加，所以在計算迭代算法過程中截斷誤差和舍入誤差反復出現(xiàn)；

3）在求解基追蹤問題中，步長較小時，算法的收斂速度較慢，隨著步長的增加，算法的收斂速度不斷提高，收斂速度與步長相關(guān).