田冬冬 許雨晴 劉 茜

(山東師范大學(xué)數(shù)學(xué)與統(tǒng)計(jì)學(xué)院，250358，濟(jì)南)

1 引 言

考慮非線性約束優(yōu)化問題：

(P) minf(x)，s.t.gi(x)≤0,i=1,…,m，hj(x)=0,j=m+1,…,l，x∈X,

其中f,gi:Rn→R,i=1,…,m,hj:Rn→R,j=m+1,…l是Lipschitz連續(xù)的，X是Rn上的非空閉集.

當(dāng)所有函數(shù)都光滑時(shí)，對于問題(P)的二階懲罰方法是一種非精確的懲罰方法，用來尋找一系列光滑罰問題的穩(wěn)定點(diǎn)：

當(dāng)取罰參數(shù)c趨于無窮大時(shí)，便可以得到原約束問題的穩(wěn)定點(diǎn).然而，當(dāng)罰參數(shù)c比較大的時(shí)候，罰問題有可能會產(chǎn)生病態(tài)，從而解決起來比較困難.增廣拉格朗日方法[1]是一種乘子方法，通過對懲罰函數(shù)添加拉格朗日乘子的估計(jì)構(gòu)成增廣拉格朗日函數(shù), 只需要懲罰參數(shù)充分大時(shí)，罰問題的穩(wěn)定點(diǎn)即為原問題的穩(wěn)定點(diǎn)，從而降低病態(tài)產(chǎn)生的可能性.在增廣拉格朗日函數(shù)的基礎(chǔ)上,后來又出現(xiàn)了非線性的增廣拉格朗日函數(shù)[2]、廣義增廣拉格朗日函數(shù)[3]等, 均為精確的罰函數(shù).

近幾年,對于實(shí)際問題更多的是要解決非光滑約束優(yōu)化問題[4-10], 例如在圖像恢復(fù)、信號重構(gòu)、最優(yōu)控制、隨機(jī)平衡問題及球面逼近等都需要求解非光滑約束優(yōu)化問題, 而光滑化方法是求解此類問題的一類最常用的方法. 光滑化方法通常會借助光滑化參數(shù)ρ→和罰參數(shù)c有界, 使之得到原非光滑約束優(yōu)化問題的最優(yōu)解.在文獻(xiàn)[11]中為尋找對于非光滑非凸約束優(yōu)化問題的穩(wěn)定點(diǎn)提出了光滑化增廣拉格朗日方法，證明了在罰參數(shù)有界的前提下，由算法迭代產(chǎn)生的任何聚點(diǎn)都將是穩(wěn)定點(diǎn).文獻(xiàn)[10]中所用的增廣函數(shù)是經(jīng)典的二次增廣拉格朗日函數(shù),是下述廣義增廣拉格朗日函數(shù)的一種特殊情況.

其中

(i1)φ:R→R是嚴(yán)格遞增的，在0點(diǎn)處是二階連續(xù)可微的，且

φ(0)=0,φ'(0)=1；

(i2)ψ:R×R→R對b是二階連續(xù)可微的，且有

很容易驗(yàn)證，許多函數(shù)滿足條件(i1)或者(i2)，例如[10]：

容易知道, 當(dāng)函數(shù)φ=φ1(t)=t, 函數(shù)ψ=ψ(a,b)=ab時(shí), 即為文獻(xiàn)[10]中給出的增廣拉格朗日函數(shù).

2 約束規(guī)格

定義1如果存在一個(gè)(正)乘子λ∈Rl,使得

定義2[11]若由

可推出

定義3令g:Rn→R是局部Lipschitz函數(shù)，已知ρ>0,gρ:Rn→R是一個(gè)連續(xù)可微函數(shù)，如果對于任意固定的x∈Rn，有

則稱{gρ:ρ>0}是函數(shù)g的一類光滑函數(shù)族.

則稱光滑函數(shù)族{gρ:ρ>0}滿足梯度一致性.

定義5已知{xk}為問題(P)的迭代序列，當(dāng)k→時(shí)，ρk→.令為序列{xk}的一個(gè)聚點(diǎn)，如果

(1)

(2)

有

λi=0，λj=0,

3 光滑化廣義增廣拉格朗日方法

在本節(jié)中, 提出一種光滑化廣義增廣拉格朗日算法,并運(yùn)用相關(guān)理論證明它的收斂性.

對于光滑參數(shù)ρ>0,用廣義增廣拉格朗日函數(shù)定義下面的光滑化廣義增廣拉格朗日函數(shù)：

對于每一個(gè)ρ>0,c>0,λ∈Rl,提出下述相應(yīng)罰問題：

在算法中, 定義下面的剩余函數(shù)

剩余函數(shù)主要是用來檢測不可行性和互補(bǔ)性.

下面將會給出一些相關(guān)的理論及其證明. 當(dāng)ρ→和罰參數(shù)c是有界時(shí), 算法產(chǎn)生的任何迭代點(diǎn)的序列都將收斂于問題(P)的一些穩(wěn)定點(diǎn). 另外, 定義5給出的拓展的弱無非零反常乘子約束規(guī)格保證了罰參數(shù)的有界性.

根據(jù)定義4給出的精確罰函數(shù)，對非光滑約束優(yōu)化問題提出下列光滑化廣義增廣拉格朗日算法.

第二步：計(jì)算dk=-令xk+1=xk+αkdk，其中αk=βlk,lk∈{0,1,2,…}是滿足下面不等式的最小數(shù)：

(3)

如果

||

(4)

令ρk+1=σρk，并運(yùn)行第三步；否則，令k=k+1，重復(fù)運(yùn)行第二步.

第三步：令

(5)

(6)

第四步：如果

(7)

返回第一步；否則，令ck=σk+1+ck,k=k+1，并返回第二步.

接下來需要證明算法的收斂性并給出相關(guān)的定理, 在此之前先引入下列引理1.

類似于文獻(xiàn)[11]中的引理，證明容易得到.

定理1假設(shè)算法1 不能在有限步終止, 令x*是序列{xk}的聚點(diǎn),{xk}是由算法1 產(chǎn)生的.如果{ck}有界, 則x*為問題(P)的穩(wěn)定點(diǎn).

(8)

令

計(jì)算可得

(9)

由引理1和(4)式，有

當(dāng)k→,時(shí)，對(9)式取極限，由梯度一致性有

(10)

對于某些i∈{1,…,m}，gi(x*)=0，則有φ'(gi(x*))=1，對(10)式進(jìn)行簡單整理可得

(11)

由ck的迭代規(guī)則，當(dāng)k→時(shí)，有ckεk→+.因此由的定義以及ψ:R×R→R對b是二階連續(xù)可微的, 而且條件(a)和(b)至少有一個(gè)成立,所以有.那么會存在序列和非零μ∈Rl,使得

(12)

(13)

從定理1中可得出, 對于某些i∈{1,…,m}，gi(x*)≠0，有μi=0；對于剩余的i∈{1,…,m}，gi(x*)=0，則有φ'(gi(x*))=1，對(13)式進(jìn)行簡單整理可得

(14)

下面證明

(15)

條件(14)和(15)與假設(shè)的拓展的弱無非零反常乘子約束規(guī)格成立是相矛盾的.

下面證μjhj(x*)≥0.因?yàn)楫?dāng)k→時(shí)，有ck→，所以對于充分大的有

因此

從定理1和定理2可得出下面的推論1.

推論1假設(shè)算法1不能在有限步終止,{xk}是由算法1產(chǎn)生的,如果拓展的弱無非零反常乘子約束規(guī)格在序列{xk}的任意一個(gè)聚點(diǎn)成立，則任一聚點(diǎn)都是問題(P)的穩(wěn)定點(diǎn).

4 求解半無限規(guī)劃問題的光滑化廣義增廣拉格朗日方法

在本節(jié)中,將應(yīng)用算法1求解半無限規(guī)劃問題, 問題的形式如下:

minf(x),

s.t.g(x,y)≤0,y∈Ω,

其中，x∈Rn是一個(gè)決策變量, Ω是R中一個(gè)緊致區(qū)間,f:Rn→R是關(guān)于x連續(xù)可微的函數(shù)，g:Rn×Ω是連續(xù)可微的.

minf(x),s.t.V(x)≤0.

因?yàn)橹岛瘮?shù)V(x)一般為非光滑函數(shù), 在文獻(xiàn)[13]中提出了下述積分熵函數(shù)來近似值函數(shù)V(x)：

當(dāng)z→x,ρ→+時(shí)，γρ(z)→V(x)，在文獻(xiàn)[13]中已經(jīng)給出了積分熵函數(shù)是值函數(shù)的光滑化函數(shù)以及其具有梯度一致性的相關(guān)證明.

對于任意給的ρ>0,c>0,λ∈R,定義廣義近似光滑化增廣拉格朗日函數(shù)

通過增廣拉格朗日算法1以及引理1、定理1和定理2,可以得到下面的收斂性定理3和定理4.

定理3假設(shè)算法1 不能在有限步終止, 令x*是序列{xk}的聚點(diǎn),{xk}是由算法1 產(chǎn)生的.如果{ck}有界, 則x*為上述半無限規(guī)劃問題的穩(wěn)定點(diǎn).

定理4假設(shè)算法1不能在有限步終止, {xk}是由算法1產(chǎn)生的,如果拓展的弱無非零反常乘子約束規(guī)格在序列{xk}的任意一個(gè)聚點(diǎn)成立， 則任一聚點(diǎn)都是上述半無限規(guī)劃問題的穩(wěn)定點(diǎn).

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

在本節(jié)中, 主要是通過兩個(gè)一般的非光滑約束問題來驗(yàn)證光滑化廣義增廣拉格朗日方法的有效性，另外將會驗(yàn)證光滑化廣義增廣拉格朗日方法對半無限規(guī)劃問題也是適用的.

接下來的實(shí)驗(yàn)中, 會用三種罰函數(shù)對算法1進(jìn)行檢驗(yàn)從而得到問題的穩(wěn)定點(diǎn)，其中

而對于半無限規(guī)劃問題, 則采用的是利用積分熵函數(shù)法進(jìn)行光滑化.

算例1[18]非光滑約束優(yōu)化問題為: 目標(biāo)函數(shù)為最小化非光滑Rosenbrock 函數(shù)以及約束函數(shù)為一個(gè)非光滑不等式約束與一個(gè)線性的等式約束，

下面開始對目標(biāo)函數(shù)及約束函數(shù)進(jìn)行光滑化：

在算例1的數(shù)值實(shí)驗(yàn)中,選擇的初始點(diǎn)為(x1,x2)=(0.3,0.2)，參數(shù)

另外ξ=5×10-4，ξ1=10-5.

終止準(zhǔn)則為

下述表1中給出的是三種不同罰函數(shù)下數(shù)值實(shí)驗(yàn)結(jié)果.

表1 數(shù)值實(shí)驗(yàn)結(jié)果

算例2[20]非光滑約束優(yōu)化問題為: 目標(biāo)函數(shù)為最小化非光滑Rosenbrock 函數(shù)以及約束函數(shù)為在變量的加權(quán)最大值上的不等式約束為

下面開始對目標(biāo)函數(shù)及約束函數(shù)進(jìn)行光滑化：

終止準(zhǔn)則為

下述表中給出的是三種不同罰函數(shù)下數(shù)值實(shí)驗(yàn)結(jié)果.

表2 數(shù)值實(shí)驗(yàn)結(jié)果

上述數(shù)值實(shí)驗(yàn)可以看出, 滿足設(shè)定條件的非光滑約束優(yōu)化問題的穩(wěn)定點(diǎn)可以通過提出的光滑化增廣拉格朗日方法進(jìn)行求解, 算法產(chǎn)生的迭代序列的聚點(diǎn)便是原問題的穩(wěn)定點(diǎn). 由此可驗(yàn)證算法1 是解決非光滑約束優(yōu)化問題的有效算法.

算例3[21]半無限規(guī)劃問題為: 目標(biāo)函數(shù)為最小化光滑函數(shù)以及約束函數(shù)為非光滑的不等式約束，

minf(x)=1.21exp(x1)+exp(x2)，

s.t.g(x,s)=s-exp(x1+x2)≤0,s∈[0,1]，

將目標(biāo)函數(shù)用值函數(shù)V(x)=max{g(x,s)}≤0代替，并利用積分熵函數(shù)γρ(x)對其進(jìn)行光滑化，因?yàn)榉e分熵函數(shù)是值函數(shù)的光滑化函數(shù)以及其具有梯度一致性, 從而得到光滑化函數(shù)

在算例3的數(shù)值實(shí)驗(yàn)中,選擇的初始點(diǎn)為(x1,x2)=(-1,1)，參數(shù)

另外ξ=10-5，ξ1=10-6.

終止準(zhǔn)則為

下述表中給出的是三種不同罰函數(shù)下數(shù)值實(shí)驗(yàn)結(jié)果.

表3 數(shù)值實(shí)驗(yàn)結(jié)果

上述數(shù)值實(shí)驗(yàn)可以看出, 滿足設(shè)定條件的半無限約束規(guī)劃問題的穩(wěn)定點(diǎn)可以通過提出的光滑化增廣拉格朗日方法進(jìn)行求解, 算法產(chǎn)生的迭代序列的聚點(diǎn)便是原半無限規(guī)劃問題的穩(wěn)定點(diǎn). 由此可驗(yàn)證算法1 也可以解決半無限規(guī)劃問題.