锥规划的核函数全牛顿步内点算法研究_第1页
锥规划的核函数全牛顿步内点算法研究_第2页
锥规划的核函数全牛顿步内点算法研究_第3页
全文预览已结束

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

1、锥规划的核函数全牛顿步内点算法研究众所周知,原-对偶内点算法是求解线性规划问题最有效的算法之一。2001年以前,几乎所有的原-对偶内点算法都是采用牛顿方向作为搜索方向,这种搜索方向和原-对偶对数障碍函数有密切联系。通过替换对数障碍函数为新的核函数障碍函数,可以得到新的搜索方向并设计核函数内点算法。基于核函数的e-凸性在设计大步可行内点算法中大大简化算法分析的作用,本文将核函数的e-凸性引入线性规划的全牛顿步可行算法设计,接着给出线性规划基于核函数的全牛顿步不可行内点算法,并推广到半正定规划,就设计新算法和复杂性分析进行研究。首先,给出了线性规划基于有限障碍核函数的全牛顿步可行算法。不仅仅将核函

2、数用来确定搜索方向,更为重要的是,将核函数的性质特别是e-凸性用于全牛顿步内点算法分析,简化了算法复杂性分析过程,并且算法得到了同迄今为止可行内点算法最好的复杂性一致的结果。接着,根据大步核函数内点算法框架研究了所讨论核函数的特点,明确指出其不可用于大步内点算法设计。实际上,此类核函数刚好可以用于设计全牛顿步内点算法,并且具有巨大的优势。为得到更好的数值表现,对核函数确定的搜索方向进行改进,定义新的宽邻域,结合经典宽邻域内点算法,给出了基于核函数的宽邻域内点算法。虽然理论复杂度较全牛顿步内点算法有所提高,但是数值实验显示了其优越性,弥补了核函数全牛顿步内点算法在数值表现上的不足。其次,基于简单

3、的核函数设计了线性规划的新的不可行内点算法。传统的全牛顿步不可行内点算法理论上有优势,但是所采用的传统牛顿方向和临近度量使得算法分析复杂。新的简单核函数不仅仅用于构造搜索方向和二次收敛域,其性质特别是e-凸性的引入使得全牛顿步不可行内点算法的复杂性分析大大简化,并且算法得到了线性规划同迄今为止最好的不可行内点算法复杂性一致的结果。进一步,借助于核函数矩阵函数的定义以及矩阵分析工具,将求解线性规划问题基于简单函数的全牛顿步不可行内点算法推广到求解半正定规划问题中,在保持同迄今为止最好的不可行内点算法复杂性一致的结果的同时同样大大简化了传统半正定规划全牛顿步不可行内点算法的复杂性分析。最后,借助于在执行可行步之后寻找更低的临近度量的估计,用来简化全牛顿步不可行内点算法复杂性分析,即去除中心步的思想,针对半正定规划问题,对核函数所确定的搜索方向进行改进,使得可行步跟踪下一扰动问题的障碍参数更新后的中心路径,设计了新的全牛顿步不可行内点算法.该算法只需要执行可行步,不需要任何中心步,复杂性分析简化的同时得到了和线性规划问题不可行内点算法迄今为止最好的复杂性一致

人人文库> 全部分类> 行业资料 > 管理策划

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论