非線性規(guī)劃中的投影變尺度算法

王 碩，胡春燕

(1.桂林電子科技大學(xué) 數(shù)學(xué)與計算科學(xué)學(xué)院，廣西 桂林 541004；2.桂林電子科技大學(xué) 電子工程與自動化學(xué)院,廣西 桂林 541004)

非線性規(guī)劃中的投影變尺度算法

王 碩1，胡春燕2

(1.桂林電子科技大學(xué) 數(shù)學(xué)與計算科學(xué)學(xué)院，廣西 桂林 541004；2.桂林電子科技大學(xué) 電子工程與自動化學(xué)院,廣西 桂林 541004)

利用投影變尺度算法，求解一類包含等式和不等式約束的一般非線性規(guī)劃問題。算法基于積極集，將下降方向、可行方向、修正方向3個方向的合理組合作為算法搜索方向，且可行方向與修正方向僅需修改變尺度投影梯度方向中的部分分量。在可行集非空、問題函數(shù)2次連續(xù)可微、約束條件線性無關(guān)等條件下，證明了算法的全局收斂性和超線性收斂性。

非線性規(guī)劃；投影變尺度算法；全局收斂性；超線性收斂性

考慮非線性規(guī)劃問題：

(1)

其中：I={1,2,…,m};E={m+1,m+2,…,m+l};f:Rn→R，gj:Rn→R(j=1,2,…,m+l)連續(xù)可微。式(1)的可行解集記為X。

上述非線性規(guī)劃問題為包含等式和不等式約束的一般線性規(guī)劃問題。這類問題在工程技術(shù)、經(jīng)濟、博弈論等領(lǐng)域都有廣泛應(yīng)用[1-3]，受到廣泛關(guān)注。Spellucci[4]將SQP算法應(yīng)用于序列等式約束2次規(guī)劃問題，該方法也被稱為序列等式約束2次規(guī)劃問題(SECQP)算法。但其算法中相應(yīng)乘子在迭代過程中不能保證非負(fù)性，同時也存在其他缺點。朱志斌[5]針對這些問題，提出了修正的SQP算法，但是，其算法每次迭代計算量仍然很大。為此，提出一種非線性規(guī)劃中的投影變尺度算法，以減少計算量。

1 投影變尺度算法

minFc(x), s.t.gj(x)≤0,j∈L。

(2)

X+={x∈Rn|gj(x)≤0,j∈L=I∪E}。

作如下假設(shè)：

H1 式(1)、(2)的可行解集非空，即X≠?,X+≠?。

H2 函數(shù)f(x)、gj(x)(j∈L)至少2階連續(xù)可微。

H3 對?x∈X+,向量組{gj(x),j∈L(x)}線性無關(guān)。

1)計算：

2)令i=i+1,εk,i=εk,i-1/2，轉(zhuǎn)步驟1)。

3)計算：

Ak=A(xk)=(gj(xk),j∈Jk),

πk=π(xk)=-Bkf(xk)。

4)計算：

則令λk=1，轉(zhuǎn)步驟9)。

7)計算ρk=-通過求解線性方程組‖‖e,得；與一樣，組合?保證成立。建立如下凸組合：

其中

(5)

8)作非精確線搜索，求滿足

(6)

9)采用BFGS公式或DFP公式修正Hk+1，并且

令xk+1=xk+λkdk,k=k+1，返回步驟1)。

2 全局收斂性

H5 存在常數(shù)b≥a>0,使得?k∈R,?y∈Rn，有

a‖y‖2≤yTHky≤b‖y‖2。

引理1 對任意迭代指標(biāo)k,本算法中步驟1)迭代次數(shù)有限。

由文獻[5]，易證以下定理1、2。

引理2 對本算法，有以下結(jié)論成立：

2)若xk不是式(1)的KKT點，則有

且存在常數(shù)c0>0,使得Fc(x)Tqk≤-c0‖qk‖2。

證明 1)經(jīng)過簡單的推導(dǎo)易知

基于2005年、2008年、2011年、2014年以及2017年各年度內(nèi)南充市各景區(qū)交通道路數(shù)量、車流量以及實驗測試數(shù)據(jù)，以南充市20國家級旅游景區(qū)為例，對景區(qū)交通可達性進行定量化分析和計算，探討了影響景區(qū)交通可達性的關(guān)鍵因素，基于關(guān)鍵影響因素提出景區(qū)可達性的具體意見和優(yōu)化策略，以便更好地促進南充市旅游資源開發(fā)利用和旅游業(yè)快速發(fā)展。

由Hk的定義有：

f(xk)+Akγ=0,γj≥0；

γjgj(xk)=0,j∈Jk。

易知

αk=0,Hkf(xk)-HkAkBkf(xk)=0,

即Pkf(xk)=0，所以

-f(x)TPk

-(Pk

由式(4)知τk∈(0,1]，因此有

結(jié)論2)得證。

引理3 存在正整數(shù)k0，使得

ck≡ck0?c,?k≥k0。

Fc(xk)→Fc(x*)，k→。

(7)

gj(x*)Tq*<0，j∈I(x*)∪E。

當(dāng)k充分大時,

對于步驟8)產(chǎn)生的λk，易證λk≥λ*=inf{λk,k∈K}>0，k∈K；又根據(jù)式(7)得，

根據(jù)引理4，可得算法的全局收斂性。

對本算法中的x*及其對應(yīng)的KKT乘子μ*，作以下假設(shè)。

H6 2階充分條件及嚴(yán)格互補條件成立。

類似文獻[6]中的引理4.1，有以下結(jié)論。

定理4 若H4～H6成立，則有

‖xk+1-xk‖=0,

3 超線性收斂性

H7Hk→H*,k→。

引理5 1)當(dāng)k充分大時，Jk≡L(x*)=L*。

引理6 1)記

故存在η>0，使

2)由

證畢。

為證明超線性收斂，作如下假設(shè)。

其中：

引理7 當(dāng)k充分大時，

利用文獻[8]中定理5.2可得到以下收斂性結(jié)果。

定理5 本算法超線性收斂，即

‖xk+1-x*‖=o(‖xk-x*‖)。

4 結(jié)束語

基于一個積極集策略，將投影變尺度算法應(yīng)用到一類包含等式和不等式約束的一般非線性規(guī)劃問題。投影變尺度算法利用下降方向、可行方向、修正方向3個方向的合理組合作為算法中的搜索方向，減少了計算量。在可行集非空、問題函數(shù)2次連續(xù)可微、約束條件線性無關(guān)等條件下，證明了算法的全局收斂性和超線性收斂性。

[1] 高自友，賀國平.約束優(yōu)化問題的一個廣義梯度投影法[J].科學(xué)通報，1991,36(19):1443-1447.

[2] 賴炎連，賀國平，高自友.非線性最優(yōu)化的廣義梯度投影法[J].中國科學(xué)，1992(9):916-924.

[3] 簡金寶，張可村.不等式約束優(yōu)化一個具有強收斂的強次可行方向法[J].西安交通大學(xué)學(xué)報:自然科學(xué)版，1999,33(8):88-91.

[4]SpellucciP.AnSQPmethodforgeneralnonlinearprogramsusingonlyequalityconstrainedsubproblems[J].MathematicsProgram,1998,82(1):413-448.

[5]ZhuZhibin,ZhangWeidong,GengZhenjie.AfeasibleSQPmethodfornonlinearprogramming[J].AppliedMathematicsandComputation,2010(215):3956-3969.

[6]ZhuZhibin.AgloballyandsuperlinearlyconvergentfeasibleQP-freemethodfornonlinearprogramming[J].AppliedMathematicsandComputation,2005(168):519-539.

[7] 朱志斌.一個新的共軛投影梯度算法及其超線性收斂性[J].應(yīng)用數(shù)學(xué)學(xué)報，2004,27(1):149-161.

[8]FacchineiF,LucidiS.Quadraticlyandsuperlinearlyconvergentforthesolutionofinequalityconstrainedoptimizationproblem[J].JOTA,1995,85(1):265-289.

編輯：翁史振 見習(xí)編輯：陳汝偉

Project variable metric algorithm for nonlinear optimization

Wang Shuo1, Hu Chunyan2

(1.School of Mathematics and Computational Science, Guilin University of Electronic Technology, Guilin 541004, China;2.School of Electronic Engineering and Automation, Guilin University of Electronic Technology, Guilin 541004, China)

To solve nonlinear optimization with equality constraints or inequality constraints, an improved project variable metric algorithm is proposed. Based on an active set strategy, the direction is combined with the descent direction, the feasible direction and the revised direction. Part of the direction is combined with the feasible direction and the revised direction. In conditions that feasible sets are nonempty, the functions of problem are twice continuously differentiable, the vectors of constraints are linearly independent, global convergence and superlinear convergence of the proposed algorithm is proved.

nonlinear optimization; project variable metric algorithm; global convergence; superlinear convergence

2015-03-17

國家自然科學(xué)基金(11361018)；廣西自然科學(xué)基金(2014GXNSFAA118010)；廣西信息科學(xué)實驗中心開放基金(20130103)；桂林市科學(xué)研究與技術(shù)開發(fā)計劃(20140127-2)

胡春燕(1975-)，女，湖南雙峰人，講師，研究方向為最優(yōu)化及其應(yīng)用。E-mail:huchyel@guet.edu.cn

王碩，胡春燕.非線性規(guī)劃中的投影變尺度算法[J].桂林電子科技大學(xué)學(xué)報，2015,35(3):250-254.

O224

A

1673-808X(2015)03-0250-05