非光滑約束優(yōu)化的廣義增廣拉格朗日方法及其在半無限規(guī)劃中的應(yīng)用

田冬冬 許雨晴 劉 茜

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

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ù)都光滑時，對于問題(P)的二階懲罰方法是一種非精確的懲罰方法，用來尋找一系列光滑罰問題的穩(wěn)定點：

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

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

其中

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

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

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

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

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

2 約束規(guī)格

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

定義2[11]若由

可推出

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

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

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

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

(1)

(2)

有

λi=0，λj=0,

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

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

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

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

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

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

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

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

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

(3)

如果

||

(4)

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

第三步：令

(5)

(6)

第四步：如果

(7)

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

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

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

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

(8)

令

計算可得

(9)

由引理1和(4)式，有

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

(10)

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

(11)

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

(12)

(13)

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

(14)

下面證明

(15)

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

下面證μjhj(x*)≥0.因為當(dāng)k→時，有ck→，所以對于充分大的有

因此

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

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

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

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

minf(x),

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

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

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

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

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

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

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

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

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

5 數(shù)值實驗

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

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

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

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

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

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

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

終止準(zhǔn)則為

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

表1 數(shù)值實驗結(jié)果

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

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

終止準(zhǔn)則為

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

表2 數(shù)值實驗結(jié)果

上述數(shù)值實驗可以看出, 滿足設(shè)定條件的非光滑約束優(yōu)化問題的穩(wěn)定點可以通過提出的光滑化增廣拉格朗日方法進行求解, 算法產(chǎn)生的迭代序列的聚點便是原問題的穩(wě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)對其進行光滑化，因為積分熵函數(shù)是值函數(shù)的光滑化函數(shù)以及其具有梯度一致性, 從而得到光滑化函數(shù)

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

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

終止準(zhǔn)則為

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

表3 數(shù)值實驗結(jié)果

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