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

基于D.C.分解的非凸二次规划SDP近似算法

作　者: 王延菲
导　师: 孙小玲
学　校: 复旦大学
专　业: 运筹学与控制论
关键词: 非凸二次规划问题凸二次约束最优D.C.分解 SDP松弛下界近似最优解随机化方法
分类号: O221.2
类　型: 硕士论文
年　份: 2010年
下　载: 70次
引　用: 0次
阅　读: 论文下载

内容摘要

非凸二次规划是一类重要的最优化问题,在工程、经济管理和金融优化等领域有广泛的应用,如生产计划问题,规模效益问题,工程设计与控制中的问题,许多具有挑战性的NP-难非凸优化问题和组合优化问题都可以表示为非凸二次规划问题.本文研究凸二次约束非凸二次规划问题,并提出一类基于D.C.分解的SDP松弛方法,该方法通过目标函数的D.C.分解和对凹函数进行线性逼近来构建原问题的凸松弛.本文考虑了两种D.C.分解方法：第一种是利用一组非零向量构造目标函数的D.C.分解,并对凹部分线性逼近；第二种是利用约束系数矩阵的正交变换构造目标函数的D.C.分解,并对凹部分进行分段线性逼近.我们证明了通过最优D.C.分解可以得到原问题的SDP松弛,并证明所得到的SDP界比经典的SDP界更紧.本文提出的D.C.分解方法的另一个优点是可以在得到SDP界的同时通过求解一个二阶锥规划得到原问题的一个近似最优解.数值结果表明,本文提出的SDP松弛可以产生比典型SDP松弛更紧的界,同时,数值结果还表明,基于SDP松弛的近似算法可以得到比传统随机化算法更好的近似最优解.本文分为五个部分.第一部分介绍非凸二次规划问题的研究背景与本文的主要工作.第二部分介绍非凸二次规划问题的现有算法,主要包括分支定界算法,半定规划松弛,以及基于半定规划松弛的随机化近似算法.第三部分是本文的主要结果,我们提出基于D.C.分解的SDP松弛方法.第四部分给出了基于D.C.分解的SDP松弛和近似算法的数值结果与数值分析.第五部分是全文的总结.

全文目录

摘要  5-6
Abstract  6-9
第一章前言  9-13
  §1.1 问题的提出  9
  §1.2 研究现状概述  9-12
  §1.3 本文的主要结果  12-13
第二章非凸二次规划现有算法综述  13-23
  §2.1 分枝定界算法  13-14
  §2.2 半定规划松弛  14-16
  §2.3 基于半定规划的随机化近似算法  16-23
    2.3.1. 最大割问题  17-19
    2.3.2. 无约束(-1,1)非凸二次规划问题  19-20
    2.3.3. 一般非凸二次规划问题  20-23
第三章基于D.C.分解SDP松弛方法  23-33
  §3.1 一类参数D.C.分解  23-26
  §3.2 两种特殊D.C.分解方法  26-28
    3.2.1. 对角扰动D.C分解  26-27
    3.2.2. 正交变换D.C.分解  27-28
  §3.3 基于系数矩阵Q,的D.C.分解  28-33
第四章数值结果与分析  33-41
  §4.1 凸二次约束问题的数值结果  33-34
  §4.2 凸二次和线性约束问题的数值结果  34-41
第五章结论  41-42
参考文献  42-47
致谢  47-48

基于D.C.分解的非凸二次规划SDP近似算法

内容摘要

全文目录

相似论文