周正勇,秦麗娜

(山西師范大學(xué)數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院,山西 臨汾041004)

1.引言

本文考慮如下無約束minimax問題:

其中分量函數(shù)fj:,復(fù)雜且二次連續(xù)可微,q較大.問題(1.1)是一類典型的不可微優(yōu)化問題,在數(shù)據(jù)擬合[1],工程設(shè)計(jì)[2],結(jié)構(gòu)優(yōu)化[3],資源配置[4],選址問題[5],電路設(shè)計(jì)[6]等領(lǐng)域有廣泛的應(yīng)用,此外,曲線擬合問題,L1和L∞逼近問題等均可等價(jià)轉(zhuǎn)化為該類問題.

由于問題(1.1)的非光滑性,光滑優(yōu)化的理論與算法不能直接用于求解該類問題.解該類問題的一類方法是將其等價(jià)轉(zhuǎn)化為如下光滑約束優(yōu)化問題:

進(jìn)而用求解一般光滑約束優(yōu)化問題的算法對(duì)(1.2)進(jìn)行求解.文[7]指出該類方法有兩個(gè)缺點(diǎn),首先,該問題中Lagrange函數(shù)的海森矩陣通常奇異;其次,目標(biāo)函數(shù)v可由αv替代,其中α是任意大于0的常數(shù),因而目標(biāo)函數(shù)可被任意尺度化,從而該問題病態(tài).另一類方法是非光滑優(yōu)化方法,如次梯度法,割平面法,捆集法等.但這類方法大多是基于非光滑凸問題建立的,其收斂性條件較強(qiáng).

解問題(1.1)的第三類方法是光滑化方法,該類方法通過構(gòu)造max函數(shù)的光滑逼近函數(shù)(一般采用凝聚函數(shù)[8]其中p >0為光滑化參數(shù)),將問題(1.1)轉(zhuǎn)化為一族帶光滑化參數(shù)的光滑無約束優(yōu)化問題:

當(dāng)p趨于∞時(shí),這族帶光滑化參數(shù)的優(yōu)化問題的穩(wěn)定點(diǎn)趨近于問題(1.1)的穩(wěn)定點(diǎn).由于問題(1.3)為光滑無約束優(yōu)化問題,因此可采用許多解光滑無約束優(yōu)化問題的算法對(duì)其進(jìn)行求解.

直接計(jì)算,凝聚函數(shù)的梯度及海森矩陣為:

其中

由于凝聚函數(shù)的梯度與所有分量函數(shù)的梯度相關(guān),海森矩陣與所有分量函數(shù)的梯度及海森矩陣相關(guān)且表達(dá)式較為復(fù)雜,因此,當(dāng)分量函數(shù)復(fù)雜且個(gè)數(shù)較多時(shí),凝聚函數(shù)的梯度及海森矩陣的計(jì)算量較大.為了改善這一問題,文[9]構(gòu)造了如下方程:

構(gòu)造了一種積極集策略的光滑化max函數(shù)αt(x):,該函數(shù)僅與函數(shù)值較大的分量函數(shù)相關(guān).文[9-10]均采用迭代策略計(jì)算αt(x)的函數(shù)值及與其相關(guān)的分量函數(shù)的指標(biāo)集,計(jì)算效率較低.

本文對(duì)文[9]中基于方程(1.4)及函數(shù)(1.5)構(gòu)造的積極集策略的光滑化max函數(shù),給出了指標(biāo)集的直接計(jì)算方法,利用該指標(biāo)集將方程(1.4)轉(zhuǎn)化為一般的三次多項(xiàng)式方程,根據(jù)該三次多項(xiàng)式方程根的性質(zhì)給出了αt(x)的一種穩(wěn)定計(jì)算策略.結(jié)合Armijo線搜索,負(fù)梯度和牛頓方向及光滑化參數(shù)的更新策略,給出了一種解含多個(gè)復(fù)雜分量函數(shù)無約束minimax問題的積極集光滑化算法,初步的數(shù)值實(shí)驗(yàn)表明了該算法的有效性.

本文用到的假設(shè)和引理.

假設(shè)1.1fj(x),j ∈Q,二次連續(xù)可微.

引理1.1[9]對(duì)任意的t >0,(1.5)式及方程(1.4)的解定義了一個(gè)二次連續(xù)可微的光滑化max函數(shù)αt(x),且αt(x)滿足

引理1.2[9]對(duì)任意的x ∈Rn,t>0,αt(x)僅與如下的指標(biāo)集相關(guān):

2.指標(biāo)集Qt(x)的直接計(jì)算方法

3.積極集光滑化max函數(shù)的穩(wěn)定計(jì)算策略

證由(3.4)及(3.5)式可得

4.積極集策略的光滑化算法及其收斂性

本節(jié)基于前兩節(jié)給出的積極集策略的光滑化max函數(shù)αt(x),結(jié)合文[11]中的Newton-Armijo算法,給出一種解含多個(gè)復(fù)雜分量函數(shù)無約束minimax問題的積極集策略的光滑化算法.

算法4.1

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

本節(jié)將文[11]中基于凝聚函數(shù)提出的第二種解無約束minimax問題的算法記為PRW2,其光滑化參數(shù)采用與算法4.1對(duì)應(yīng)的更新策略pk+1=pk/ω.本節(jié)選取了兩個(gè)梯度及海森矩陣較為復(fù)雜的半無限minimax問題,將其等距離離散化后得到兩類含多個(gè)復(fù)雜分量函數(shù)的無約束minimax問題,將算法4.1同算法PRW2進(jìn)行了數(shù)值比較.算法在MATLAB R2014a中編程實(shí)現(xiàn),在配置為INTEL(R) Core(TM) i5-6200U 2.30GHz,內(nèi)存為4.00GB的筆記本上運(yùn)行.數(shù)值結(jié)果表明,對(duì)含多個(gè)復(fù)雜分量函數(shù)的無約束minimax問題,算法4.1的穩(wěn)定性與計(jì)算效率均高于算法PRW2.

例5.1[12]

例5.2[12]

算法4.1的參數(shù)設(shè)置如下:

終止準(zhǔn)則為

相對(duì)應(yīng)的將算法PRW2 的終止準(zhǔn)則設(shè)為

例5.1及例5.2等距離離散化后分量函數(shù)的個(gè)數(shù)分別取2.5k1×105(k1=1,......,40)與2k2×103(k2=2,......,40).在算法PRW2中,當(dāng)計(jì)算機(jī)內(nèi)存溢出時(shí),算法停止.

圖5.1給出了例5.1及例5.2在不同離散程度下算法4.1與算法PRW2的總迭代時(shí)間.由圖可知,兩者的總迭代時(shí)間基本隨著分量函數(shù)個(gè)數(shù)的增加呈上升趨勢(shì),且算法4.1的總迭代時(shí)間均比算法PRW2的總迭代時(shí)間少.隨著分量函數(shù)個(gè)數(shù)的增加,算法4.1的總迭代時(shí)間增長(zhǎng)穩(wěn)定性較好,而算法PRW2穩(wěn)定性較差,例如在例5.2中,當(dāng)分量函數(shù)個(gè)數(shù)為1.2×104,3×104和3.2×104時(shí),算法PRW2的迭代次數(shù)分別為86,68和60,總迭代時(shí)間分別為3.80秒,6.37秒和5.53秒,而其它離散化問題的迭代次數(shù)介于4650到5489之間,總時(shí)間介于176.02秒到1029.10秒之間.

圖5.2給出了例5.1及例5.2在不同離散程度下算法4.1與算法PRW2的平均迭代時(shí)間.由圖可知,算法4.1的平均迭代時(shí)間均比算法PRW2的平均迭代時(shí)間少.算法4.1在例5.1中平均時(shí)間較高的離散問題有8個(gè),對(duì)應(yīng)分量函數(shù)的個(gè)數(shù)為6.5×106,6.75×106,7×106,7.25×106,7.5×106,7.75×106,8×106,8.25×106,分量函數(shù)賦值次數(shù)分別為39,40,41,43,56,48,57,54,梯度賦值次數(shù)分別為13,13,13,13,14,15,18,21,海森矩陣賦值次數(shù)及迭代次數(shù)分別為9,9,9,9,10,11,14,17,平均迭代時(shí)間分別為10.58秒,11.67秒,12.09秒,12.87秒,13.40秒,11.71秒,10.84秒,9.87秒,而其它離散化問題的分量函數(shù)賦值次數(shù)為41或42,梯度賦值次數(shù)為23或24,海森矩陣賦值次數(shù)及迭代次數(shù)為19,20或21,平均迭代時(shí)間介于3.10秒到7.04秒之間.此外,由圖5.1及5.2可知,當(dāng)例5.1及例5.2中分量函數(shù)的個(gè)數(shù)分別大于4×106和4×103時(shí),由于計(jì)算機(jī)內(nèi)存溢出,算法PRW2 失敗.

圖5.1 算法4.1與算法PRW2 總迭代時(shí)間

圖5.2 算法4.1與算法PRW2 平均迭代時(shí)間

圖5.3 算法4.1中相關(guān)分量函數(shù)的個(gè)數(shù)與q的平均比例

圖5.3給出了例5.1及例5.2在不同離散程度下算法4.1中相關(guān)分量函數(shù)的個(gè)數(shù)與q的平均比例.由圖可知,隨著分量函數(shù)個(gè)數(shù)的增多,相關(guān)分量函數(shù)的個(gè)數(shù)與q的平均比例總體呈遞減趨勢(shì),例5.1及例5.2在算法4.1的迭代中相關(guān)分量函數(shù)的個(gè)數(shù)平均比例不超過11%和3.5%.因此,當(dāng)分量函數(shù)較多且復(fù)雜時(shí),算法4.1僅需計(jì)算少部分分量函數(shù)的梯度及海森矩陣,而算法PRW2在每次迭代中均需計(jì)算所有分量函數(shù)的梯度及海森矩陣,因此,算法4.1的計(jì)算效率優(yōu)于算法PRW2.