一个无惩罚型原始对偶内点算法及其收敛性分析-论文.pdf

《一个无惩罚型原始对偶内点算法及其收敛性分析-论文.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第37卷第3期应用数学学报Vo1．37No．32014年5月ACTAMATHEMATICAEAPPLICATAESINICAM，2014一个无惩罚型原始对偶内点算法及其收敛性分析邱松强(中国矿业大学理学院数学系，徐州221116)(E—mail：sqqiu~cumt．edu．ca)陈中文(苏州大学数学科学学院，苏州215006)(E—mail：zwchen@suda．edu．cn)摘要本文提出一个新的无惩罚型原始对偶内点算法，区别于罚函数法和滤子法，新算法通过对尝试点的不可行性的控制来确保算法的全局收敛性．算法首先求解—个线性系统获得搜索方向，然后根据当前迭代点的最优性度量和可行性度量

2、之间的关系来确定当前是优先改善可行性度量还是改善最优性度量，最后利用直线搜索法确定步长．新算法没有使用专门的可行性恢复过程，在通常的假设条件下，我们分析了新算法的全局收敛性，给出了初步的数值实验结果．关键词无惩罚型方法；原始对偶内点法；障碍函数；全局收敛性MR(2000)主题分类65K05；90C30中图分类02241引言本文讨论如下形式的优化问题rain，()，s．t．c(x)=0(1．1)X>0．其中，f(x)：R一R，c(x)：R”一R均为二次连续可微函数．一般约束优化问题可以通过引入松弛变量转化为问题(1．1)的形式．本文2012年5月14日收到．2012年8月15日收到修改稿

3、．国家自然科学基金(11371273)及中央高校基本科研业务费专项资金(2013XK03)资助项目424应用数学学报37卷在过去20多年里，内点法或者障碍函数法在非线性规划中的应用已经引起了广泛的关注并且取得了很多成果．对于内点法的收敛性现在已经有了很好的理解出现了很多有效的算法，其中一些算法已经被应用到一些软件中去，如『2,31等．大体上，依据其计算尝试步的框架，内点法可分为信赖域内点法[4，5]和线性搜索内点法，6，]两大类．算法的全局化手段，可以分为惩罚型和无惩罚型两大类．惩罚型内点算法的研究比较多，如[2，4，6，7]等，无惩罚型内点算法中过滤内点法居多，比如[8]和【9]，基

4、于无惩罚无滤子技术的内点法的成果比较少，f101给出了一种利用类似于Gould和Toint的trustfunnel技术的无惩罚型内点算法．本文提出一种新的基于障碍函数框架的线性搜索无惩罚型内点算法，与已有的内点算法相比，本文算法的一个显著特点是既不使用精确罚函数也不使用滤子技术，而是采用类似fl0]和[11]中的全局化技术．在迭代过程中，算法要求迭代点的可行性违反度不超过一个递减的上界序列．通过比较当前点的可行性度量和最优性度量决定减小目，J标函数值或改善可行性．本文算法与文[11]的算法相比，主要有以下几点区别：(1)本文算法首先求解一个线性系统获得搜索方向后，再根据当前迭代点的最优

5、性度量和可—行性度量之间的关系，确定优先改善可行性还是改善最优性，而f11]的算法中最优性度量是在获得法向步后计算并且随着法向步的变化而变化；(2)本文算法每次迭代只计算∑一个搜索方向，而『111的算法需将尝试步分解为法向步和切向步；(3)这两个算法接受尝试步的准则不同．与[10]的算法相比，二者的区别主要是：(1)本文算法使用障碍函数法框架，【101的算法使用中心邻域法框架；(2)本文算法每次迭代只求解一个线性系统，『10]的算法每次迭代需求解两个线性系统；(3)两者接受尝试步的准则不同；(4)本文算法不需要借助专门的可行性恢复程序，[10]的算法需要调用可行性恢复算法．2主算法框架

6、根据内点法的一般框架，我们将问题(1．1)和一个障碍函数优化问题联系起来rain“()(2．1)s．t．c(z)=0问题(2．1)的Lagrange函数是L(x，)=()+ATc()=，()一∑inxt+c()仁=1其中，∈R是Lagrange乘子．如果是(2．1)的一个最优解，那么我们有“()+c()=0，c(5)=03期邱松强，陈中文：一个无惩罚型原始对偶内点算法及其收敛性分析425或者等价地『Vf(x)+c()—z]l【c()I=0，(2．2)XZe—ej其中，是相对-f约束0的Lagrange乘子，e=(1，⋯，lX：diag(xl，⋯，)，z=diag(z一，)．内点法选择一

7、个单调不增趋于0的序列{)，通过近似地求解一系列障碍函数优化问题(=)来获得原问题的解．我们分别定义障碍函数问题和原问题的残量II『l厂()+c()(，，)：⋯c()XZe一el1『Vf(x)+c()Eo(x，，)=⋯c()XZe为了叙述方便，从现在开始，我们将一个由多个部分组成的向量，比如(XT，T，ZT)T简写成(，A，)．用％表示第k次迭代对应的迭代点，表示向量Xk的第i个分1●●●●●●j]●●●●●●j量，fk=f(x)，c=c()，