解才先，朱寧

（桂林電子科技大學(xué)數(shù)學(xué)與計(jì)算科學(xué)學(xué)院，廣西桂林541004）

一個(gè)不等式約束問(wèn)題的SQP方法及其收斂性

解才先，朱寧

（桂林電子科技大學(xué)數(shù)學(xué)與計(jì)算科學(xué)學(xué)院，廣西桂林541004）

提出一個(gè)關(guān)于不等式約束問(wèn)題的SQP算法，其效益函數(shù)為非可微精確罰函數(shù)，罰因子具有自動(dòng)調(diào)節(jié)性.通過(guò)求解一輔助線性方程組，獲得二階修正步，并利用弧式搜索，建立了問(wèn)題的一個(gè)可行下降算法.在一定的假設(shè)條件下，證明了算法是全局收斂的，并且具有超線性收斂速度.

SQP方法；弧式搜索；非可微精確罰函數(shù)；全局收斂性；超線性收斂性

0 引言

序列二次規(guī)劃（SQP）算法是解非線性最優(yōu)化問(wèn)題的最有效方法之一，自上世紀(jì)70年代以來(lái)一直是非線性領(lǐng)域的一個(gè)研究熱點(diǎn)[1-8].但是，如果不等式約束優(yōu)化問(wèn)題對(duì)應(yīng)的二次子問(wèn)題無(wú)可行解，或者它即使有解，但其解為無(wú)界時(shí)，則該方法失敗或產(chǎn)生一個(gè)不收斂的點(diǎn)列.針對(duì)這個(gè)問(wèn)題，研究者提出了一些解決方法.Zhang等[5]提出，當(dāng)二次子問(wèn)題無(wú)可行解或者有解但無(wú)界時(shí)，通過(guò)解一線性規(guī)劃獲得搜索方向，在一定假設(shè)條件下，獲得了算法的全局收斂性.本文在文獻(xiàn)［5］的基礎(chǔ)上對(duì)算法進(jìn)行了進(jìn)一步的修正，通過(guò)求解一輔助線性方程組獲得二階修正步，并利用弧式搜索，在一些微弱假設(shè)條件下，證得單位步長(zhǎng)是可以接受的，從而克服了Maratos效應(yīng)，最終得出該算法還具有超線性收斂速度.

1 算法模型

本文考慮如下不等式約束優(yōu)化問(wèn)題：

其中f:Rn→R，g:Rn→Rm是二階連續(xù)可微的.求解問(wèn)題（1）的SQP方法是一個(gè)迭代算法，每一步迭代中其搜索方向dk是通過(guò)求解下列二次子問(wèn)題所得：

這里Bk是一對(duì)稱正定矩陣.迭代具有下列形式：xk+1=xk+tkdk，其中tk是通過(guò)對(duì)效益函數(shù)采取一維搜索所得的步長(zhǎng).令：

Φ（x）沿著d∈Rn的方向?qū)?shù)為：

其中I0（x）=｛j:gj（x）=Φ（x），j∈M∪｛｝0｝，通常來(lái)講，Φ′（x；d）是不連續(xù)的.文獻(xiàn)［6］提出了Φ′（x；d）的一個(gè)連續(xù)逼近Φ*（x；d），即：

這里，稱式（3）為Φ（x）沿著方向d的偽方向?qū)?shù)，很容易證明Φ*（x；d）在Rn×Rn上是連續(xù)的[6].

引理1[7]?x,d∈Rn，有Φ*（x；d）≥Φ′（x；d），且Φ*（x；·）為Rn上的凸函數(shù).令：

定義1 （廣義MFCQ）[5]令x∈Fc，如果?z∈Rn，‖z‖=1和δx＞0，使得：成立，則稱在x處滿足廣義MFCQ.

當(dāng)x∈Fc，求解下列線性規(guī)劃：

令d（x，B）為下面二次規(guī)劃Q（x，B）的解：

這里B是一對(duì)稱正定矩陣.

引理2i）若Q（x，B）是可行的，則式（5）有唯一解d（x，B）.

ii）若d（x，B）為Q（x，B）的解，當(dāng)且僅當(dāng)存在一Lagrange乘子λ∈Rn，使得：

（S0）給定數(shù)據(jù)x1∈Rn，u∈（0，），B1對(duì)稱正定，α1，0為初始步長(zhǎng)，M1為對(duì)初始搜索方向dk范數(shù)的要求，σ，σ1分別為步長(zhǎng)αk及Mk的增長(zhǎng)倍數(shù)，α1，0＞0，M1＞0，σ＞1，σ1＞1，令k:=1；

（S1）令i:=0和tk，0=1，解式（2）計(jì)算dk，若式（2）不可行或xk∈Fc且‖dk‖＞Mk，轉(zhuǎn)（S5），若dk=0，停；

（S2）若ΔP（xk，αk，i，dk）≤轉(zhuǎn)（S4）；

（S3）αk，i:=σαk，i，若P（xk，αk，i）＞P（x1，αk，i），轉(zhuǎn)（S9），否則，轉(zhuǎn)（S2）.

轉(zhuǎn)（S8），其中ωk表示搜索方向，這里為

轉(zhuǎn)（S7）；

轉(zhuǎn)（S8），否則，i:=i+1，αk，i:=αk，i-1，選擇tk，i:=轉(zhuǎn)（S7）；

（S8）令αk+1，0:=αk，i（為方便起見(jiàn)，記ik=i，αk=αk，i，tk=tk，i），xk+1=xk+tkωk，Mk+1:=Mk，利用BFGS校正[9]公式產(chǎn)生Bk+1，令k:=k+1，轉(zhuǎn)（S1）；

（S9）令αk，0:=αk，i，xk:=x1產(chǎn)生一個(gè)新的Bk，轉(zhuǎn)（S1）.

2 算法可行性

在以下的分析中，假設(shè)如下條件成立.

假設(shè)Ai）{xk}是一有界序列；

ii）?x∈F，積極約束的梯度線性無(wú)關(guān)；

iii）?x∈Fc，廣義MFCQ在x處成立；

iv）?k，Bk為屬于一對(duì)稱正定矩陣的緊致集Σ中的有界序列，且存在常數(shù)0＜b1≤b2＜∞，使得b1‖dk‖2≤（dk）TBkdk≤b2‖dk‖2，?dk∈Rn，k=1，2，…成立.

由命題1，容易得以下定理.

定理1若算法在（S1）終止于xk，則xk是問(wèn)題（1）的K－T點(diǎn).

命題2[8]若假設(shè)A成立，是一可行點(diǎn)，是一對(duì)稱正定矩陣，則d（x，B）在（，）的一個(gè)領(lǐng)域內(nèi)有定義且在（）上連續(xù).

命題3[5]算法不會(huì)在（S2）和（S3）之間無(wú)限循環(huán).

命題4[5]算法不會(huì)在（S5）和（S6）之間無(wú)限循環(huán).

命題5算法不會(huì)在（S4）之間無(wú)限循環(huán).

證明由命題3的證明，當(dāng)i充分大時(shí)，有αk，i=.現(xiàn)假設(shè)算法在（S4）之間無(wú)限循環(huán)，則必有tk，i→0，i→∞.而且

令i→∞，有：

由引理1和式（4），可得

但是由（S2），可得

結(jié)合式（9），這與0＜u＜1矛盾，證畢.

命題6[5]算法不會(huì)在（S7）之間無(wú)限循環(huán).

3 超線性收斂性

為證算法具有超線性收斂性質(zhì)，還需作如下假設(shè).

假設(shè)Bi）｛xk｝→；

由命題1，可得以下引理.

引理3（dk，λk）→（0，），在這里，）是問(wèn)題（1）的K－T對(duì)，（dk，λk）是問(wèn)題Q（xk，λk）的K－T對(duì).

證明類似文獻(xiàn)［10］中命題4.1.

引理5假設(shè)｛xk｝為算法在弧式搜索下產(chǎn)生的無(wú)窮序列.若假設(shè)A和假設(shè)B成立，則當(dāng)k充分大時(shí)，步長(zhǎng)tk=1.

證明由引理4和‖dk‖→0，k→∞.當(dāng)k充分大時(shí)，可得：‖‖≤‖dk‖由假設(shè)A ii）可得，當(dāng)k充分大時(shí)，≠0.

結(jié)合命題3和命題5，要證明當(dāng)k充分大時(shí)步長(zhǎng)tk=1，只要證明

成立即可.

因?yàn)椤琩k‖→0，k→∞和引理4，有：

由式（6）和引理3，可得：

由Bk的有界性，引理4以及的定義式（8），有：

由式（4）、（7）和（S2），知：

所以：

因?yàn)閤k→ˉ，λk→和假設(shè)B（ii），可得:

因此當(dāng)k充分大時(shí)：

定理2若引理5條件成立，則｛xk｝超線性收斂于xˉ，即：

證明由文獻(xiàn)［9］中定理12.7.5，有：

由引理5知，當(dāng)k充分大時(shí)，tk=1成立.因此：

4 結(jié)語(yǔ)

在該算法下，類似于文獻(xiàn)［5］可以很容易證明僅在假設(shè)A條件下，該算法具有全局收斂性.但是當(dāng)x不可行時(shí)，如何構(gòu)造一個(gè)更有效的線性規(guī)劃來(lái)求解出搜索方向D（x），還有待于進(jìn)一步研究.

[1] Che Jianren，Su Ke.A modified SQP method and its global convergence[J].Applied Mathematics and Computation，2007（186）：945-951.

[2] Xue Wenjuan,Shen Chungen，Pu Dingguo.A penalty- function- free line search SQP method for nonlinear programming[J].Journal of Computational and Applied Mathematics，2009（228）：313-325.

[3] Zhu Zhibin,Zhang Kecun，Jian Jinbao.An improved SQP algorithm for inequality constrained optimization[J].Mathematical Methods of Operations Research,2003（58）：271-282

[4] Su Ke，Yu Zhensheng.Amodified SQP method with nonmonotone technique and its global convergence[J].Computers and Mathemativs with Applications，2009（57）：240-247.

[5] Zhang Juliang，Zhang Xiangsun.A SQP method for inequality constrained optimization[J].Acta Mathematicae Applicatae Sinica，2002，18（1）：77-84.

[6] Bazaraa M S，Goode J J.An algorithm for solving linearly constraint minimax problem[J].EJOR，1982（11）：158-166.

[7] Zhou Guanglu.A modified SQP method and its global convergence[J].Journal of Global Optimization，1997（11）:193-205.

[8] Facchinei F.Robust recursive quadratic programming algorithm model with global and superlinear convergence properties[J].JOTA，1997（92）:543-579.

[9] 袁亞湘，孫文瑜.最優(yōu)化理論與方法[M].北京：科學(xué)出版社，1997.

[10] DE Q Pantoja J F A.Mayne D Q.Exact penalty function algorithm with simple updating of the penalty parameter[J].JOTA，1991，69（3）:441-467.

A SQP Method for Inequality Constrained Optimization and Its Convergence

XIE Cai-xian，ZHU Ning

(School of Mathematics and Computing Science,Guilin University of Electronic Technology,Guilin 541004,Guangxi，China)

In this paper，a SQP method,in which the merit function is nondifferentiable exactpenaltyfunction，ispresentedtosolveinequalityconstraint.Thepenaltyis adjusted automatically.The arc- search and the second- order correction，which is obtained by solving an auxiliary linear equation system，are used to obtain a feasible descent algorithm.Under some suitable assumptions，it is proved that the convergence of the algorithm is global as well as superlinear.

SQP method；arc- search；nondifferentiable exact penalty function；global convergence；superlinear convergence

O221.2

A

1001-4217（2010）01-0017-07

2009-11-05

解才先（1985-），男，山東臨沂人，碩士研究生.研究方向：優(yōu)化及應(yīng)用.E-mail:xiecaixian1@163.com