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

王 碩，胡春燕

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

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

王 碩1，胡春燕2

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

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

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

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

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

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 對(duì)?x∈X+,向量組{gj(x),j∈L(x)}線性無(wú)關(guān)。

1)計(jì)算：

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

3)計(jì)算：

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

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

4)計(jì)算：

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

7)計(jì)算ρk=-通過(guò)求解線性方程組‖‖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 對(duì)任意迭代指標(biāo)k,本算法中步驟1)迭代次數(shù)有限。

由文獻(xiàn)[5]，易證以下定理1、2。

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

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

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

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

基于2005年、2008年、2011年、2014年以及2017年各年度內(nèi)南充市各景區(qū)交通道路數(shù)量、車(chē)流量以及實(shí)驗(yàn)測(cè)試數(shù)據(jù)，以南充市20國(guó)家級(jí)旅游景區(qū)為例，對(duì)景區(qū)交通可達(dá)性進(jìn)行定量化分析和計(jì)算，探討了影響景區(qū)交通可達(dá)性的關(guān)鍵因素，基于關(guān)鍵影響因素提出景區(qū)可達(dá)性的具體意見(jiàn)和優(yōu)化策略，以便更好地促進(jìn)南充市旅游資源開(kāi)發(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充分大時(shí),

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

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

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

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

類(lèi)似文獻(xiàn)[6]中的引理4.1，有以下結(jié)論。

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

‖xk+1-xk‖=0,

3 超線性收斂性

H7Hk→H*,k→。

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

引理6 1)記

故存在η>0，使

2)由

證畢。

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

其中：

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

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

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

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

4 結(jié)束語(yǔ)

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

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

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

[3] 簡(jiǎn)金寶，張可村.不等式約束優(yōu)化一個(gè)具有強(qiáng)收斂的強(qiáng)次可行方向法[J].西安交通大學(xué)學(xué)報(bào):自然科學(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] 朱志斌.一個(gè)新的共軛投影梯度算法及其超線性收斂性[J].應(yīng)用數(shù)學(xué)學(xué)報(bào)，2004,27(1):149-161.

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

編輯：翁史振 見(jiàn)習(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

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

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

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

O224

A

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