学位论文 > 优秀研究生学位论文题录展示
几类非凸规划问题的分支定界算法研究
作 者: 魏飞
导 师: 高岳林
学 校: 北方民族大学
专 业: 计算数学
关键词: 全局优化 非凸二次规划 带有二次约束的二次规划 多乘积规划 分支定界方法
分类号: O221
类 型: 硕士论文
年 份: 2011年
下 载: 96次
引 用: 0次
阅 读: 论文下载
内容摘要
本论文针对几类非凸规划问题,提出了几个基于分支定界的全局优化算法,进行了收敛性分析,并给出了数值实验结果.全文分为四部分,主要内容如下:第一部分针对一类非负二次整数规划问题提出了一个新的矩形分支缩减方法.在这个方法里,给出了一个新的超矩形二分方法和一个新的线性规划松弛定下界的方法,同时为了提高逼近程度和加快收敛速度,使用了超矩形缩减技术.第二部分研究了一类特殊的全局最优化问题—非凸二次规划问题,提出了一个新的矩形分支缩减方法,这个方法中的分支过程采用了新的超矩形二分方法,定界过程是在构造松弛问题的基础上,构造了一个线性松弛定下界的方法;为了提高逼近程度,加快收敛速度,分支定界算法采用了超矩形缩减技术.第三部分研究了一类带有二次约束的二次规划问题的分支定界算法,分支及缩减过程同上,构造了一个新的线性松弛定下界方法.第四部分利用对数函数的性质将一类多乘积规划问题等价地转化为一个凹最小问题.针对这个问题的凹和特殊结构,利用单纯形上凹函数凸包络的线性性质,给出了线性规划松弛问题以确定原问题最优值的下界,由此提出了一类多乘积规划问题的单纯形分支定界算法,并且给出了收敛性证明.数值例子表明所提出的算法是可行的和有效的.
|
全文目录
摘要 4-5 Abstract 5-8 第1章 绪论 8-14 1.1 课题的研究背景和意义 8-10 1.2 国内外研究现状 10-11 1.3 本文的研究目的和研究内容 11-14 1.3.1 本文的研究目的 11-12 1.3.2 本文的主要研究内容 12 1.3.3 本文的篇章结构 12-14 第2章 分支定界算法概述 14-17 2.1 引言 14 2.2 分支定界算法的基本思想 14 2.3 分支节点的选择 14-15 2.4 算法流程 15-16 2.5 分支定界法的算法分析 16-17 第3章 二次整数规划 17-34 3.1 引言 17 3.2 问题的等价形式 17-19 3.3 定界技术 19-21 3.4 整超矩形的剖分与缩减 21-23 3.4.1 整超矩形的剖分 21-22 3.4.2 整超矩形的缩减 22-23 3.5 超矩形分支定界算法 23-25 3.6 数值实验 25-32 3.7 本章小结 32-34 第4章 带有线性约束的非凸二次规划 34-51 4.1 引言 34 4.2 问题的等价转化 34-35 4.3 定界技术 35-37 4.4 超矩形的剖分与缩减 37-39 4.4.1 超矩形的剖分 37-38 4.4.2 超矩形的缩减 38-39 4.5 算法描述及收敛性分析 39-42 4.6 数值分析 42-50 4.7 本章小结 50-51 第5章 带有二次约束的二次规划 51-58 5.1 引言 51 5.2 定界技术 51-53 5.3 算法描述及收敛性分析 53-55 5.4 数值例子 55-57 5.5 本章小结 57-58 第6章 多乘积规划 58-66 6.1 引言 58-59 6.2 等价问题及其线性规划松弛 59-61 6.3 单纯形分支定界算法及其收敛性分析 61-63 6.3.1 算法描述 61-63 6.3.2 收敛性分析 63 6.4 数值例子 63-65 6.5 本章小结 65-66 第7章 研究工作总结及展望 66-68 7.1 研究工作的总结 66 7.2 未来的工作展望 66-68 参考文献 68-72 致谢 72-73 攻读硕士期间撰写的论文、参与的项目及作者简介 73 1 硕士期间撰写的论文 73 2 在校期间参与的科研项目 73 3 作者简历 73
|
相似论文
- 非凸规划组合同伦算法复杂性分析,O224
- 两类非凸全局优化问题的分支定界算法,O224
- 二次规划及多目标规划的全局最优性条件,O221
- 比式和问题的全局优化算法,O224
- 求解非线性规划问题的两种方法,O221.2
- 基于Kriging模型的全局优化方法研究,TH122
- 团簇基态结构预测的高效启发式算法,O561
- 单目标_多目标遗传算法的研究,TP18
- 全局优化理论几种算法的改进与研究,O224
- 基于遗传算法的组卷系统的研究与应用,O224
- 基于食物链生态进化算法的输电网扩展规划,TM715
- 融合粒子群的全局优化混合智能算法研究,TP18
- 功率半导体器件版图拼接技术研究,TN303
- 基于视觉认知的全局优化算法,TP301.6
- 求解全局优化问题的可视化算法,O224
- 基于待消解项识别的全局优化共指消解方法研究,TP391.1
- 新一代电梯的调度算法研究,TU857
- 改进的差异进化算法求解高维全局优化问题研究,TP18
- 基于D.C.分解的非凸二次规划SDP近似算法,O221.2
- 有约束的连续规划问题的填充函数方法,O221
- 几类二次约束二次优化问题的全局最优性条件,O224
中图分类: > 数理科学和化学 > 数学 > 运筹学 > 规划论(数学规划)
© 2012 www.xueweilunwen.com
|