約束Minimax問題的無罰函數(shù)無濾子的SQP算法

姜合峰,高娟,王福勝

(太原師范學(xué)院 數(shù)學(xué)系,山西 晉中 030619)

約束Minimax問題的無罰函數(shù)無濾子的SQP算法

姜合峰,高娟,王福勝

(太原師范學(xué)院 數(shù)學(xué)系,山西 晉中 030619)

文章提出了一種求解帶等式與不等式約束的minimax問題的既無罰函數(shù)又無濾子的SQP算法。首先引入了ε-積極約束集,在此基礎(chǔ)上建立了兩個(gè)新的二次規(guī)劃子問題得到搜索方向,既克服了Maratos效應(yīng),又大大地減少了算法的運(yùn)算量;另外給出了一種新的線性搜索步長策略,該方法既避免了罰因子的選取,又減小了計(jì)算機(jī)儲(chǔ)存量;在適當(dāng)?shù)募僭O(shè)條件下,證明了算法的全局收斂性;初步數(shù)值實(shí)驗(yàn)驗(yàn)證了算法的有效性與優(yōu)越性。

約束極大極小問題;SQP算法;積極約束集;全局收斂性

0 引言

極大極小問題是一類極其重要和應(yīng)用廣泛的優(yōu)化問題,它不僅是一類特殊的非線性規(guī)劃問題,而且是一類特殊形式的非光滑優(yōu)化問題。在工農(nóng)業(yè)、國防、化工、能源、通信、金融、經(jīng)濟(jì)管理等領(lǐng)域中,大量的現(xiàn)實(shí)問題都能轉(zhuǎn)化成極大極小問題模型,通過求解極大極小問題的最優(yōu)解從而解決了原實(shí)際問題。

本文考慮如下一般約束極大極小問題:

(1)

其中F(x)=max(fi(x)),i∈I,I={1,2,…,m},J={1,2,…,m′},E={1,2,…,l},并且fi(i∈I),gi(i∈J)和hi(i∈E)∶Rn→R都是二階連續(xù)可微的函數(shù)。目前求解非線性優(yōu)化問題(1)的算法很多,例如次梯度方法,捆綁法,切平面法,凝聚函數(shù)法,光滑函數(shù)正則極大項(xiàng)的技巧,梯度投影法,罰函數(shù)法,序列二次規(guī)劃法(SQP),信賴域法[1-5]等。Fletcher和Leyffer[6]于2002年提出了“Filter”技術(shù)用來求解非線性規(guī)劃問題。由于濾子方法具有良好的數(shù)值結(jié)果,因此,可以采用濾子技巧與SQP算法相結(jié)合求解約束極大極小問題,例如文獻(xiàn)[8-10]構(gòu)造了求解等式約束優(yōu)化問題。

基于文獻(xiàn)[10]的思想,本文在文獻(xiàn)[7]的基礎(chǔ)上,增加約束條件,并借助于ε-積極約束識(shí)別技術(shù),構(gòu)造了求解問題(1)的一個(gè)既不使用罰函數(shù)又無濾子的SQP算法,新算法既可以克服Maratos效應(yīng),又大大減少了計(jì)算工作量。

1 算法

對(duì)于所研究的問題(1),本文引入以下記號(hào):

(2)

(3)

(4)

正如傳統(tǒng)的濾子技巧,先定義約束違反函數(shù):

(5)

其中

(6)

由以上定義可得:p(c(x))=0當(dāng)且僅當(dāng)x為可行點(diǎn)。

首先作出如下假設(shè):

(H1)函數(shù)fi(x)(i∈I),gi(x)(i∈J)和hi(x)(i∈E)是二階連續(xù)可微的。

(H2)對(duì)任意x∈Rn,向量組{fi(x)-fik(x),i∈I(x){ik};gi(x),i∈J(x);hi(x),i∈E}LICQ成立。

(H3)點(diǎn)列{xk}有界,且存在常數(shù)a,b>0,使得對(duì)任意的k∈z+,d∈Rn,a‖d‖2≤dTHkd≤b‖d‖2成立。

根據(jù)上述假設(shè),我們用轉(zhuǎn)軸運(yùn)算[4]產(chǎn)生當(dāng)前迭代點(diǎn)xk的近似積極約束集Lk。

構(gòu)造新的基于積極約束集Lk上的二次規(guī)劃子問題產(chǎn)生搜索方向和高階校正方向,并保證其有解:

(7)

高階校正方向的二次規(guī)劃子問題:

(8)

下面給出算法的具體步驟:

算法A

步1(產(chǎn)生積極約束集)由轉(zhuǎn)軸運(yùn)算產(chǎn)生當(dāng)前迭代點(diǎn)xk的εk積極約束集Lk,εk為終止參數(shù)。

步2(產(chǎn)生搜索方向)求解二次規(guī)劃子問題(7),得其解為(dk,zk),相應(yīng)的KKT乘子為(λk,μk,νk).如果‖dk‖≤ε,則算法停止。

步4(搜索步長) 計(jì)算{1,β,β2,…}中滿足

(9)

(10)

或者

(11)

的最大值λk。

步6(更新迭代) 令xk+1=xk+λkdk,計(jì)算新的對(duì)稱正定矩陣Hk+1,置k=k+1,轉(zhuǎn)步1。

注:當(dāng)式(9)-(10)成立時(shí),我們稱之為一個(gè)f型迭代;當(dāng)式(11)成立時(shí),我們稱之為一個(gè)h型迭代。

2 收斂性分析

引理1[5]設(shè)假設(shè)(H1)-(H3)成立,Hk為對(duì)稱正定矩陣,且(dk,zk)為子問題(7)的最優(yōu)解,則對(duì)?x∈Rn,有

(2) 若dk=0,則xk為問題(1)的KKT點(diǎn)。

(3) 若dk≠0,則zk<0,且dk為函數(shù)F(x)在點(diǎn)xk的一個(gè)下降方向。

定理1 如果假設(shè)(H1)和(H3)成立,且limk→∞inf{F(xk)}>-∞,則算法A或者有限步終止于問題(1)的KKT點(diǎn),或者產(chǎn)生一個(gè)無窮點(diǎn)列{xk},其存在某一聚點(diǎn)x*為問題(1)的KKT點(diǎn)。

證明 (1)若算法A有限步終止,則顯然x*為問題(1)的KKT點(diǎn)。

(2)若算法A產(chǎn)生一個(gè)無窮點(diǎn)列{xk},由假設(shè)(H3)知{xk}存在聚點(diǎn)x*,故存在一無窮子列K,使得xk→x*,k∈K,有λk→λ*,則討論下面三種情況:

情形Ⅰ:當(dāng)k充分大時(shí),算法A均執(zhí)行h型迭代。

由題設(shè)可知,(11)式對(duì)步長λk均成立,可得

又因?yàn)閜(c(xk))≥0,故limk→∞p(c(xk))=0。用反證法,若x*不是問題(1)的KKT點(diǎn),則‖dk‖收斂到非零常數(shù),所以對(duì)充分大的k∈K,存在常數(shù)ε1>0,使得‖dk‖>ε1。不難證明,λk≥λ*=inf{λk,k∈K}>0。又因算法A均執(zhí)行h型迭代,則有

上式兩邊取極限得

出現(xiàn)矛盾。所以limk→∞‖dk‖=0,由引理1得,聚點(diǎn)x*為問題(1)的KKT點(diǎn)。

情形Ⅱ:當(dāng)k充分大時(shí),算法A均執(zhí)行f型迭代。

故{F(xk)}收斂。用反證法,若x*不是問題(1)的KKT點(diǎn),則‖dk‖收斂到非零常數(shù),所以對(duì)充分大的k∈K,存在常數(shù)ε1>0,使得‖dk‖>ε1。因?yàn)棣薻≥λ*=inf{λk,k∈K}>0。又由(9)式及假設(shè)(H3)得

上式兩邊取極限得

出現(xiàn)矛盾,所以limk→∞‖dk‖=0,由引理1得,聚點(diǎn)x*為問題(1)的KKT點(diǎn)。

情形Ⅲ:當(dāng)k充分大時(shí),h型迭代和f型迭代無限交替的情形。

不失一般性,若從(k2q-1+1)次迭代到k2q次迭代和從(k2q+1+1)次迭代到k2q+2次迭代均為h型迭代,從(k2q+1)次迭代到k2q+1次迭代均為f型迭代,其中q=0,1,2,….

首先證明:

(12)

根據(jù)算法A的結(jié)構(gòu),當(dāng)q=0,1,2,…時(shí),有

(13)

(14)

(15)

(16)

(17)

(18)

從而序列{…,p(c(xk2q-1)),p(c(xk2q+1)),…}是單調(diào)遞減序列,且對(duì)所有的q≥0,有p(c(xk2q+1))≤0.95p(c(xk2q-1)),由此可見limq→∞p(c(xk2q+1))=0。再結(jié)合(13)-(14)和p(c(xk))≥0,得

所以,由上極限結(jié)果不難得出limk→∞p(c(xk))=0,即(12)式得證。

再用反證法,假設(shè){xk}的每個(gè)聚點(diǎn)x*都不是問題(1)的KKT點(diǎn),則‖dk‖收斂到非零常數(shù),所以對(duì)充分大的k∈K,存在常數(shù)ε1>0,使得‖dk‖>ε1。又因h型迭代交替執(zhí)行無限次,由(11)式可知

上式兩邊取極限得

此式與(12)矛盾,所以limk→∞‖dk‖=0,由引理1得,聚點(diǎn)x*為問題(1)的KKT點(diǎn)。

3 數(shù)值實(shí)例

由表1可以看出:算法A的迭代次數(shù)比較少,精度比較高,并且適用范圍比較廣泛,尤其是對(duì)等式約束和混合約束極大極小問題來說效果更好。

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

續(xù)表1 數(shù)值結(jié)果

[1] Polak E,Mayne D H,Higgins J E.Superlinearly Convergent Algorithm for Min-max Problems[J].JournalofOptimizationTheoryandApplications,1991,69(3):407-439.DOI：10.1007/BF00940683.

[2] Wang F S,Wang Y P.Nonmonotone Algorithm for Minimax Optimization Problems[J].AppliedMathematicsandComputation,2011,217:6296-6308.DOI:10.1016/j.amc.2011.01.002.

[3] Wang F S,Jian J B.A Nonmonotonic Hybrid algorithm for min-max Problem[J].OptimizationandEngineering,2014,15:909-925.DOI:10.1007/S11081-013-9229-3.

[4] Jian J B,Zhang X L,Ma R Q.Generalized Monotone Line Search SQP Algorithm for Constrained Minimax Problems[J].Optimization,2009,58(1):101-131.DOI:10.1080/02331930801951140.

[5] 簡金寶.光滑約束優(yōu)化快速算法[M].北京:科學(xué)出版社,2010.

[6] Fletcher,Gould NIM,Leyffer S,etal.Global Convergence Of A Trust Region SQP-filter Algorithm for General Nonlinear Programming[J].SIAMJournalOnOptimization,2002,13:635-659.DOI:10.1137/S1052623499357258.

[7] Luo Z J,Wang L R.Improved Filter-SQP Algorithm with Active Set for Constrained Minimax Problems[J].JournalofAppliedMathematics,2014(2)：1-7.DOI:org/10:1152/2014/293475.

[8] Gould N,Toint Ph L.Nonlinear Programming Without a Penalty Function or a Filter[J].MathematicalProgramming,2010,122(1):155-196.DOI:10.1007/S10107-008-0244-7.

[9] Gould N,Toint Ph L.Erratum to:Nonlinear Programming without a Penalty Function or a Filter[J].MathematicalProgramming,2012,131(1-2):403-404.DOI:10.1007/S10107-011-491-X.

[10] Liu Xinwei,Yuan Yaxiang.A Sequential Quadratic Programming Method Without A Penalty Function Or A Filter For Nonlinear Equality Constrained Optimization[J].SIAMJournalOnOptimization,2011,21(2):545-571.DOI:1137/080739884.

[11] Rustem B，Nguyen Q.An Algorithm for the Inequality Constrained Discrete min-max Problem[J].SIAMJournalonOptimization,1998,8(1):265-283.DOI:10.1137/S1056263493260386.

A SQP Algorithm without a Penalty Function or a Filter for Constrained Minimax Problems

JIANG Hefeng,GAO Juan,WANG Fusheng*

(DepartmentofMathematics,TaiyuanNormalUniversity,Jinzhong030619,China)

A SQP algorithm without a penalty function or a filter is introduced to solve minimax problems with equality and inequality constraints. Based on theε-active constraint subset,two new quadratic programming subproblems are established to get the search direction, which both overcomes the Maratos effect, and greatly reduces the computational complexity of the algorithm.A new linear search step length strategy is proposed,the method not only avoids a choice of penalty factor,but also reduces the storage capacity of the computer.It is proved that under appropriate assumptions, the algorithm is globally convergent;moreover,several numerical examples are reported to verify the effectiveness and superiority of the algorithm.

Constrained minimax problems; SQP algorithm; Active constraint subset; Global convergence

10.13451/j.cnki.shanxi.univ(nat.sci.).2017.01.003

2016-06-01；

2016-08-30

國家自然科學(xué)基金(批準(zhǔn)號(hào):11171250)

姜合峰(1973-),男,碩士,副教授。

*通信作者：王福勝(WANG Fusheng),E-mail:fswang2005@163.com

O221.2

A

0253-2395(2017)01-0057-05