約束優(yōu)化問題穩(wěn)定序列二次規(guī)劃方法研究綜述*

劉美杏,簡金寶

(玉林師范學(xué)院,復(fù)雜系統(tǒng)優(yōu)化與大數(shù)據(jù)處理廣西高校重點實驗室,廣西玉林　537000)

?

約束優(yōu)化問題穩(wěn)定序列二次規(guī)劃方法研究綜述*

劉美杏,簡金寶**

(玉林師范學(xué)院,復(fù)雜系統(tǒng)優(yōu)化與大數(shù)據(jù)處理廣西高校重點實驗室,廣西玉林537000)

(Guangxi Colleges and Universities Key Lab of Complex System Optimization and Big Data Processing,Yulin Normal University,Yulin,Guangxi,537000,China)

摘要:穩(wěn)定序列二次規(guī)劃(sSQP)方法由于在求解病態(tài)或退化約束優(yōu)化問題獲得理論與數(shù)值的突破性進展而備受關(guān)注,重要成果頻繁問世.本文對近期國際上若干重要sSQP方法及其思想進行概述,包括罰函數(shù)型sSQP方法,濾子型sSQP方法和非精確恢復(fù)(IR)型sSQP方法等,并對約束優(yōu)化問題sSQP方法的進一步研究進行探索性思考.

關(guān)鍵詞：約束優(yōu)化問題穩(wěn)定序列二次規(guī)劃收斂速度

0　引言

穩(wěn)定序列二次規(guī)劃(sSQP)方法作為序列二次規(guī)劃(SQP)方法的重要擴展,致力于考慮子問題模型、假設(shè)條件、技術(shù)構(gòu)造、收斂性質(zhì)(全局收斂或收斂速度)與數(shù)值效果等方面的研究.尤其是對相對弱條件下的收斂速度與數(shù)值效果.值得注意的是,對于退化約束優(yōu)化問題,當對應(yīng)原始解的拉格朗日乘子不唯一時,快速收斂性的實現(xiàn)難度極大.自1998年,Wright[1]首次提出求解退化不等式約束優(yōu)化的sSQP方法以來,以 Wright,Hager,Izmailov,Fernndez,Solodov,Gill及Robinson等為代表的sSQP方法及理論研究發(fā)展迅速,取得系列成果.文獻[1]的方法在每次迭代時需求解一個目標函數(shù)二次的極大極小問題,可等價轉(zhuǎn)化為原始對偶空間上的穩(wěn)定二次規(guī)劃(QP)問題。該作者在二階充分最優(yōu)性條件(SOSC)、Mangasarian-Fromovitz約束規(guī)格(MFCQ)和嚴格互補等條件下,證明了sSQP方法的局部二次收斂性.文獻[2]進一步改進文獻[1]的sSQP方法,在SOSC和MFCQ等較弱的條件下,證明算法具備局部二次收斂性.Hager[3]對收斂性假設(shè)條件進行研究,僅在SOSC條件下獲得文獻[1]中算法的局部收斂性,并提出用一對不等式約束來表示等式約束,從而可將方法推廣到一般約束優(yōu)化問題.相比較,傳統(tǒng)SQP方法對乘子唯一性有著較苛刻的要求,只能依靠嚴格MFCQ條件來保證.特別地,在等式約束情形下,迫使線性無關(guān)約束規(guī)格(LICQ)成立[4].文獻[5]將sSQP方法推廣到求解含等式與不等式約束的變分問題,當初始點充分靠近原始對偶穩(wěn)定點時,僅需SOSC假設(shè)條件,實現(xiàn)了算法的超線性收斂性.對于等式約束優(yōu)化問題,文獻[6]在非臨界乘子的條件下建立了超線性收斂的sSQP方法.文獻[7]基于線性方程組,在無需LICQ和嚴格互補等較強的假設(shè)條件下,提出一個二次收斂的牛頓型sSQP方法,并給出了該方法超線性收斂的重要定理.文獻[8]將擬牛頓型sSQP方法拓廣到變分不等式問題,通過對Bregman距離極小化來更新矩陣信息,這樣僅需要SOSC便可證明算法的超線性收斂性.

上述文獻主要聚焦在最優(yōu)解的局部范圍內(nèi)構(gòu)造有效算法,并研究不同假設(shè)條件對其收斂速度的影響,建立了一批局部超線性收斂或二次收斂的sSQP方法.這些文獻都側(cè)重于局部收斂速度的分析,對算法全局優(yōu)化策略(全局收斂性質(zhì))未做深入研究.而此問題正是實際應(yīng)用和優(yōu)化學(xué)者們希冀解決的問題,也是衡量最優(yōu)化算法有效性的重要指標之一.近年來，盡管國內(nèi)外不少學(xué)者對全局化sSQP方法潛心研究,但成果有限.本文主要介紹如下幾類的全局sSQP算法:罰函數(shù)型sSQP方法[9-12]、濾子型sSQP方法[13]和IR型sSQP方法[14],并對約束優(yōu)化問題sSQP方法的進一步研究進行探索性思考.

1　函數(shù)型sSQP方法

當前,對sSQP方法全局化策略的研究仍是一項極其具有挑戰(zhàn)性的工作,其中約束優(yōu)化sSQP方法全局化時罰函數(shù)的選取極其困難,這對于最優(yōu)性或下降性影響甚大.Gill等[9]引入原始對偶廣義增廣拉格朗日(AL)函數(shù),提出了一個求解等式約束加簡單界約束優(yōu)化問題的全局收斂sSQP方法.Izmailov等[11]充分利用AL方法的魯棒性,在沒有任何積極約束識別策略下構(gòu)造了一個sSQP方法,并證明了算法的全局收斂性和局部收斂速度.隨后,他們又在文獻[12]中以原始對偶精確罰函數(shù)[15]為效益函數(shù),提出了一個求解等式約束優(yōu)化問題的sSQP方法,并分析了算法的全局收斂性和超線性收斂速度.下面參考文獻[12],介紹一個具體的罰函數(shù)型sSQP算法.

考慮等式約束優(yōu)化問題:

min f(x)

s.t. h(x)=0,

(1)

其中f(x):Rn→R,h(x)=(h1(x),…,hl(x))T:Rn→Rl至少是二階可微函數(shù).令問題(1)的Lagrange函數(shù)為

(2)

(3)

進而,定義函數(shù)Φ:Rn×Rl→ Rn×Rl,

(4)

對一個給定的原始對偶迭代點(x,λ)∈Rn×Rl及穩(wěn)定參數(shù)σ>0,考慮如下原始對偶空間上的sSQP子問題,并產(chǎn)生sSQP方向(ξ,η)，

s.t. h(x)+h′(x)ξ-ση=0,

(5)

基于上述sSQP方向(搜索方向),文獻[12]采用如下原始對偶效益函數(shù)[15]φc1,c2:Rn×Rl→ R,

(6)

此處選取適當罰參數(shù)c1>0,c2>0,可以保證由子問題(5)產(chǎn)生的sSQP方向是φc1,c2(x,λ)的下降方向.

由文獻[16]和文獻[17]知,原始對偶效益函數(shù)(6)是一個精確罰函數(shù).即如果c2>0充分小,c1>0充分大,則φc1,c2(x,λ)任意穩(wěn)定點都是問題(1)的穩(wěn)定點;反之,如果最優(yōu)性系統(tǒng)(3)的原始對偶解(x,λ)滿足LICQ和SOSC等條件,則它必是罰函數(shù)φc1,c2(x,λ)的嚴格局部極小解.

(7)

算法1(文獻[12]中sSQP算法)

步驟1由(4)式計算ΦkΦ(xk,λk),若Φk=0,終止.

步驟3(i)如果

(8)

則進入步驟5.

(ii)如果

‖h(xk)‖≥ψ1(σk)

(9)

且

(10)

(iii)如果

(11)

步驟5計算αk=θj,此處j為滿足不等式

φc1,c2((xk,λk)+θjdk)≤φc1,c2(xk,λk)+

(12)

的最小非負整數(shù).

步驟6令(xk+1,λk+1)=(xk,λk)+αkdk,k∶=

k+1,返回步驟1.

在算法1的迭代過程中,常量值C1,C2的設(shè)置對該算法的執(zhí)行有著重要的防御作用.一般地,這兩個數(shù)值應(yīng)該取足夠大,方能保證罰參數(shù)c1,c2的更新法則不受影響.為了增強算法設(shè)計的有效性,當子問題(5)KKT系統(tǒng)無解或步驟3的任一情形都不被執(zhí)行時,算法1執(zhí)行步驟4的擬牛頓步防御措施,以修正sSQP方向使之具有下降性,從而算法具有良好的適定性和全局收斂性質(zhì).當初始點充分靠近穩(wěn)定點時,僅需要非臨界Lagrangian乘子假設(shè),即可證明算法1的超線性收斂.對退化測試問題,算法1表現(xiàn)出了良好的數(shù)值效果.

2　濾子型sSQP方法

濾子法是近20年提出的求解非線性約束優(yōu)化的一種有效方法.該方法的提出是為了避免在實際問題中設(shè)置罰參數(shù).早期濾子法的研究歸功于Fletcher和Leyffer[20],隨后該方法因良好的數(shù)值效果而備受關(guān)注,近期代表成果見文獻[21-23]等.文獻[13]對穩(wěn)定QP子問題進行修正,并結(jié)合雙濾子技術(shù)[21]提出了求解一般約束優(yōu)化問題的濾子型sSQP方法.下面對文獻[13]中的算法進行分析.

考慮如下一般非線性規(guī)劃問題:

min f(x)

s.t. hε(x)=0,

hΙ(x)≤0,

(13)

其中,hε(x)=(hi(x),i∈ε),hΙ(x)=(hi(x),i∈Ι),ε= {1,2,·s,l},Ι= {l+1,l+2,·s,m},f:Rn→ R,hi:Rn→ R,i∈ε∪Ι為連續(xù)可微函數(shù).定義問題(13)的Lagrangian函數(shù)L(x,μ)為

(14)

這里μ=(μ1,μ2,·s,μm)T是Lagrangian乘子向量.

對于當前給定的原始對偶估計迭代點對(xk,μL,k),求解如下修正的穩(wěn)定QP子問題:

(15)

(16)

問題(15)是一個傳統(tǒng)的穩(wěn)定QP子問題模型.源于算法良好的收斂性質(zhì),設(shè)計了兩種乘子更新方式,其中μL,k保證全局收斂,μk則滿足局部收斂的需求.類似地,考慮Bk和σL,k的更新準則.

基于問題(15)的解(dk,Δλk),定義原始對偶搜索方向(dk,Δμk)(此處Δμk=Δλk+μL,k-μk),此方向?qū)λ惴ㄊ諗啃岳碚摲治鲇兄匾淖饔?其等價于求解如下相容的穩(wěn)定QP子問題:

Δμ‖2

(17)

在設(shè)計非線性規(guī)劃問題(13)的有效算法時,除需要對目標函數(shù)進行極小化,同時要不斷降低約束違反度函數(shù):

(18)

然而,搜索方向(dk,Δμk)難以直接達到這樣的要求.因此,引入如下輔助目標函數(shù)Φ(x,μ)和松弛約束違反度函數(shù) p(x,μ):

(19)

(20)

進而引進雙濾子技術(shù)(基于文獻[21],但有所改進),包括“全局濾子”和“局部濾子”.前者致力于算法收斂于KKT點或穩(wěn)定點,后者以實現(xiàn)其局部收斂速度.對于第k次迭代,“全局濾子”和“局部濾子”分別記為Fgk,Flk.

(21)

(22)

此處γ1,γ2∈(0,1).

(23)

(24)

此處γ3>0是一個常數(shù).

對于問題(13)及當前迭代點對(xk,μk),求解穩(wěn)定QP子問題(17)得到搜素方向(dk,Δμk),并沿著此方向和步長α,分別定義函數(shù)Φ的實際下降量和線性預(yù)測下降量:

ΔΦk(α)=Φ(xk,μk)-Φ(xk+αdk,μk+αΔμk),

(25)

此外,文獻[13]結(jié)合“全局濾子”接受條件,進一步利用回溯技術(shù)選擇了恰當?shù)牟介Lαk,判斷條件和步長下界.

開關(guān)條件:

(26)

充分下降條件:

(27)

(28)

(29)

其中,

(30)

(31)

(32)

其中,μmax>0,β∈(0,1)是兩個常數(shù).

下面給出求解問題(13)的濾子型sSQP算法.

算法2(文獻[13]中sSQP算法之外循環(huán))

步驟1如果(xk,μk)是問題(13)的KKT點或不可行穩(wěn)定點,則終止.

算法3(算法2之內(nèi)循環(huán))

步驟3如果開關(guān)條件(26)不成立或充分下降條件(27)成立,則終止.否則令α=r α,返回步驟1.

利用雙濾子技術(shù),由算法2產(chǎn)生的所有迭代點均能被濾子接受(全局濾子或局部濾子),這對整個算法的收斂性質(zhì)分析起到至關(guān)重要的作用.在理論上,不需要任何約束規(guī)格,即可證明:濾子型sSQP算法2不僅具有全局收斂性(存在收斂子列或收斂于KKT點,或收斂于不可行穩(wěn)定點),而且在SOSC下,算法達到超線性收斂速度.

3　IR型sSQP方法

sSQP方法的研究最早可以追溯到20世紀末,雖然在適當?shù)募僭O(shè)條件或技術(shù)下早期的研究成果實現(xiàn)了算法快速的收斂速度,但在理論上能實現(xiàn)全局收斂的成果較少.濾子型sSQP方法需儲存濾子信息,會造成存儲量大,而且當?shù)c遠離可行域,或者在迭代過程中當試探步長比既定下界要小時,為尋找一個能被全局濾子接受的新迭代點,需要執(zhí)行可行性恢復(fù)階段,這無疑增加算法計算成本,從而影響數(shù)值效果.然而,IR技術(shù)[24-27]可以減少可行性恢復(fù)階段的復(fù)雜性,對sSQP算法的理論分析有著重要的作用.文獻[14]提出了求解含等式且變量有界約束優(yōu)化的IR型sSQP方法.下面詳細介紹此算法.

考慮問題(1),且滿足約束條件x∈Ω={x∈Rn|a≤x≤b},此處a,b∈Rn.定義問題(1)的自然殘差σ:Rn×Rl→R，

(33)

其中,PΩ表示在Ω上的正交投影,L∶Rn×Rl→R是Lagrangian函數(shù)(2).

對于原始對偶迭代點對(xk,λk),罰參數(shù)ρk>0及Qk，其中Qk是問題(1)Lagrangian Hesse的近似,考慮如下擬牛頓型sSQP子問題:

xk‖λ‖2

ξ∈Ω.

(34)

為構(gòu)造全局收斂算法,引入下面的輔助函數(shù)Fk(x,λ),Hk(x,λ):Rn× Rl→ R:

(35)

(36)

選取點Yk(x)=(x,λk+ρkh(x)),易知Hk(Yk(x))=0,?x∈Rn,且對于Yk∶=Yk(xk),Y∶=(x,λ),sSQP子問題(34)等價于如下QP子問題:

(37)

注意到Hk(Yk)=0.不難發(fā)現(xiàn)上述QP子問題(37)對應(yīng)于優(yōu)化問題:

s.t.Hk(Y)=0,Y∈Ω×Rl

(38)

的QP近似子問題.通過近似求解問題(37)可獲得sSQP方法的局部收斂性質(zhì)[3,5].

對每次迭代,IR方法包括恢復(fù)階段和極小化階段.在恢復(fù)階段,給定迭代點Xk,計算恢復(fù)點Yk,避免了目標函數(shù)值以及可行性惡化.在極小化階段,基于可行性和最優(yōu)性構(gòu)造了一個含罰參數(shù)的效益函數(shù),并沿著一階可行方向進行線搜索.

下面給出IR型sSQP算法的具體步驟.

算法4(文獻[14]中sSQP算法)

(39)

步驟2(i)令Xk,0=(xk,0,λk,0)=(xk,λk),θ0∈(0,1),Qk,0為對稱正定矩陣,j∶=0.

(ii)計算Yk,j=(xk,j,λk,j+ρkh(xk,j)),求解如下QP子問題,得到最優(yōu)解Dk,j∈ Rn×Rl.

(40)

如果‖Dk,j‖

(iii)令θj+1∈{2-i:i∈N∪{0}}為滿足下面不等式的最大值:

Φk(Yk,j,θj+1)-Φk(Xk,j,θj+1)≤

(41)

此處Φk(X,θ)=θFk(X)+(1-θ)‖Hk(X)‖是效益函數(shù).

(iv)令tj∈{2-i:i∈N∪{0}}為滿足下面不等式的最大值:

Φk(Yk,j+tjDk,j,θj+1)-Φk(Xk,j,θj+1)≤

(42)

(v)令Xk,j+1=Yk,j+tjDk,j,選取對稱正定矩陣Qk,j+1,令j∶=j+1,返回步驟2(ii).

事實上，基于IR方法的思想,算法4無需實質(zhì)性地修正sSQP子問題(34)的結(jié)構(gòu)，只需求解子問題(37)得到非精確解，然后巧妙利用類似增廣拉格朗日(AL)罰參數(shù)更新策略(步驟3),即可獲得算法的全局收斂性質(zhì).在嚴格MFCO和SOSC等條件下,可保證罰參數(shù)序列是有界的,進而算法繼承了良好的局部收斂速度(線性收斂).

4　展望

本文對求解約束優(yōu)化問題的若干sSQP方法的思想及算法作了一個較詳細的概述,主要介紹了早期sSQP方法的局部收斂成果;近年來實現(xiàn)了全局收斂的罰函數(shù)型sSQP方法、濾子型sSQP方法和非精確恢復(fù)(IR)型sSQP方法.對sSQP方法還有如下一些問題值得思考和研究.

①如何修正原始對偶罰函數(shù)型sSQP算法,在適當?shù)募僭O(shè)條件下,將方法拓展到一般約束優(yōu)化問題,并制成軟件包使之得到廣泛應(yīng)用;

②現(xiàn)有的濾子型sSQP算法考慮內(nèi)點法求解一個與傳統(tǒng)QP子問題相當?shù)男拚€(wěn)定QP子問題,無疑會在嚴格內(nèi)點的選擇和計算上遇到困難;加之濾子技術(shù)需要進入可行性恢復(fù)階段,也會增加計算成本.因此,如何改進算法以減少計算量,有待進一步探討;

③目前基于IR技術(shù)構(gòu)造sSQP方法時,需要嚴格MFCQ和SOSC等條件以實現(xiàn)算法線性收斂,沒有繼承傳統(tǒng)sSQP方法優(yōu)點(具有快速收斂速度的魯棒性),如何修正罰參數(shù)以更新技術(shù)等,建立超線性收斂的IR型sSQP方法值得進一步深入研究;

④求解大規(guī)模稀梳優(yōu)化與工程優(yōu)化 (如龐雜的電氣工程中的潮流問題、機組合問題)的高效的sSQP方法有必要進一步探索.

參考文獻:

[1]WRIGHT S J.Superlinear convergence of a stabilized SQP method to a degenerate solution[J].Computational Optimization and Applications,1998,11(3):253-275.

[2]WRIGHT S J.Modifying SQP for degenerate problems[J].SIAM Journal on Optimization,2002,13(2):470-497.

[3]HAGER W W.Stabilized sequential quadratic programming[J].Computational Optimization and Applications,1999,12(1/2/3):253-273.

[4]IZMAILOV A F,SOLODOV M V.Newton-Type Methods for Optimization and Variational Problems:Springer Series in Operations Research and Financial Engineering[M].Switzerland:Springer International Publishing,2014.

[6]IZMAILOV A F,SOLODOV M V.Stabilized SQP revisited[J].Mathematical Programming,2012,133(1/2):93-120.

[7]LI D H,QI L.A Stabilized SQP Method via Linear Equations[R].New South Wales:Mathematics Department,University of New South Wales,2000.

[9]GILL P E,ROBINSON D P.A globally convergent stabilized SQP method[J].SIAM Journal on Optimization,2013,23(4):1983-2010.

[10]GILL P E,KUNGURTSEV V,ROBINSON D P.A Globally Convergent Stabilized SQP Method:Superlinear Convergence[R].UCSD Center for Computational Mathematics Technical Report CCoM-13-4,2014.

[11]IZMAILOV A F,SOLODOV M V,USKOV E I.Combining stabilized SQP with the augmented Lagrangian algorithm[J].Computational Optimization and Applications,2015,62(2):405-429.

[12]IZMAILOV A F,SOLODOV M V,USKOV E I.Globalizing stabilized sequential quadratic programming method by smooth primal-dual exact penalty function[J].Journal of Optimization Theory and Applications,2016,169(1):148-178.

[13]SHEN C G,ZHANG L H,LIU W.A stabilized filter SQP algorithm for nonlinear programming[J].Journal of Global Optimization,2016,65(4):677-708.

[15]DI PILLO G,GRIPPO L.A new class of augmented Lagrangians in nonlinear programming[J].SIAM Journal on Control and Optimization,1979,17(5):618-628.

[16]BERTSEKAS D P.Constrained Optimization and Lagrange Multiplier Methods[M].New York:Academic Press,1982.

[17]BERTSEKAS D P.Enlarging the region of convergence of Newton’s method for constrained optimization[J].Journal of Optimization Theory and Applications,1982,36(2):221-252.

[18]IZMAILOV A F,SOLODOV M V.On attraction of Newton-type iterates to multipliers violating second-order sufficiency conditions[J].Mathematical Programming,2009,117(1/2):271-304.

[19]IZMAILOV A F,SOLODOV M V.Critical Lagrange multipliers:What we currently know about them,how they spoil our lives,and what we can do about it[J].TOP,2015,23(1):1-26.

[20]FLETCHER R,LEYFFER S.Nonlinear programming without a penalty function[J].Mathematical Programming,2002,91(2):239-269.

[21]SHEN C G,LEYFFER S,FLETCHER R.A nonmonotone filter method for nonlinear optimization[J].Computational Optimization and Applications,2012,52(3):583-607.

[22]GOULD N I M,LOH Y,ROBINSON D P.A filter method with unified step computation for nonlinear optimization[J].SIAM Journal on Optimization,2014,24(1):175-209.

[23]GOULD N I M,LOH Y,ROBINSON D P.Anonmon- otone filter SQP method:Local convergence and numerical results[J].SIAM Journal on Optimization,2015,25(3):1885-1911.

[26]BIRGIN E G,MARTNEZ J M.Local convergence of an inexact-restoration method and numerical experiments[J].Journal of Optimization Theory and Applications,2005,127(2):229-247.

[27]FISCHER A,FRIEDLANDER A.A new line search inexact restoration approach for nonlinear programming[J].Computational Optimization and Applications,2010,46(2):333-346.

(責(zé)任編輯：尹闖)

An Overview of the Researches on Stabilized Sequential Quadratic Programming Methods for Constrained Optimization Problems

LIU Meixing,JIAN Jinbao

Key words：constrained optimization problems,stabilized sequential quadratic programming,convergence rate

Abstract：The stabilized sequential quadratic programming (sSQP) methods attract great attention with respect to the theoretical and numerical breakthrough for solving ill-posed or degenerate constrained optimization problems,and many important references about sSQP methods were published.This paper gives an overview on some important sSQP methods,which mainly include penalty function type sSQP methods,filter type sSQP methods and inexact restoration (IR) type sSQP methods,and a few exploratory considerations for further study on sSQP methods are given.

收稿日期：2016-07-01

作者簡介：劉美杏(1987-),女，碩士，主要從事最優(yōu)化理論與算法研究。

中圖分類號:O221.2

文獻標識碼：A

文章編號：1005-9164(2016)05-0385-07

修回日期：2016-08-27

*國家自然科學(xué)基金項目(11271086),廣西自然科學(xué)基金項目(2014GXNSFFA118001),廣西高校科研項目(ZD201407)和復(fù)雜系統(tǒng)優(yōu)化與大數(shù)據(jù)重點實驗室開放基金項目(2015CSOBDP0203)資助。

**通信作者:簡金寶(1964-),男,教授,博士,博士生導(dǎo)師,主要從事最優(yōu)化理論與算法及應(yīng)用研究,E-mail:jianjb@gxu.edu.cn。

廣西科學(xué)Guangxi Sciences 2016,23(5):385～391

網(wǎng)絡(luò)優(yōu)先數(shù)字出版時間：2016-11-21【DOI】10.13656/j.cnki.gxkx.20161121.006

網(wǎng)絡(luò)優(yōu)先數(shù)字出版地址：http://www.cnki.net/kcms/detail/45.1206.G3.20161121.1520.012.html