存零約束優(yōu)化問題的序列二次方法*

羅美鈴， 李高西， 黃應全， 劉麗穎

（重慶工商大學 數(shù)學與統(tǒng)計學院，重慶 400067）

引 言

本文考慮下述非線性規(guī)劃問題：

其中，函數(shù)f(x)，g1,···,gp，h1,···,hq，G1,···,Gl，H1,···,Hl: Rn→R均連續(xù)可微.為簡單起見，我們令g=(g1,···,gp)T，h=(h1,···,hq)T，G=(G1,···,Gl)T，H=(H1,···,Hl)T.在問題(1)任意可行點x處，對任意固定的t，Gt(x)和Ht(x)至少有一個為零，我們稱這樣的約束為存零約束，稱問題(1)為“存零約束優(yōu)化”問題，簡記為MPSC問題.該模型首先由Mehlitz[1]提出并系統(tǒng)研究.文獻[1]指出，最優(yōu)控制問題的離散化、either-or約束優(yōu)化、0-1規(guī)劃等問題均可以轉(zhuǎn)化為問題(1)，因此有必要討論問題(1)的理論與算法.由于常用的約束規(guī)范，比如線性獨立約束規(guī)范(LICQ)、Mangasarian-Fromovitz約束規(guī)范(MFCQ)在問題(1)的可行點處均不滿足，因此不能將其看作一般的非線性規(guī)劃處理.

MPSC的約束結構與具有互補約束的優(yōu)化問題和具有消失約束的優(yōu)化問題密切相關(具體可見文獻[2]).最近，Mehlitz[1]給出了一些平穩(wěn)性概念，如弱平穩(wěn)性、Mordukhovich (M-)平穩(wěn)性和強(S)平穩(wěn)性來確保這些平穩(wěn)條件在問題的最優(yōu)點處成立，然后提出了一些MPSC定制的約束條件，例如MPSC Mangasarian-Fromovitz約束規(guī)范(MPSC-MFCQ)、MPSC線性獨立約束規(guī)范(MPSC-LICQ)、MPSC Abadie約束規(guī)范和MPSC Guignard約束規(guī)范.在文獻[1]的基礎上，Luo等[3]提出了一種求解MPSC的松弛方法；然后，Achtziger等[4]研究了MPSC的二階最優(yōu)性條件；最近，Liang等[5]討論了MPSC的最優(yōu)性條件和精確罰問題.

序列二次規(guī)劃算法，簡稱SQP算法，最早由Wilson提出.在數(shù)值效果和穩(wěn)定性方面，它是目前約束優(yōu)化問題的一種最有效的方法.隨著SQP算法自身理論的不斷完善，許多學者將該算法應用到工程和經(jīng)濟等各種實際優(yōu)化模型中，例如均衡問題[6-7]、最優(yōu)控制問題[8]、極大極小問題[9]、半無限規(guī)劃問題[10]等，并取得了顯著的效果.Wright[11]建議用改進的SQP算法處理非線性規(guī)劃問題.Fletcher等[6]將原始的SQP算法直接應用于均衡約束優(yōu)化(MPEC)問題，并得到了相關的收斂性結論.隨后，朱志斌等[12]同樣以MPEC為背景，引入線搜索和高階修正方向，從而獲得了更好的結果.由于求解一般非線性規(guī)劃問題的標準約束規(guī)范LICQ和MFCQ在MPSC中的任一可行點處均失效，我們便引入MPSC-LICQ到問題(1)中，并保證該問題在SQP算法下收斂.本文將SQP算法應用于問題(1)中，進而分析該算法的收斂性過程，這是本文研究的主要內(nèi)容.

本文主要結構如下：第1節(jié)給出本文研究所需的基本定義，同時討論了強平穩(wěn)條件與KKT條件的關系；第2節(jié)給出了該問題的序列二次算法框架；第3節(jié)在MPSC-LICQ條件下給出了算法的收斂性；第4節(jié)給出數(shù)值實驗結果；最后是所得結論.

1 預備知識

在本節(jié)中，我們先建立一些相關的指標集，同時給出與MPSC相關的基本定義，隨之分析問題(1)的強平穩(wěn)點和KKT點之間的關系.

為便于后續(xù)討論，定義指標集：

定義1[1]設x*∈Rn為 MPSC的可行點，如果存在乘子滿足

則我們稱x*為強平穩(wěn)點，簡記為S-平穩(wěn)點.

定義2[1]設x*∈Rn為 MPSC的可行點，如果在x*點處約束函數(shù)的梯度

滿足線性獨立，我們稱MPSC-LICQ在x*點處成立.

在文獻[1]中，Mehlitz通過構造MPSC特定的約束規(guī)格，從而來研究原問題(1)的局部最優(yōu)解與各平穩(wěn)點之間的關系.下面我們將直接分析原問題的KKT點與S-平穩(wěn)點的聯(lián)系.

定理1設x*為問題(1)的KKT點，當且僅當x*為該問題的S-平穩(wěn)點.

證明 必要性

則有

即得證x*為原問題的S-平穩(wěn)點.

充分性

令x*是原問題的S-平穩(wěn)點，由定義1，設對任意t∈{1,2,···,l}，有

則有

從而等價于

2 QP問題及算法

本節(jié)以文獻[13]為背景，在標準非線性規(guī)劃問題的基礎上引入了存零約束，同時給出相應的二次規(guī)劃子問題以及模型對應的算法.

對子問題產(chǎn)生的搜索方向d無論步長怎樣選取，都不能保證新的迭代點為原問題的可行點.為此，我們引進一個勢函數(shù)來確定步長，為使目標函數(shù)值下降，同時又使迭代點接近可行，我們使用?1精確罰函數(shù)：

基于問題(5)，首先給出算法的具體步驟.

算法

選擇參數(shù)η ∈(0,1/2)，ρ ∈(0,1)， 設容許誤差為0 ≤ε1,ε2?1.令k:=0.

步1求解子問題

的最優(yōu)解dk.

步2若‖dk‖≤ε1， 且‖ (g(xk))-‖1+‖h(xk)‖1+‖(G1(xk)H1(xk),···,Gl(xk)Hl(xk))T‖1≤ε2，停止計算，得到原問題的一個近似的下降方向.

步3將?1精確罰函數(shù)作為價值函數(shù)P(x,π)， 選擇罰參數(shù)πk，使得dk是該函數(shù)在xk處的下降方向.

步4Armijo搜索.令mk是使下列不等式成立的最小非負整數(shù)m：

P(xk+ρmdk,πk)-P(xk,πk)≤ηρmP′(xk,π;dk).

令αk:=ρmk,xk+1:=xk+αkdk.

步5計算下一步迭代的各約束梯度

以及對應的最小二乘乘子

步6 校正矩陣Bk為Bk+1.令

其中

參數(shù)θk定義為

步7令k:=k+1，轉(zhuǎn)步1.

為后續(xù)研究，我們給出子問題Q(x,B)的最優(yōu)系統(tǒng)：

其中(d,λ)為原始-對偶平穩(wěn)點.

3 SQP算法的全局收斂性

本節(jié)我們將在給定的假設條件下分析第2節(jié)中算法的收斂性.

引理1設f(x)和gi(x)(i∈{1,2,···,p})，hj(x)(j∈{1,2,···,q})，Gt(x)，Ht(x)(t∈{1,2,···,l})連 續(xù)可微，若在可行點x處MPSC-LICQ成立，算法產(chǎn)生的序列{xk}和 {dk}是 有界的，并且l imk∈N0,k→∞xk=x*， 令則序列{λk}有界.

證明用反證法，假設序列{ λk} 無界，則存在N1?N0，使得

根據(jù)子問題Q(xk,Bk)最優(yōu)系統(tǒng)第一個等式有

上述等式與MPSC-LICQ矛盾.因此{ λk}有界.

類似于文獻[13]中的定理11.2.1可得如下定理.

定理2設f(x)和gi(x)(i∈{1,2,···,p})，hj(x)(j∈{1,2,···,q})，Gt(x),Ht(x)(t∈{1,2,···,l}) 連續(xù)可微，矩陣B正定，若 (d,λ)為 子問題Q(x,B)的 KKT點對，其中d≠0 ， 引理1成立，且有 |λτ|≤πτ，τ∈{1,2,···,p}∪{1,2,···,q}∪{1,2,···,l}， 則P′(x,π;d)＜0.

證明定義指標集：

并根據(jù)文獻[13]中的引理11.2.1，我們有

利用子問題Q(x,B)的最優(yōu)性條件：

并在上述等式兩邊同時乘以d得

由于d為 子問題Q(x,B)的 解，根據(jù)題設和互補條件分析P′(x,π;d)的右端第二項開始的各級數(shù)或小于等于零或等于零，進而有

下面將給出對應算法的全局收斂性結果.

定理3設f(x)和gi(x)(i∈{1,2,···,p})，hj(x)(j∈{1,2···,q})，Gt(x)，Ht(x)(i∈{1,2,···,l})連續(xù)可微，引理1成立，且存在正常數(shù)m與M使對任意的d∈Rn，有

m‖d‖2≤dTBkd≤M‖d‖2, ?k≥1.

則在Armijo步長規(guī)則下，算法產(chǎn)生的點列或終止于原問題的S-平穩(wěn)點，或其聚點是S-平穩(wěn)點.

證明若存在指標k使dk=0， 則由子問題Q(xk,Bk)的最優(yōu)性條件得

從而xk為原問題(1)的KKT點，算法終止.

若對任意的k， 均有dk≠0，則算法產(chǎn)生無窮點列 {xk}.設x*為 其一聚點，由MPSC-LICQ和引理1中 { λk}的有界性，不妨設

再由式(8)， ?f(x),?gi(x),?hj(x),?Gt(x)和 ?Ht(x)的 連續(xù)以及B*的正定性，可知 {dk}k∈N0收斂，記極限為d*.則(d*,λ*)是 子問題Q(x*,B*)的KKT點對.

下面用反證法證明d*=0.若d*≠0，由Armijo步長規(guī)則

P(xk+αkdk,π)≤P(xk,π)+ηαk[?P(xk,π)]Tdk

有

當對于充分大的k∈N0，且根據(jù)定理2有

此矛盾說明d*=0， 從而x*為原問題(1)的KKT點.由定理1，S平穩(wěn)條件與KKT條件等價，所以該點也為S-平穩(wěn)點.

4 數(shù)值實驗

本文在數(shù)值實驗過程中以MATLAB作為主要處理工具，其電腦型號及配置為Lenovo小新Pro14HU2021x，第十一代智能英特爾酷睿i5處理器，16 GB運行內(nèi)存.同時基于文獻[1]中存零約束的優(yōu)化問題實例，來分析SQP算法的數(shù)值實驗結果.

4.1 MPSC實例

例1考慮問題(文獻[1]中的例4.1)

顯然，( 1,1,1)是全局最優(yōu)解.

例2考慮問題(文獻[1]中的例5.1)

其有唯一的全局最小解( 0,0).

例3考慮問題(文獻[1]中的例5.2)

其有唯一的全局最小解( 0,0).

例4考慮問題(文獻[1]中的例5.3)

其有唯一的全局最小解( 0,0).

對以上例子進行數(shù)值實驗，其中后3個例子取相同初始值.由于每次運行時間不同，我們對每個例子在同一初始值處分別運行50次，求各項結果的平均值.表1中每列表示意義如下：第一列表示各算例，x*表示問題的精確解，x′表示問題的近似解，S表示成功率，N表示平均迭代次數(shù)，T表示平均運行時間.

表1中結果顯示，通過SQP算法每次都能成功并較快地獲得問題的精確解或近似解，其中同一目標函數(shù)對應的約束函數(shù)越復雜，處理該問題的迭代次數(shù)和運行時間會相應增多或變長.這一結果說明采用SQP算法來處理MPSC是合理可行的.

4.2 投資組合

隨后，我們基于文獻[14]中的投資組合優(yōu)化實例對應的存零約束問題，來分析SQP算法的數(shù)值實驗結果.例子如下：

其中的變量x,y∈Rn， 隨機生成Q∈Rn×n，μ ∈Rn，l,u∈Rn以及ρ ∈R，e表示所有元素均為1的列向量.變量與參數(shù)的實際經(jīng)濟含義為：x,y分 別表示所選擇投資股票的份額(比例)和松弛變量，Q為方差-協(xié)方差矩陣，μ 為資產(chǎn)的預期收益平均值，l,u為資產(chǎn)的最小最大買入閾值，ρ為 期望的回報水平.以上參數(shù)取值為ρ=0．002,li=-10,ui=20(i=1,2,···,n)，μ是 隨機生成的列向量，初始點x0是 從第一行開始每1 /(2n)個元素分別取值為-1/(2n)，5 /(2n)， 0和0的列向量，Q為 隨機生成的對稱正定矩陣.表2中第一列表示樣本量，即x的維度，其余符號如表1所述.

表1 MPSCs數(shù)值結果Table 1 MPSCs numerical results

表2 投資組合數(shù)值結果Table 2 Portfolio numerical results

結果顯示，隨著變量維度的不斷增加，相應的迭代次數(shù)和運行時間逐漸增加，與此同時，SQP算法處理投資組合問題時的成功率雖然逐漸降低，但依舊能較大概率求解該問題，這一結果說明SQP算法處理含高維變量的問題仍然可行.

5 結 論

本文研究了存零約束優(yōu)化問題的求解方法.首先基于MPSC相應的定義，討論了MPSC中的S-平穩(wěn)點和KKT點之間的關系，然后利用SQP算法設計出該類問題對應的算法.通過構造合理的假設條件，證明了算法生成的乘子的適定性，進而得到了算法的全局收斂性質(zhì).最后的數(shù)值實例表明提出的算法對求解存零約束優(yōu)化問題的可行性，且可推廣應用到具有大樣本的實際經(jīng)濟問題中.本文應用的方法對于求解存零約束優(yōu)化問題提供了一個新的方式.

致謝本文作者衷心感謝重慶工商大學科研項目(ZDPTTD201908)和重慶工商大學研究生創(chuàng)新型科研項目(yjscxx2022-112-184)對本文的資助.

參考文獻（ References ）：

［1］MEHLITZ P.Stationarity conditions and constraint qualifications for mathematical programs with switching constraints[J].Mathematical Programming, 2020, 181（1）: 149-186.

［2］MEHLITZ P.On the linear independence constraint qualification in disjunctive programming[J].Optimization,2020, 69（10）: 2241-2277.

［3］LUO Z Q, PANG J S, RALPH D.Mathematical Programs With Equilibrium Constraints[M].Cambridge: Cambridge University Press, 1996.

［4］ACHTZIGER W, KANZOW C.Mathematical programs with vanishing constraints: optimality conditions and constraint qualifications[J].Mathematical Programming, 2008, 114（1）: 69-99.

［5］LIANG Y C, YE J J.New optimality conditions and exact penalty for mathematical programs with switching constraints[J].Journal of Optimization Theory and Applications, 2021, 190: 1-31.

［6］FLETCHER R, LEYFFER S, RALPH D, et al.Local convergence of SQP methods for mathematical programs with equilibrium constraints[J].SIAM Journal on Optimization, 2006, 17（1）: 259-286.

［7］朱志斌, 羅志軍, 曾吉文.互補約束均衡問題一個新的磨光技術[J].應用數(shù)學和力學, 2007, 28（10）: 1253-1260.（ZHU Zhibin, LUO Zhijun, ZENG Jiwen.Complementary constraint equalization problem a new polishing technique[J].Applied Mathematics and Mechanics, 2007, 28（10）: 1253-1260.（in Chinese））

［8］ITO K, KUNISCH K.Augmented Lagrangian-SQP methods for nonlinear optimal constol problems of tracking type[J].SIAM Journal on Control and Optimization, 1996, 34（3）: 874-891.

［9］YU Y H, GAO L.Nonmonotone line search algorithm for constrained minimax problems[J].Journal of Optimization Theory and Application, 2002, 115: 419-446.

［10］LING C, QI L Q, ZHOU G L, et al.Global convergence of a robust smoothing SQP method for semi-infinite programming[J].Journal of Optimization Theory and Application, 2006, 129: 147-164.

［11］WRIGHT J.Modifying SQP for degenerate problems[J].SIAM Journal on Optimization, 2002, 13（2）: 470-497.

［12］朱志斌, 簡金寶, 張聰.非線性互補約束均衡問題的一個SQP算法[J].應用數(shù)學和力學, 2009, 30（5）: 613-622.（ZHU Zhibin, JIAN Jinbao, ZHANG Cong.An SQP algorithm for mathematical programs with nonlinear complementarity constraints[J].Applied Mathematics and Mechanics, 2009, 30（5）: 613-622.（in Chinese））

［13］王宜舉, 修乃華.非線性最優(yōu)化理論與方法[M].北京: 科學出版社, 2019.（WANG Yiju, XIU Naihua.Theory and Method of Nonlinear Optimization[M].Beijing: Science Press, 2019.（in Chinese））

［14］FRANGIONI A, GRNTILE C.SDP diagonalizations and perspective cuts for a class of nonseparable MIQP[J].Operations Research Letters, 2007, 35（2）: 181-185.