一種嚴(yán)格成立的懲罰函數(shù)法及其求解

侯小秋

(黑龍江科技大學(xué) 電氣與控制工程學(xué)院， 哈爾濱 150022)

0 引 言

懲罰函數(shù)法求解約束最優(yōu)化問(wèn)題，將問(wèn)題的目標(biāo)函數(shù)與約束函數(shù)構(gòu)造增廣目標(biāo)函數(shù)，即懲罰函數(shù)，將約束最優(yōu)化問(wèn)題轉(zhuǎn)化為無(wú)約束最優(yōu)化問(wèn)題求解。根據(jù)懲罰函數(shù)構(gòu)造的思想不同，分為內(nèi)點(diǎn)懲罰函數(shù)法[1]、外點(diǎn)懲罰函數(shù)法[2]和混合懲罰函數(shù)法[3]，還可分為靜態(tài)懲罰函數(shù)法[4]、動(dòng)態(tài)懲罰函數(shù)法[4]、退火懲罰函數(shù)法[4]和自適應(yīng)懲罰函數(shù)法[4]。各種懲罰函數(shù)法都有自己的優(yōu)缺點(diǎn)。筆者分析一種外點(diǎn)懲罰函數(shù)法[2]解析解和數(shù)值解在可行域內(nèi)成立的條件，針對(duì)具有偏置量的外點(diǎn)懲罰函數(shù)法，同樣分析其數(shù)值解和解析解在可行域內(nèi)的條件，當(dāng)偏置量滿(mǎn)足允許誤差限的限制條件時(shí)，偏置量外點(diǎn)懲罰函數(shù)法具有嚴(yán)格成立性，提出一種高數(shù)值穩(wěn)定性的改進(jìn)DFP擬牛頓法，應(yīng)用文中求解偏置量外點(diǎn)懲罰函數(shù)法。

1 外點(diǎn)懲罰函數(shù)法

1.1 解析解

一般約束最優(yōu)化問(wèn)題為

式中：x——優(yōu)化變量；

f(x)——優(yōu)化函數(shù)；

gj(x)——等式約束；

cm(x)——不等式約束。

構(gòu)造懲罰函數(shù)[2]為

(1)

式中：F(…)——懲罰函數(shù)；

M(k)——懲罰因子，且有，0

式(1)的解析解x*為

(2)

由式(2)求得的x*，若

cm(x*)≤0,m=1,2,…,M。

(3)

(4)

則，解析解x*在可行域外，外點(diǎn)懲罰函數(shù)法解無(wú)效。

1.2 數(shù)值解

數(shù)值解可采用無(wú)約束最優(yōu)化的最速下降法和牛頓法及擬牛頓法等求解，當(dāng)

cm(xk+1)≤0,m=1,2,…,M，

(5)

式中：xk+1——k+1步數(shù)值解；

k+1——迭代步數(shù)。

(6)

則，數(shù)值解在可行域外，外點(diǎn)懲罰函數(shù)法解無(wú)效。

2 偏置量外點(diǎn)懲罰函數(shù)法

2.1 解析解

在文獻(xiàn)[2]的外點(diǎn)懲罰函數(shù)法的懲罰函數(shù)中加入偏置量，構(gòu)造懲罰函數(shù)為

(7)

μ——偏置量，μ>0。

針對(duì)式(7)求解可構(gòu)成偏置量外點(diǎn)懲罰函數(shù)法，由式(7)可得其解析解為

同樣，具有式(3)、(4)的解，在可行域內(nèi)或可行域外的問(wèn)題。

2.2 數(shù)值解

分析表明，其數(shù)值解形式與式(5)、(6)一致的結(jié)論。

2.3 偏置量外點(diǎn)懲罰函數(shù)法的嚴(yán)格成立

令

fm(x,μ)=cm(x)+μ。

(8)

選取終止條件為

f1(xk+1,μ),…,fM(xk+1,μ)‖p≤ε,

(9)

式中：ε——允許誤差限，ε>0適當(dāng)正數(shù)；

‖…‖p——范數(shù)，p=1或2。

則由式(9)得

-ε1/p≤fm(xk+1,μ)≤ε1/p。

(10)

將式(8)代入式(10)得

-ε1/p≤cm(xk+1)+μ≤ε1/p,

(11)

則由式(11)得

-ε1/p-μ≤cm(xk+1)≤ε1/p-μ,

選取

μ≥ε1/p，

(12)

則有

cm(xk+1)≤ε1/p-μ≤0。

(13)

滿(mǎn)足不等式(13)約束，偏置量外點(diǎn)懲罰函數(shù)法的嚴(yán)格成立。可采用無(wú)約束最優(yōu)化的最速下降法[5]、修正牛頓法[6]、共軛梯度法[7]和擬牛頓法[8]等算法求解,文中采用改進(jìn)的DFP擬牛頓法求解。

3 改進(jìn)的DFP擬牛頓法

3.1 改進(jìn)的DFP擬牛頓法的推導(dǎo)

文獻(xiàn)[9]的DFP擬牛頓法的迭代矩陣為

Hk+1=Hk+ΔHk,

(14)

式中：Hk——近似矩陣；

ΔHk——校正矩陣。

(15)

式中：Zk——近似解增量；

Yk——梯度增量。

且

Zk=xk-xk-1,

Yk=?f(xk)-?f(xk-1),

式中：f(…)——目標(biāo)函數(shù)；

?f(xk)——梯度。

Hk+1應(yīng)滿(mǎn)足的擬牛頓條件

Hk+1Yk=Zk,

(16)

將式(14)代入式(16)得

ΔHkYk=Zk-HkYk。

(17)

文獻(xiàn)[9]的DFP校正公式為

改進(jìn)為

(18)

式中：λ1——權(quán)重矩陣；

λ2——輔助矩陣。

式(18)右乘Yk得

(19)

比較式(19)和式(17)得

(20)

(21)

由式(21)得

(22)

可取

(23)

令

Uk=αk(Zk+δ1Yk),

(24)

Vk=βk(HkYk+δ2Yk),

(25)

式中：δ1——權(quán)重因子；

δ2——權(quán)重因子；

αk——加權(quán)因子；

βk——加權(quán)因子。

由式(24)代入式(20)得

(26)

由式(26)可得

由式(25)代入式(23)得

(27)

由式(27)得

由文獻(xiàn)[6]可知，

當(dāng)Yk不是零向量時(shí)，只要適當(dāng)選取δ1和δ2，即可使αk和βk的分母不趨于零，提高了算法的數(shù)值穩(wěn)定性。

式(24)、(25)、(22)代入式(18)，再代入式(14)、(15)得

(28)

由式(28)可知，Hk+1不對(duì)稱(chēng)，要使改進(jìn)的DFP擬牛頓法有效，需保證Hk+1廣義正定，由文獻(xiàn)[11]的引理2，若Hk+1廣義正定，其對(duì)稱(chēng)分量

正定。

式中：n——SA的維數(shù)；

SA(i,j)——SA的元素。

式中，b——適當(dāng)?shù)恼龜?shù)。

下面討論式(28)的2個(gè)簡(jiǎn)化算法。

算法1

λ2=λ3Hk,

式中，λ3——對(duì)角矩陣。

算法2

δ1=δ2=0,

λ2=λ4Hk,

式中，λ4——加權(quán)因子。

則，式(28)退化為

(29)

下面證明式(29)的算法，因引入加權(quán)因子λ4，可提高算法的數(shù)值穩(wěn)定性。此時(shí)，Hk+1對(duì)稱(chēng)，引入Hk=QTQ，Q非奇異矩陣，代入式(29)得，?Y∈Rn，且Y≠0，有

YTHk+1Y=YTHkY(1+λ4)+

記QY=w,QYk=q，則

(30)

選取λ4>0，則式(30)的第二項(xiàng)與文獻(xiàn)[13]的證明擴(kuò)大1+λ4倍，加強(qiáng)了算法的數(shù)值穩(wěn)定性。

3.2 改進(jìn)的DFP擬牛頓法求解

由式(7)可得

(31)

則

(32)

式(31)、(32)代入式(28)求解

4 算例的數(shù)值分析

待優(yōu)化問(wèn)題

s.t.g1(x)=x2+x4-x5-1=0，

g2(x)=x1+x2+x3+x4+x5-2=0，

g3(x)=2x1-0.5x3+x4-x5-1.5=0，

初始化x1(0)=0.5，x2(0)=0.4，x3(0)=0.1，x4(0)=0.15，x5(0)=0.1。選取ε=1M(k)=2×1.1k，H0=I，λ2=diag[2,3,4,3,2]。

采用Matlab軟件編程實(shí)現(xiàn)數(shù)值分析，選取μ=ε1/2=1，嚴(yán)格成立的具有偏置量的懲罰函數(shù)法的優(yōu)化過(guò)程如表1所示。由表1可知，在優(yōu)化步驟k=3時(shí)，得優(yōu)化解，且c1(x3)=-1.270 9<0，不等式約束滿(mǎn)足，其最優(yōu)解合理有效。選取μ=0.1，具有偏置量的懲罰函數(shù)法的優(yōu)化過(guò)程如表2所示。

表1 嚴(yán)格成立的具有偏置量懲罰函數(shù)法的優(yōu)化過(guò)程

表2 具有偏置量的懲罰函數(shù)法的優(yōu)化過(guò)程

由表2可知，在優(yōu)化步驟k=4時(shí)停止優(yōu)化，此時(shí)，c1(x4)=0.111 6>0，不等式約束不滿(mǎn)足，其最優(yōu)解也是不合理的無(wú)效。

5 結(jié) 論

(1)理論分析表明，外點(diǎn)懲罰函數(shù)法和具有偏置量的外點(diǎn)懲罰函數(shù)法其解析解和數(shù)值解有時(shí)不滿(mǎn)足不等式約束。當(dāng)偏置量和允許誤差限滿(mǎn)足式(12)時(shí)，具有偏置量的外點(diǎn)懲罰函數(shù)法得數(shù)值解滿(mǎn)足不等式約束，嚴(yán)格成立。

(2)在DFP擬牛頓法的校正公式中引入輔助矩陣和權(quán)重矩陣，獲得了改進(jìn)的DFP擬牛頓法，式(24)、(25)對(duì)Uk和VK進(jìn)行改進(jìn)，使αk和βk的分母中引入了δ1‖Yk‖2和δ2‖Yk‖2項(xiàng)，合理地選取δ1和δ2，可使αk和βk的分母不趨于零，提高了算法的數(shù)值穩(wěn)定性。給出了改進(jìn)后DFP擬牛頓法的兩個(gè)簡(jiǎn)化算法，其簡(jiǎn)化算法2具有提高算法數(shù)值穩(wěn)定性的性能。