蘇珂，林雨萌，李小川

(河北大學(xué) 數(shù)學(xué)與信息科學(xué)學(xué)院，河北省機(jī)器學(xué)習(xí)與計(jì)算智能重點(diǎn)實(shí)驗(yàn)室，河北 保定 071002)

求解非線性不等式約束優(yōu)化問題的方法有很多[1-4].在這些方法中，通常使用罰函數(shù)或拉格朗日函數(shù)來檢驗(yàn)迭代的可行性.罰函數(shù)法就是通過求解若干個(gè)罰函數(shù)的極小值來得到約束優(yōu)化問題的極小點(diǎn)的方法.但是，罰函數(shù)的使用，特別是罰參數(shù)的選擇，存在著一些困難.進(jìn)而提出了濾子技巧[5]，之后濾子技巧被應(yīng)用于多種約束優(yōu)化問題[6-12]，但濾子方法仍不可避免地遇到了Maratos效應(yīng).Maratos效應(yīng)是指價(jià)值函數(shù)拒絕了一些在解決問題上取得良好結(jié)果的試探點(diǎn).為克服濾子方法的不足，Ulbrich[13]提出了一種以拉格朗日函數(shù)代替目標(biāo)函數(shù)作為接受準(zhǔn)則的新濾子方法.在此基礎(chǔ)上，Nie等[14]利用固定標(biāo)量將目標(biāo)函數(shù)和約束違反度函數(shù)相結(jié)合，作為新的目標(biāo)函數(shù)，但試探點(diǎn)的判別準(zhǔn)則不變.實(shí)際上，如果能夠?qū)Ξ?dāng)前試探點(diǎn)放松接受準(zhǔn)則，就可以在一定程度上避免Maratos效應(yīng)，同時(shí)降低計(jì)算成本.

基于上述思想和方法，本文提出了一類具有自適應(yīng)參數(shù)的極大極小問題的非單調(diào)濾子信賴域方法.與Ulbrich[13]提出的理論不同，本文在濾子中不使用拉格朗日函數(shù)，而是使用與文獻(xiàn)[14]相似的函數(shù).此外，與Nie[14]等所提出的判別準(zhǔn)則不同的是本文中的參數(shù)不是固定的，是可以改變的，這意味著判別準(zhǔn)則是根據(jù)參數(shù)的不同而更新的.為了避免試探點(diǎn)落入“山谷”，還在判定中加入了非單調(diào)技術(shù).與現(xiàn)有的序列二次規(guī)劃(SQP)-濾子方法不同，本文修正了二次子問題，使其總是可行的，從而避免了可行性恢復(fù)階段，并在一定程度上減少了計(jì)算量.在合理的假設(shè)下，該算法具有全局收斂性.

1 一種改進(jìn)的求解極小極大問題的靈活非單調(diào)濾子方法

考慮下面的極大極小最優(yōu)化問題

(1)

其中fj(j∈I={1,2,…，m})：Rn→R是Rn上連續(xù)可微的實(shí)值函數(shù).

顯然，目標(biāo)函數(shù)φ(x)是連續(xù)的，但不一定是可微的.式(1)等價(jià)于式(2).

mint

s.t.fj(x)-t≤0,j∈I={1,2,…,m},

(2)

其中(x,t)∈Rn+1，定義

C(x,t)=(f1(x)-t,f2(x)-t,…,fm(x)-t)T,

其雅可比矩陣為A(x,t).

定義指標(biāo)集如下：IA(x)={j:fj=φ(x),j∈I},IN(x)={j:fj<φ(x),j∈I}.

令

f(x)=(f1(x),f2(x),…,fm(x))T,e=(1,1,…,1)T∈Rm.

構(gòu)造對角矩陣F(x)=diag(f1(x),f2(x),…,fm(x)).

為了求解式(2)，通過以下二次問題(QP)求得搜索方向dk

(3)

其中Δk是信賴域半徑，Hk∈Rn×n是f(x)的二階近似Hesse陣.

定義約束違反度函數(shù)h(x,t)=‖C(x,t)+‖2,其中Cj(x,t)+=max{Cj(x,t),0,j∈I},C(x,t)+=(C1(x,t)+,C2(x,t)+,…,Cm(x,t)+)T.定義目標(biāo)函數(shù)p(x,t)=t，在當(dāng)前迭代點(diǎn)xk處，令pk=p(xk,tk)，hk=h(xk,tk)，Ck=C(xk,tk).

點(diǎn)對支配定義、濾子集定義和試探點(diǎn)被接受的定義均和文獻(xiàn)[9]中定義1、2、3相同.

在經(jīng)典的濾子方法中，可接受的點(diǎn)對位于(h,p)平面的左下角(圖1，區(qū)域I),被拒絕的點(diǎn)對位于(h,p)平面右上部分(圖1，區(qū)域II).

為了避免Maratos效應(yīng)，設(shè)在第k次迭代處的目標(biāo)函數(shù)為

l(xk,tk)=p(xk,tk)+δkh(xk,tk)=p(xk)+δk‖C(xk,tk)+‖2,

(4)

其中，對于j=1,2,…,m,Cj(xk,tk)+=max{Cj(xk,tk),0}，δk是第k次迭代時(shí)的一個(gè)自適應(yīng)參數(shù)，它可以根據(jù)當(dāng)前試探點(diǎn)的不同改進(jìn)而改變.設(shè)l(xk,tk)=lk，在傳統(tǒng)濾子方法中，式(4)中δk=0(圖2).圖2的右半部分有4個(gè)區(qū)域I、II、III、IV.在當(dāng)前迭代k處，若試探點(diǎn)對(hk,lk)進(jìn)入?yún)^(qū)域IV，根據(jù)接受準(zhǔn)則，拒絕該試探點(diǎn)對.若(hk,lk)進(jìn)入?yún)^(qū)域I、II或III，則調(diào)整參數(shù)δk.對于區(qū)域III，為了實(shí)施更嚴(yán)格的接受準(zhǔn)則，增加δk的取值，這將導(dǎo)致拒絕區(qū)域變大，接受區(qū)域變小(圖3).因此，δk的更新為

(5)

圖1 經(jīng)典濾子集示意Fig.1 Schematic diagram of classical filter set

圖2 含參數(shù)濾子集示意Fig.2 Schematic diagram of filter set with parameters

若(hk,lk)進(jìn)入?yún)^(qū)域II，則該算法進(jìn)行了很好的改進(jìn)，故放寬接受準(zhǔn)則，使接受域變大，即降低δk的值(圖4)，所以δk更新為

(6)

若(hk,lk)進(jìn)入?yún)^(qū)域I，則接受該點(diǎn)對，且lk增加，hk減小，δk不變.若(hk,lk)進(jìn)入?yún)^(qū)域IV，則該點(diǎn)對被拒絕，δk不變.

圖3 松弛濾子集示意Fig.3 Schematic diagram of relaxation filter set

圖4 嚴(yán)格濾子集示意Fig.4 Schematic diagram of strictly filter set

算法A的描述形式如下：

步驟0令0<Δ0<1,0<γ<β<1,0<λ≤1,0<γ0<γ1≤1<γ2,M≥1,μ>0,α1=α2=0.5，x0∈Rn,H0∈Rn×n是正定矩陣，初始區(qū)域半徑Δ0≥Δmin>0,F0={(μ,+∞)}.令k=0,m(k)=0 .

步驟1 求子問題QP得到(dk,zk)，如果‖dk‖=0終止.

步驟6 令Δk∈[γ0Δk,γ1Δk]，轉(zhuǎn)步驟1.

2 算法的收斂性

假設(shè)下面的條件是成立的.

假設(shè)1對于任給的點(diǎn)x0∈Rn，水平集L(x0)={x∈Rn:φ(x)≤φ(x0)}是緊集.

假設(shè)2任給的點(diǎn)x∈L(x0)，目標(biāo)函數(shù)梯度向量線性無關(guān).

假設(shè)3函數(shù)fj和約束函數(shù)Cj(j∈I)是二次連續(xù)可微的.

假設(shè)4對于所有的k,{(xk,tk)}位于Rn的有界閉凸子集S上.

假設(shè)5函數(shù)A:Rm×(n+1)→Rn+1在定義域上是一致有界的.

假設(shè)6序列矩陣{Hk}是一致有界的,即對于所有的k，MH>0，其中‖Hk‖≤MH.

對于所有的{(xk,tk)}∈S，根據(jù)上面的假設(shè)，存在一個(gè)約束Mf使得‖2fj(xk)‖≤Mf,j∈I.可以假設(shè)存在一個(gè)約束ν1、ν2，使得‖p(xk,tk)‖≤ν1,‖C(xk,tk)‖≤ν2，‖C(xk,tk)‖≤ν2，‖2C(xk,tk)‖≤ν2.問題(2)在點(diǎn)(x*,t*)的Karush-Kuhn-Tucker條件為

引理1假設(shè)(dk,zk)是SQP信賴域子問題(3)的解，則

1) 如果dk=0則zk=0;2) 如果dk≠0則zk<0.

證明:1)不失一般性，在式(3)中，根據(jù)算法A可知，因?yàn)?dk,zk)是SQP信賴域子問題(3)的解，所以存在乘子νk∈Rm和νk∈R，滿足

在建筑物受太陽輻射的各個(gè)外表面中，屋面是建筑物上部與外界直接接觸的重點(diǎn)部位，受輻射熱也是最多的，其保溫與隔熱對建筑節(jié)能具有重要意義。為達(dá)到節(jié)能目的，屋面上可設(shè)置架空層增加空氣的流動，蓄水屋面及設(shè)置屋頂綠化形成生態(tài)型屋面等。這樣不僅可以增加環(huán)境的美觀性，還可以改善建筑物屋面的熱工性能以達(dá)到節(jié)能的目的。屋面保溫材料的選用上不宜用密度大、導(dǎo)熱系數(shù)高的材料，這樣會導(dǎo)致屋面的重量和厚度過大，不利于結(jié)構(gòu)設(shè)計(jì)；同時(shí)也不宜選用吸水率較大的材料，防止保溫層吸水而降低保溫效果。

(Hk+νkE)dk+f(xk)νk=0,eTνk=1,

(F(xk)+diag(f1(xk)Tdk,…,fm(xk)Tdk)-(φ(xk)+zk)E)νk=0,uk(‖dk‖-Δk)=0,f(xk)Tdk-zke≤φ(xk)e-f(xk),‖dk‖≤Δk,νk≥0,uk≥0.

如果dk=0，可以得到zk≥0.

引理2假設(shè)1～6成立，且令(dk,zk)是子問題(3)的可行點(diǎn)，則

(7)

(8)

證明:對于所有的j∈I，使用Taylor展式可以得到

其中yk介于xk和xk+dk之間.因?yàn)閐k是可行的且‖2fj(yk)‖2≤dk，得到

|δk+1|<Δk，因此

則式(8)成立.

引理3在假設(shè)條件成立前提下，算法A是有效的.

證明:當(dāng)δk充分小時(shí)，證明濾子可以接受試探點(diǎn)(xk+1,tk+1)，考慮下面2種情況.

根據(jù)δk的更新和式(8)，可得

當(dāng)Δk→0時(shí)，得證.

證明:若算法A非有限終止，則有無限多個(gè)迭代點(diǎn)被濾子接受.根據(jù)濾子的定義，分2種情況證明：

1)因?yàn)閙(k+1)≤m(k)+1,有

(9)

當(dāng)n=k+1，分以下2種情況討論：

定理1設(shè){(xk,tk)}是由算法A生成的無窮序列，則存在{(xk,tk)}的聚點(diǎn)為式(2)的Karush-Kuhn-Tucker點(diǎn).

因此存在一個(gè)子集K，ν*∈Λ使得在K上，νk→ν*.稱序列{νk}收斂于ν*.

令I(lǐng)A(x)={j∶νk,j>0},對于任意的j∈IA(x),由引理1中證明可知

fj(xk)Tdk=φ(xk)+zk-fj(xk),

3 數(shù)值結(jié)果

算法參數(shù)設(shè)置如下：H0=E∈Rn×n,β=0.6,γ=0.1,Δ=0.5,α=α1=α2=0.45,η=η1=η2=0.25,程序用Matlab編寫.

解為x=(1.139 0,0.899 6)T,f1=f2=1.952 2.初始點(diǎn)是x0=(1,-1)T.

解為x=(1,1)T,f1=f2=f3=2.初始點(diǎn)是x0=(1,-1)T.

解為x=(0.453 3,-0.906 6)T,f1=f3=0.616 4.初始點(diǎn)是x0=(1,-2)T.

表1中，比較了本文的算法與文獻(xiàn)[16]的算法.NF和NG分別表示目標(biāo)函數(shù)f和梯度的計(jì)算次數(shù).IT 表示迭代次數(shù).此外，用“-”表示在文獻(xiàn)[16]中沒有給出的值，f*是最優(yōu)解.

表1中的結(jié)果表明，與文獻(xiàn)[16]中算法相比，本文的算法是有效的,3個(gè)問題的迭代次數(shù)令人滿意.

表1 文獻(xiàn)[16]中算法與算法A的數(shù)值結(jié)果比較

4 總結(jié)

在該方法中，試探點(diǎn)的接受準(zhǔn)則是靈活的，拒絕區(qū)域是根據(jù)以往試探點(diǎn)的不同表現(xiàn)而變化的，而在傳統(tǒng)的濾子方法中，濾子結(jié)構(gòu)中的元素是固定的.數(shù)值計(jì)算結(jié)果表明，與傳統(tǒng)方法和Matlab算法相比，新方法具有更好的計(jì)算效率和更小的計(jì)算量.此外，該方法中自適應(yīng)參數(shù)的使用和調(diào)整是平衡目標(biāo)函數(shù)和約束違反度函數(shù)值的一種很好的方法.