两类非凸规划问题的优化算法

论文摘要

众所周知,非凸规划问题通常存在多个非全局的局部最优解,增加了求解的难度,是一类典型的NP-难问题.同时,非凸规划问题广泛应用于投资组合与优化,经济,贸易,工程优化设计等领域,吸引了很多研究者的关注.近几年,求解这类模型的多种方法被提出,具体有启发式算法、水平集算法、分支定界算法等.本文针对一类Minimax分式规划问题和一类特殊的DC规划问题,依据模型本身的特点,分别给出了相应的迭代算法和分支定界算法.主要内容如下:第一章,首先给出本文所研究的两种问题模型,然后分别介绍这两种模型的相关背景,理论意义和研究近况,最后简单介绍了本文的主要研究工作.第二章,针对一类Minimax分式规划问题,提出一种迭代算法.首先,通过引入变量将原问题等价转化,其次将等价问题中的约束函数整理成正项式之比的形式,再利用压缩方法,根据选取的不同点y将等价问题压缩为易于解决的几何规划问题.这样,原问题的解就可以通过求解一系列几何规划问题来间接得到.最后,对本章算法的收敛性给出相应的证明过程.数值结果表明该算法是可行有效的.第三章,针对一类特殊的DC规划问题,提出一种分支定界算法.首先,将原问题转化为其等价问题,然后利用凸松弛技巧将等价问题进行松弛,从而确定原问题最优值的下界,通过求解一系列凸规划问题得到原问题的最优解和最优值,同时使用了基于可行性的压缩方法来加速算法的迭代.最后,给出算法的收敛性证明.数值实验结果表明该算法是可行有效的。

论文目录

• 摘要
• ABSTRACT
• 第一章 绪论
•   1.1 问题模型
•   1.2 相关研究
•   1.3 主要内容
• 第二章 一类Minimax分式规划问题的迭代算法
•   2.1 引言
•   2.2 等价问题
•   2.3 压缩方法
•   2.4 算法及其收敛性
•     2.4.1 迭代算法
•     2.4.2 收敛性证明
•   2.5 数值实验
• 第三章 一类特殊DC规划问题的分支定界算法
•   3.1 引言
•   3.2 问题的转化
•     3.2.1 问题的等价转化
•     3.2.2 问题的凸化
•   3.3 算法及其收敛性
•     3.3.1 分支过程
•     3.3.2 压缩过程
•     3.3.3 分支定界算法
•     3.3.4 收敛性证明
•   3.4 数值实验
• 结论
• 参考文献
• 致谢
• 攻读学位期间发表的学术论文目录

文章来源

类型: 硕士论文

作者: 班凤丽

导师: 申培萍

关键词: 分式规划,规划,几何规划,迭代算法,分支定界算法

来源: 河南师范大学

年度: 2019

分类: 基础科学

专业: 数学

单位: 河南师范大学

基金: 国家自然科学基金(11671122)项目

分类号: O221

DOI: 10.27118/d.cnki.ghesu.2019.000704

总页数: 60

文件大小: 1841K

下载量: 17