趙富強(qiáng),曾玲

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

等式約束優(yōu)化一個(gè)新的SQP算法

趙富強(qiáng),曾玲

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

提出了一個(gè)處理等式約束優(yōu)化問題新的SQP算法,該算法通過求解一個(gè)增廣Lagrange函數(shù)的擬New ton方法推導(dǎo)出一個(gè)等式約束二次規(guī)劃子問題,從而獲得下降方向.罰因子具有自動調(diào)節(jié)性,并能避免趨于無窮.為克服M aratos效應(yīng)采用增廣Lagrange函數(shù)作為效益函數(shù)并結(jié)合二階步校正方法.在適當(dāng)?shù)臈l件下,證明算法是全局收斂的,并且具有超線性收斂速度.

等式約束優(yōu)化；SQP算法；等式約束二次規(guī)劃；全局收斂；超線性收斂

1 引言

本文考慮如下優(yōu)化問題

其中f,gj(j∈E)為連續(xù)可微函數(shù).求解問題(1)的SQP方法是一個(gè)迭代算法。即：每一步迭代中其搜索方向dk是通過求解一個(gè)下列形式的二次規(guī)劃所得

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

序列二次規(guī)劃(SQP)算法一直是求解非線形約束優(yōu)化問題的有效方法之一,70年代以來該類算法的研究一直是非線形規(guī)劃研究領(lǐng)域的一個(gè)熱點(diǎn),并出現(xiàn)了大量的研究成果文[1-11].然而SQP方法目前仍面臨著一個(gè)重要的困難:

(1)SQP算法要求迭代過程中每一個(gè)二次規(guī)劃子問題都有解.由于子問題的約束條件是原問題的線形近似,因此而產(chǎn)生的約束區(qū)域可能是空集.

(2)存在Maratos效應(yīng).即:即使迭代點(diǎn)非常接近問題(1)的最優(yōu)點(diǎn)時(shí)也不能保證步長為1.

本文對等式約束優(yōu)化問題進(jìn)一步研究,我們利用文[1]的思想通過求解增廣Lagrange函數(shù)極小點(diǎn)的擬New ton法推導(dǎo)出二次規(guī)劃子問題,這樣可以保證每一步迭代都有可行解dk并且是下降方向.同時(shí)吸收文[3]中罰因子調(diào)整方法,經(jīng)過分析避免罰因子趨于無窮.為克服M aratos效應(yīng),利用增廣Lagrange函數(shù)作為效益函數(shù),同時(shí)結(jié)合二階步校正方法,在適當(dāng)?shù)臈l件下,證明了算法的全局收斂性與超線性收斂性.

2 算法及其理論基礎(chǔ)

3 算法的全局收斂性

4 算法的超線性收斂性

本節(jié)討論算法的超線性收斂性.首先證明算法產(chǎn)生的點(diǎn)列{xk}整列收斂于x?.為此,需另作如下假設(shè):

由引理7及文[9]之定理5.2或文[12]之定理12.3.3知有以下收斂性定理成立.

定理2算法是超線性收斂的,即

心理素質(zhì)包括認(rèn)知、情感、意志、個(gè)性等智力與非智力方面的品質(zhì)，是人的心理能量的體現(xiàn)。學(xué)生的體質(zhì)水平與心理品質(zhì)具有一定程度的正相關(guān)，他們在力量、運(yùn)動速度、耐力、反應(yīng)靈敏性等方面的欠缺，或者跑、跳躍、投擲、攀登、懸垂、支撐等運(yùn)動能力不強(qiáng)，往往影響他們參與其他活動的心理狀態(tài)，使他們表現(xiàn)出畏懼困難、競爭意識不強(qiáng)、團(tuán)隊(duì)意識差、意志品質(zhì)薄弱、心理承受能力差等心理弱點(diǎn)。因此，高職院校體育教育必須以科學(xué)的方式方法培養(yǎng)和訓(xùn)練學(xué)生，使他們具備較強(qiáng)的運(yùn)動能力、良好的心肺功能、健壯勻稱的體格體型，進(jìn)而以獨(dú)特的方式培養(yǎng)學(xué)生良好的心理品質(zhì)，幫助學(xué)生在成長過程中不斷完善自我。

4 數(shù)值實(shí)驗(yàn)

本節(jié)我們用M atlab軟件及其工具箱編程,在一定范圍內(nèi)對實(shí)際例子進(jìn)行數(shù)值試驗(yàn).在以下算例中統(tǒng)一參數(shù)取值為

表1算法A的數(shù)值實(shí)驗(yàn)結(jié)果

參考文獻(xiàn)

[1]王秀國,薛毅.基于增廣Lagrange函數(shù)的RQP方法[J].計(jì)算數(shù)學(xué),2003,11:393-406.

[2]張菊亮,章祥蓀.一個(gè)等式約束問題的SQP方法及其收斂性[J].應(yīng)用數(shù)學(xué)學(xué)報(bào),2001,24(1):1-9.

[3]朱志斌.一般約束最優(yōu)化強(qiáng)收斂的擬乘子-強(qiáng)次可行方向法[J].經(jīng)濟(jì)數(shù)學(xué),2001,18(3):80-87.

[4]聶普炎.等式約束情況下多項(xiàng)式函數(shù)的乘子法[J].云南大學(xué)學(xué)報(bào):自然科學(xué)版,2000,22(3):165-168.

[5]高自友,賀國平,賴炎連.具有相容子問題的序列二次規(guī)劃算法[J].中國科學(xué):A輯,1996,26(11):991-1001.

[6]朱志斌,張可村.不等式約束優(yōu)化一個(gè)新的SQP算法[J].計(jì)算數(shù)學(xué),2004,4:413-426.

[8]Powell M J D,Yuan Y.A recursive quad ratic programming algorithm that uses differentiable exact penalty function[J].M ath.Programming,1986,35:265-278.

[9]Facchinei F,Lucidi S.Quadraticly and superlinearly convergent for the solution of inequality constrained optim ization p roblem[J].JOTA,1995,85(2):265-289.

[10]Zhu Zhibin,Zhang Kecun,Jian Jinbao.An im proved SQP algorithm for inquality constrained optim iza tion[J].Mathem atical methods of Opertions Research,2003,58:271-282.

[11]Zhou G L.A modified SQP method and its global convergence[J].Jouunal of G lobal optim ization,1997,11: 193-205.

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

[13]王宜舉,修乃華.非線形規(guī)劃理論與算法[M].西安:陜西科學(xué)技術(shù)出版社,2004.

[14]Hock W,Schittkowski K.Test Exam p les for Nonlinear Programming Codes[M]//Lecture Notes In Econom ics and Mathem atical System s.Berlin:Springer,1987.

A new SQP algorithm for equality constrainedop timization

ZHAofu-qiang,ZENG Ling

(School of Mathematics and computing Science,Guilin University of Electronic and Technology, Guilin 541004,China)

In this paper,a new SQPm ethod is presented to solve equality constrained optim ization.It obtains descent direction by solving a equality constrained op tim ization subprob lem which is deduced by solving the augm ented Lagrangian in quasi-New ton m ethod.The penalty param eter is ad justed autom atically and avoided tending to infinity.In order to conquer M aratos effect,it takes augm ented Lagrangian as a merit function and combines two-step revised method.Under some suitable assum ptions,we p rove that the algorithm is global convergence as well as superlinear convergence.

equality constrained optim ization,SQP algorithm,equality constrained quadratic programming, global convergence,superlinear convergence

O221.2

A

1008-5513(2009)02-0276-08

2008-06-10.

國家自然科學(xué)基金(10501009),廣西自然科學(xué)基金(0728206).

趙富強(qiáng)(1982-),在讀碩士.研究方向：最優(yōu)化理論與方法.

2000M SC:90C30