一個不等式約束問題的SQP方法及其收斂性

解才先，朱寧

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

一個不等式約束問題的SQP方法及其收斂性

解才先，朱寧

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

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

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

0 引言

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

1 算法模型

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

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

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

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

其中I0（x）=｛j:gj（x）=Φ（x），j∈M∪｛｝0｝，通常來講，Φ′（x；d）是不連續(xù)的.文獻［6］提出了Φ′（x；d）的一個連續(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.

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

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

這里B是一對稱正定矩陣.

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

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

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

（S1）令i:=0和tk，0=1，解式（2）計算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（為方便起見，記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)生一個新的Bk，轉(zhuǎn)（S1）.

2 算法可行性

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

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

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

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

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

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

定理1若算法在（S1）終止于xk，則xk是問題（1）的K－T點.

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

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

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

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

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

令i→∞，有：

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

但是由（S2），可得

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

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

3 超線性收斂性

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

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

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

引理3（dk，λk）→（0，），在這里，）是問題（1）的K－T對，（dk，λk）是問題Q（xk，λk）的K－T對.

證明類似文獻［10］中命題4.1.

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

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

結(jié)合命題3和命題5，要證明當k充分大時步長tk=1，只要證明

成立即可.

因為‖dk‖→0，k→∞和引理4，有：

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

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

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

所以：

因為xk→ˉ，λk→和假設(shè)B（ii），可得:

因此當k充分大時：

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

證明由文獻［9］中定理12.7.5，有：

由引理5知，當k充分大時，tk=1成立.因此：

4 結(jié)語

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

[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].北京：科學出版社，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)化及應用.E-mail:xiecaixian1@163.com