几类非凸规划问题的分支定界算法研究

论文摘要

本论文针对几类非凸规划问题,提出了几个基于分支定界的全局优化算法,进行了收敛性分析,并给出了数值实验结果.全文分为四部分,主要内容如下:第一部分针对一类非负二次整数规划问题提出了一个新的矩形分支缩减方法.在这个方法里,给出了一个新的超矩形二分方法和一个新的线性规划松弛定下界的方法,同时为了提高逼近程度和加快收敛速度,使用了超矩形缩减技术.第二部分研究了一类特殊的全局最优化问题—非凸二次规划问题,提出了一个新的矩形分支缩减方法,这个方法中的分支过程采用了新的超矩形二分方法,定界过程是在构造松弛问题的基础上,构造了一个线性松弛定下界的方法;为了提高逼近程度,加快收敛速度,分支定界算法采用了超矩形缩减技术.第三部分研究了一类带有二次约束的二次规划问题的分支定界算法,分支及缩减过程同上,构造了一个新的线性松弛定下界方法.第四部分利用对数函数的性质将一类多乘积规划问题等价地转化为一个凹最小问题.针对这个问题的凹和特殊结构,利用单纯形上凹函数凸包络的线性性质,给出了线性规划松弛问题以确定原问题最优值的下界,由此提出了一类多乘积规划问题的单纯形分支定界算法,并且给出了收敛性证明.数值例子表明所提出的算法是可行的和有效的.

论文目录

• 摘要
• Abstract
• 第1章 绪论
• 1.1 课题的研究背景和意义
• 1.2 国内外研究现状
• 1.3 本文的研究目的和研究内容
• 1.3.1 本文的研究目的
• 1.3.2 本文的主要研究内容
• 1.3.3 本文的篇章结构
• 第2章 分支定界算法概述
• 2.1 引言
• 2.2 分支定界算法的基本思想
• 2.3 分支节点的选择
• 2.4 算法流程
• 2.5 分支定界法的算法分析
• 第3章 二次整数规划
• 3.1 引言
• 3.2 问题的等价形式
• 3.3 定界技术
• 3.4 整超矩形的剖分与缩减
• 3.4.1 整超矩形的剖分
• 3.4.2 整超矩形的缩减
• 3.5 超矩形分支定界算法
• 3.6 数值实验
• 3.7 本章小结
• 第4章 带有线性约束的非凸二次规划
• 4.1 引言
• 4.2 问题的等价转化
• 4.3 定界技术
• 4.4 超矩形的剖分与缩减
• 4.4.1 超矩形的剖分
• 4.4.2 超矩形的缩减
• 4.5 算法描述及收敛性分析
• 4.6 数值分析
• 4.7 本章小结
• 第5章 带有二次约束的二次规划
• 5.1 引言
• 5.2 定界技术
• 5.3 算法描述及收敛性分析
• 5.4 数值例子
• 5.5 本章小结
• 第6章 多乘积规划
• 6.1 引言
• 6.2 等价问题及其线性规划松弛
• 6.3 单纯形分支定界算法及其收敛性分析
• 6.3.1 算法描述
• 6.3.2 收敛性分析
• 6.4 数值例子
• 6.5 本章小结
• 第7章 研究工作总结及展望
• 7.1 研究工作的总结
• 7.2 未来的工作展望
• 参考文献
• 致谢
• 攻读硕士期间撰写的论文、参与的项目及作者简介
• 1 硕士期间撰写的论文
• 2 在校期间参与的科研项目
• 3 作者简历