学位论文 > 优秀研究生学位论文题录展示

非凸规划组合同伦算法复杂性分析

作　者: 刘巍
导　师: 刘庆怀
学　校: 长春工业大学
专　业: 应用数学
关键词: 非凸优化组合同伦方法复杂性分析全局优化
分类号: O224
类　型: 硕士论文
年　份: 2011年
下　载: 32次
引　用: 0次
阅　读: 论文下载

内容摘要

优化是一门应用相当广泛的学科,其方法已普遍用于科学、工程与经济等重要领域,成为政府部门、科研机构和产业部门进行科学决策的有力工具。非凸优化问题的有效解法与复杂性分析研究是重要的研究方向。复杂性理论结果对算法的使用和发展具有一定的启示作用。复杂性理论领域一方面设计和分析有效算法,另一方面从两个对立的角度来看待算法问题。一个有效的算法,可直接用于解决问题,并且其本身就是问题的有效的可解性的证明。相反,复杂性理论的目标是证明难的问题不能用有限的资源量来解决。现有的大多数关于约束优化的算法都只能求出局部极小点(或稳定点),而诸多的实际问题都要求得到全局极小点。我们借鉴全局优化中的某些方法(填充函数法、打洞函数法),融水平值下降思想,对一类非凸优化问题的全局算法进行了研究。我们知道,用组合方法研究凸规划时发现,无需增加其它条件(与解存在性条件相同)便可得到相应算法的大范围收敛性；而且在通常假设条件下(自和谐条件),通过分段分析技巧,克服了组合同伦路径不单调所带来的困难,得到了与其它内点法类似的多项式复杂度估计,同时也相应地对线性互补问题与非线性互补问题的复杂性估计也已得到了类似成果。但对非凸情形该算法的复杂度还无任何结果,对此进行研究十分必要。本文首先研究了可行域满足法锥条件的非凸规划组合同伦算法的复杂性,在平凡的条件下(假设目标函数在一个大的范围内有界),证明了解非凸规划的组合同伦算法的复杂性。其次,利用了多项式第二判别矩阵,基于水平值下降思想,构建了多项式函数极小化问题的全局优化算法,数值实验表明新的算法十分有效。

全文目录

摘要  2-3
Abstract  3-4
目录  4-5
第一章绪论  5-12
  1.1 复杂性理论产生背景及研究现状  5-6
  1.2 内点算法的产生背景及研究现状  6-8
  1.3 组合同伦算法的发展及研究现状  8-10
  1.4 全局优化算法的发展及研究现状  10-11
  1.5 本文主要内容及章节安排  11-12
第二章预备知识  12-15
  2.1 组合同伦算法简介  12-13
  2.2 全局优化相关知识  13-14
  2.3 本章小结  14-15
第三章法锥条件下非凸规划的组合同伦算法复杂性分析  15-24
  3.1 基本算法与假设条件  15-19
  3.2 非凸规划同伦算法复杂性分析  19-22
  3.3 数值算例实验  22-24
第四章多项式函数极小化问题的全局优化算法  24-28
  4.1 引言与问题提出  24
  4.2 基本概念与基本定理  24-26
  4.3 算法步骤  26-27
  4.4 算法收敛性分析及算例实验  27-28
第五章总结及展望  28-29
  5.1 研究结果总结  28
  5.2 研究展望  28-29
致谢  29-30
参考文献  30-33
附录  33-39
作者简介  39
攻读硕士学位期间研究成果  39-40

非凸规划组合同伦算法复杂性分析

内容摘要

全文目录

相似论文