姜合峰,高娟,王福勝

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

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

姜合峰,高娟,王福勝

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

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

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

0 引言

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

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

(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ù)正則極大項的技巧,梯度投影法,罰函數(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ù),構(gòu)造了求解問題(1)的一個既不使用罰函數(shù)又無濾子的SQP算法,新算法既可以克服Maratos效應(yīng),又大大減少了計算工作量。

1 算法

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

(2)

(3)

(4)

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

(5)

其中

(6)

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

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

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

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

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

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

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

(7)

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

(8)

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

算法A

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

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

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

(9)

(10)

或者

(11)

的最大值λk。

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

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

2 收斂性分析

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

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

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

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

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

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

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

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

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

上式兩邊取極限得

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

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

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

上式兩邊取極限得

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

情形Ⅲ:當(dāng)k充分大時,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,…時,有

(13)

(14)

(15)

(16)

(17)

(18)

從而序列{…,p(c(xk2q-1)),p(c(xk2q+1)),…}是單調(diào)遞減序列,且對所有的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}的每個聚點x*都不是問題(1)的KKT點,則‖dk‖收斂到非零常數(shù),所以對充分大的k∈K,存在常數(shù)ε1>0,使得‖dk‖>ε1。又因h型迭代交替執(zhí)行無限次,由(11)式可知

上式兩邊取極限得

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

3 數(shù)值實例

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

表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)號:11171250)

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

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

O221.2

A

0253-2395(2017)01-0057-05