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

二阶锥规划的理论与算法研究

作　者: 曾友芳
导　师: 简金宝
学　校: 上海大学
专　业: 运筹学与控制论
关键词: 二阶锥规划理论预估-校正算法光滑化算法收敛性分析
分类号: O221.2
类　型: 博士论文
年　份: 2011年
下　载: 192次
引　用: 0次
阅　读: 论文下载

内容摘要

二阶锥规划是在有限个二阶锥的笛卡儿乘积与仿射子空间的交集上求一个线性目标函数的最小值问题二阶锥规划是锥规划的一个分支，它既是线性规划的推广，又是半定规划的特例，是一种具有优美结构的对称锥规划这类规划应用广泛，比如在设施选址、图论控制优化、天线阵列设计、投资组合问题等方面以及金融、工程设计、数字信号处理、声学、力学、民航、电气等领域都有所应用因此，研究二阶锥规划问题的理论和算法具有重要的理论意义和应用价值二阶锥规划问题的研究起源于17世纪，但直至最近十几年才进入活跃阶段，2fJfJ3年有了对其理论和算法研究的阶段性综述文章对二阶锥规划的算法研究主要分为内点法和非内点法两大类原始一对偶内点法是一类重要的内点法，包含“可行内点法”和"不可行内点法”两种，前者的初始点和迭代点均要求可行，后者的初始点和迭代点只需满足二阶锥约束可行内点法主要有原始一对偶路径跟踪算法，基于核函数的原始一对偶内点算法等不可行内点法常见的有不可行内点预估一校正算法，非精确不可行内点算法等非内点法主要有光滑牛顿法，非内点f内部)连续化方法，序列二次规划法等在较全面了解二阶锥规划研究背景和研究进展的基础上，本文对二阶锥规划的理论和算法进行了深入的研究，并取得如下主要成果：l在12完善了综述性文章中若当代数性质一个重要定理的证明(见定理l 2 3)，提出并证明了若当代数理论的三个新定理f见定理l 2 6一定理l 2 8)2详细分析了2维f每个二阶锥约束都是2维的情形)二阶锥规划转化为线性规划的过程，给出相关的重要性质，并提出了求解2维二阶锥规划的对偶单纯形法和原始一对偶单纯形法，举例说明了算法的有效性并进行了灵敏度分析3基于不可行内点法的优点和预估一校正算法的思想，建立了两个新的求解二阶锥规划的预估一校正算法其预估方向分别是Newton方向和Euler方向，校正方向属于Alizadeh—Haeberly一0verton㈦H0)方向的范畴算法的优点是对于初始内点和迭代内点可行或不可行的情形都适用主要创新点是构造了一个更简单的中心路径的邻域，这不仅与最优性条件切合，而且由此构造的两个新算法能处理较大规模的问题在一些假设条件下，算法具有全局收敛性、线性和二次收敛速度，并获得了0(rln(s。e))的迭代复杂性界，其中r表示二阶锥规划问题所包含的二阶锥约束的个数数值实验结果表明提出的这两个算法是有效的4分别提出了非光滑向量值Fische r_BurmeisterfFB)函数和向量值最小函数的两个新光滑函数，并基于此建立了两个求解二阶锥规划的非内点连续化算法它们的共同优点是：初始点可任取；每次迭代只需求解一个线性方程组得到搜索方向，进行一次线搜索得到步长；在无严格互补假设下，得到算法的全局收敛性和强收敛性而且，证明了基于非光滑FB函数的光滑化算法还具有二次收敛性，并能很好地求解较大规模问题，同时证明了基于向量值最小函数的非内部连续化算法还获得超线性收敛性全文结构如下：第一章对国内外的研究主流和发展现状进行追踪和系统分类描述，并且建立了三个有关若当代数的新定理；第二章提出2维二阶锥规划的对偶单纯形法和原始一对偶单纯形法并进行了灵敏度分析；第三章建立二阶锥规划两个新的预估一校正算法，它们对初始点和迭代点可行或不可行的情况都适用；第四章基于非光滑FB函数的一个新光滑函数建立了光滑化算法，并进行较大规模的数值实验；第五章提出向量值最小函数的一个新光滑函数并基于此建立了具有超线性收敛性的非内部连续化算法；第六章总结全文内容并展望进一步的研究工作

全文目录

摘要  6-8
ABSTRACT  8-11
主要符号说明  11-14
第一章绪论  14-43
  §1.1 二阶锥规划的研究背景  14-28
     1.1.1 数学模型  14-15
     1.1.2 应用简介  15-19
     1.1.3 研究进展  19-28
  §1.2基础知识  28-43
     1.2.1 代数性质  28-40
     1.2.2 对偶性，互补性与最优性  40-41
     1.2.3 算法收敛的定义  41
     1.2.4 牛顿法与欧拉法简介  41-43
第二章 2维二阶锥规划的单纯形类方法  43-56
  §2.1 2维二阶锥规划问题的转化和性质  43-46
  §2.2 2维二阶锥规划的对偶单纯形法  46-50
  §2.3 2维二阶锥规划的原始一对偶单纯形法  50-56
第三章二阶锥规划两个新的预估一校正算法  56-75
  §3.1 引言  56-58
  §3.2 预估一校正算法I  58-61
  §3.3 收敛性分析  61-66
  §3.4 复杂性分析  66-68
  §3.5 预估一校正算法II  68-70
  §3.6 数值实验结果  70-75
第四章二阶锥规划基于非光滑FB函数的一个光滑化算法  75-90
  §4.1 引言  75-78
  §4.2 新光滑函数及其特征  78-82
  §4.3 算法的描述  82-84
  §4.4 收敛性分析  84-87
  §4.5 数值实验结果  87-89
  §4.6 结论  89-90
第五章二阶锥规划一个超线性收敛的非内部连续化算法  90-102
  §5.1 引言  90-91
  §5.2 新光滑函数及其特性  91-95
  §5.3 算法的描述及适定性  95-97
  §5.4 全局收敛性和超线性收敛性  97-101
  §5.5 结论  101-102
第六章总结与展望  102-104
  §6.1 本文工作总结  102-103
  §6.2 研究工作展望  103-104
参考文献  104-121
作者在攻读博士学位期间已发表的论文  121-122
作者在攻读博士学位期间参加或主持的科研项目  122-123
致谢  123-124

二阶锥规划的理论与算法研究

内容摘要

全文目录

相似论文