二次分式规划问题的理论与算法研究

论文摘要

分式规划是一类重要的非线性数学规划问题,目前已广泛地应用于经济金融、图像处理、投资组合等领域,本文主要研究两类分式规划问题:带有单边二次约束的二次分式规划和带有双边二次约束的二次分式规划。其中双边约束问题是单边约束问题的更一般形式,本文着重研究单边约束问题,并尝试将单边约束问题的结论和算法推广到双边约束问题。二次分式规划的目标函数的非凸性质,对求解这一类问题的全局最优解造成了一定的困难,目前已知的算法中主要分为两大类。一类是利用Dinkelbach参数化技巧求解一系列的QCQP问题;另一类方法是将先问题转化为SDP问题,求出原问题的最优值,然后再求解一个QCQP问题。遗憾的是,这两类算法的计算复杂度较高,不适合处理较大规模的问题。本文提出了一个求解带有二次约束的二次分式规划问题的非常有效率的算法。本文从研究它的Lagrange对偶问题入手,估计出最优Lagrange乘子的上界和下界,并且证明了原问题与对偶问题的强对偶性。利用二分法近似求解最优Lagrange乘子的值,每一步只需求解一个最小特征值或最小广义特征值问题,进而可以求解出二次分式规划问题的全局最优解。由于本算法只需求解最小特征值问题,所以对于大规模的稀疏问题此算法的计算效率是非常高的,本文的数值实验证明了此算法的正确性,并且表明相比于其它算法在计算复杂度方面具有极大的优势。

论文目录

• 摘要
• abstract
• 第一章 绪论
•   1.1 研究背景和研究意义
•   1.2 几类二次分式规划问题的研究现状
•     1.2.1 单边约束
•     1.2.2 双边约束
•     1.2.3 多个约束
•   1.3 本文的主要工作
•   1.4 本文的结构安排
• 第二章 预备知识
•   2.1 S-引理
•   2.2 次微分和次梯度
•   2.3 特征值问题
• 第三章 带有单边约束的二次分式规划问题
•   3.1 Lagrange对偶问题
•     3.1.1 强对偶性
•     3.1.2 最优乘子区间
•     3.1.3 对偶函数的次梯度
•   3.2 线性时间算法
•     3.2.1 最小化特征值子问题
•     3.2.2 更新二分搜索区间
•     3.2.3 讨论
•   3.3 时间复杂度分析
•   3.4 数值实验
•     3.4.1 工具包简介
•     3.4.2 实验环境和实验参数设置
•     3.4.3 实验结果
• 第四章 带有双边约束的二次分式规划问题
•   4.1 Lagrange对偶问题
•     4.1.1 强对偶性
•     4.1.2 最优乘子区间
•     4.1.3 对偶函数的次梯度
•   4.2 算法
•   4.3 数值实验
•     4.3.1 实验结果
• 第五章 总结
• 参考文献
• 致谢
• 在硕士期间发表的学术论文
• 附录

文章来源

类型: 硕士论文

作者: 马腾飞

导师: 王丽平

关键词: 二次分式规划,线性时间算法,全局优化,强对偶,二分法

来源: 南京航空航天大学

年度: 2019

分类: 基础科学

专业: 数学

单位: 南京航空航天大学

分类号: O221.2

DOI: 10.27239/d.cnki.gnhhu.2019.001021

总页数: 58

文件大小: 2215K

下载量: 44