资源描述:
《二阶修正的约束变尺度算法》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库。
1、系统科学与数学‘人二,一二阶修正的约束变尺度算法赖炎连贺国平中国科学院应用数学研究所一、引言,我们知道年代发展起来的约束变尺度算法是求解非线性规划问题的分有效的方法之一它的特点是初始点可任取且有快速的收敛速度若我们考虑如下的非线性规划问题劣,,,,,,‘,一。⋯‘劣,‘,,一,一,,‘,。,,其中了幻幻镇均为上一般的二阶连续可微的实函数则约束变尺,,度方法的基本步骤是在当前的迭代点叙处首先求解下列子问题·,‘‘·,‘了,‘,‘,,专‘君‘,,,,,‘,孟一⋯‘考‘,,’,,。一,⋯,,。,,,其中是对称正定矩阵它是问题的函数的矩,,,了二,二一
2、伪二,二,,二阵的近似垒。一⋯,“,设的解为人相应的乘子向量为则令,,,几。心是从叔出发沿方向人对如下效益函数价劝作某种一维搜索所确定的步长戈,君万,价一一艺艺,。,,,’和对上述基本算法进行了开创性的工作以来获得了许多满意的,结果导出了一系列新的算法但这些算法也还有许多不完善之处最主要的是在解的,,,局部邻域内使用如的效益函数难以避免效应即单位步长不能保证效益函数下降,,,解决上述问题的一个重要途径是采用二阶修正方法如〔和。,〔,,〔‘,,等最近又提出了一个新的二阶修正方法改进了前,面的工作但此算法在每一步都需要求解两个二次子规划以获得搜索方
3、向计算量较大年月日收到现在工作单位山东矿业学院犷期二阶修正的约束变尺度算法,虽然〔中提出一个改进方案但没有收敛性证明,,在本文中我们使用新的线搜索方法将二次规划问题的求解与二阶修正步骤有机地,,结合起来给出了一个新的算法它不需要每一步求解两个子问题但仍较好地克服了效应我们证明了算法的全局收敛性和局部超线性收敛性二、算法及其性质,‘‘二,‘,,沿用的记号以和分别记和为避免效应考虑如下子问题·了“‘·‘,‘,专。二‘‘,,,一一,,,阴专⋯,‘·‘,““,。,‘,一,专,二,解一上述问题的条件可写成。一一‘一一二‘·,‘甲·一““,客客专一合客,‘
4、·,,,’‘劣上‘‘‘,‘一‘一一二。、了二‘‘,粤妻,仁,二‘了,‘,,,十二粤“、一。‘一,‘⋯,、、、、,若令、一,二‘,一,,一产气乏夕,习牙—‘二、十‘二,一二。,,,全粤一⋯协艺,峨心,,“,,“万,这里入是子问题的解护⋯洲是相应的乘子向量当君,幻都是二阶连续可微时可得·,·’“,·气一‘,穿艺专馨二,‘。。分,十。‘。粤毛镇乙于是可得式的一个近似表达式为,一,,一一,习琴分一卷赖炎连贺国平,护,二,穿一⋯‘,‘‘,,穿一娜簇成’‘二,,,,牙牙牙》,一显然上述条件正是如下二次规划问题的条件声’‘’,,,解,,,形’,。脚,,因此若
5、记的解为入则可以期望入将是一个更好的搜索方向,下面我们先定义功叙十刃然后给出一个改进的二阶修正算法令价一二以。‘冬艺,,,,、。艺二艺一一二改进的二阶修正算法步骤。”,,,,,产〔,给定初始点〔选取初始正定矩阵罚因子常数产且那闪丙,取及一“,,入,,,“,步骤设已得叙凡求解子问题设其解向量为心乘子向量为若,,叔一,人则停止即为原问题的点否则转步骤王。,。衣。,步骤令计算一试正,一价牙,拼,,“,产,。示,,,一。,,步骤若入转步骤若令,,,若提灸,今否则“转步骤,,,“一叙口,步骤求解子问题设解为乘子为爪令户心十武一口,计算价叔一价入价一价。,
6、牙,产,,一在,,一二。步骤若则令,,,产,。,一花若提通且。通,否则,入,“转步骤若入脚则令入转步骤,,,“步骤修正凡得一新的正定矩阵凡令友女转步骤,为使上述算法可行我们假定子问题和都是可解的我们不难证明下面两个引理二阶修正的约束变尺度算法一,,,引理设人是子问题的一个点人钾相应的乘子是八满足条件、声,,,全镇提,则币幻和沙幻在点叙沿方向心的方向导数都存在且‘价,‘沙·,其中‘。功一‘,“、一,‘恕‘。·中‘一中,“,一沙、恕一,峨,。,引理设心是子问题的一个点是相应的乘子且沪〔,一,成则对任意的有‘沙、一,以,、丑‘,,巾粤万且功叙随反单调
7、下降,由上述引理由中一功,‘价一价价一价。十。坐︸︺丛匕令价一‘沙。,,两从而可知当入充分小时有内。凌”灸十介花开,因而算法步骤在第步到第步之间不会产生无限循环保证了算法的可行性三、全局收敛性,为了证明全局收敛性我们作如下假设,,。凡对称正定且存在常数使对任意左都有犷罚因子满足条件犷。“,·隆攫于龚牙,,,,,序列都有界,引理价叙口为式所定义则·必,一价‘“一”忽‘,。,。,证用反证法设常数充分小存在使得当及时总有价叙一。,,叙八,试由算法中的性质和价叔十户对八的凸性镬叭镇以及十,算法中两种叙的定义均可得币。一币妻产价一沙爪。赖炎连贺国平卷内叹
8、〔试叙一必八人,,因此当及时·价。一功,产。。,,由引理不难证明价叙是一个单调下降下有界的数列所以习功一币,,·价,一价。一”恕从而有叹又由及消二。一