pk线性互补问题的mehrotra型预估校正算法分析及拓展

(69页)

'pk线性互补问题的mehrotra型预估校正算法分析及拓展'
AbstractInterior-point algorithm, as one of the most efficient algorithms, not only has polynomial complexity, but also has superior practical performance. Since the first practical polynomial interior-point algorithm was presented by Karmarkar in 1984, the researches on Interior-Point Methods (IPMs) has achieved fruitful result. At present, interior-point algorithms are successfully used for solving Linear Programming, Convex Programming, Complementarity Problems, Semi-definite Programming and Second?order Cone Optimization. Several powerful IPMs based optimization packages have been developed and widely used.This thesis is devoted to studying Mehrotra-type predictor-corrector algorithms for ? (k) complementarity problems. Complementarity problem is a class of the widely used mathematical problems, which has important applications in engineering, economic analysis and traffic equilibrium. Therefore, it is significant to study the algorithms for solving the ?(k) complementarity problems. The thesis majors in researching on Mehrotra-type predictor-corrector algorithms for E(k) linear complementarity problem and 尺(k) nonlinear complementarity problems. Three new algorithms are presented and the polynomial complexity of them is proved.The thesis contains four chapters. Chapter one introduces some preliminary knowledge and research backgrounds. Chapter two presents a Mehrotra-type predictorcorrector algorithm for R(k) linear complementarity problem, the polynomial complexity of which is given. A numerical experiment verifies the efficiency of the algorithm. In Chapter three, two Mehrotra-type predictor-corrector algorithms based on "safety strategy^ are given, one for solving monotone nonlinear complementarity problem and another for /i (k ) nonlinear complementarity problem. With the assumption of the Scaled Lipschitz Condition, we proved the polynomial complexity of the algorithms. Finally, a conclusion is made regarding the discuss topic together with the further expectation in Chapter four.Key words: interior-point algorithm complementarity problem Mehrotra- type predictor-corrector algorithm polynomial complexity目 录弓丨言 11绪论 21.1互补问题简介 21.2内点算法的产生与发展概况 21.3 基本概念及符号约定 42 R(k)线性互补问题的Mehrotra型预估-校正算法 62.1 ?(k)线性互补问题介绍 62.2算法描述 72.3算法复杂性分析 92.4数值实验 212.5小结 223非线性互补问题的Mehrotra型预估■校正算法 233.1引言 233.2预备知识 233.3单调非线性互补问题的Mehrotra型预估■校正算法 243.4 ?(k)非线性互补问题的Mehrotra型预估■校正算法 343.5小结 434全文总结与展望 44参考文献 45后记 51附录:攻读硕士学位期间发表的部分学术论著 52引言最优化是一门应用非常广泛的学科,它是研究在有限种或无限种可行方案中挑选 最优方案,构造寻求最优解的计算方法.随着科学技术的飞速发展,最优化方法作为 一个重要的数学分支,广泛地应用于社会生活的各个方面.生产计划安排、工程设计 参数选取、资源分配、城市规划、军事指挥等等都离不开最优化.而互补问题作为一 类非常重要的优化问题,在力学、金融交通平衡、最优控制等众多领域都有广泛应用. 因此,对互补问题的研究无论从理论上还是从实际应用上讲都有着非常重要的意义.内点算法自1984年由Karmarkar11JLU来,便成为优化领域的研究热点之一.经过 二十多年的研究,线性规划的内点算法取得了丰硕的成果,并已被成功推广到凸规划、 互补问题、半定规划、二阶锥规划等各类优化问题.在多种内点算法中,预估■校正算 法是最有效的内点算法之一,被广泛应用于优化软件包的开发.其中,Mehrotra型预 估■校正算法⑵因在预估步和校正步使用相同的系数矩阵,对求解大型问题有显著优 势by由于其良好的实际计算效果,Mehrotra型预估■校正算法成为众多优化软件包 的算法基础
关 键 词:
pk 线性 互补 问题 mehrotra 预估 校正 算法 分析 拓展
 剑锋文库所有资源均是用户自行上传分享,仅供网友学习交流,未经上传用户书面授权,请勿作他用。
关于本文
本文标题:pk线性互补问题的mehrotra型预估校正算法分析及拓展
链接地址: //www.wenku365.com/p-43709356.html
关于我们 - 网站声明 - 网站地图 - 资源地图 - 友情链接 - 网站客服点击这里,给剑锋文库发消息,QQ:1290478887 - 联系我们

本站为“文档C2C交易模式”,即用户上传的文档直接卖给(下载)用户,本站只是中间服务平台,本站所有文档下载所得的收益归上传人(含作者)所有【成交的100%(原创)】。本站是网络服务平台方,若您的权利被侵害,侵权客服QQ:1290478887 欢迎举报。

1290478887@qq.com 2017-2027 //www.wenku365.com 网站版权所有

粤ICP备19057495号 

收起
展开