求解新的锥模型信赖域子问题的半正定松弛算法研究

论文摘要

随着信赖域方法的快速发展和对其应用前景的日益重视,国内外对于信赖域的改进算法的研究越来越多、越来越深入。在信赖域子问题中利用锥模型代替普通的二次模型的做法近年来受到很大的关注,如何求解这样一个模型也成为了亟待解决的问题。在本文中我们尝试应用半正定松弛技术解决这一难题。本文主要探讨的是带锥模型的信赖域子问题的求解。我们针对具有良好定义的新型锥模型信赖域子问题,提出了一个能有效地解决此问题的算法：首先把原始的锥模型信赖域子问题(P)划分为两个数学规划(P1)和(P2)的合集；通过将规划(P1)齐次化,可以知道(P1)等价于一个二次规划问题；这个二次规划经过进一步转化成半正定规划(CP)的形式,从而可以运用半正定松弛算法求解,并且利用求得的解通过我们构造的一个回溯算法可以得到问题(P1)的解。值得注意的是,经过证明可以得到之前的半正定松弛是紧的,也就是说松弛后的问题的最优解与松弛前的问题的最优解没有间隙,它们是相等的。应用类似的方法可以得到问题(P2)的解,在(P1)的解与(P2)的解之中使得原问题(P)的目标函数取值较小的解即为此锥模型信赖域子问题的最优解。我们对算法进行了数值试验,证明了我们的算法是高效的。

论文目录

摘要

ABSTRACT

第一章序言

1.1 锥模型背景介绍

1.2 半正定松弛技术

1.3 软件工具

1.4 论文的主要工作

第二章相关预备知识

2.1 凸理论

2.2 KKT最优性条件

2.3 信赖域方法

2.4 半正定规划

2.5 本章小结

第三章求解新锥模型信赖域子问题的主要理论结果

3.1 等价的齐次化问题

3.2 问题的半正定规划形式

3.3 锥模型信赖域子问题求解的主要定理

3.3.1 强可行条件

3.3.2 紧松弛与回溯过程

3.4 本章小结

第四章算法设计与数值实验

4.1 算法原理及具体流程

4.1.1 算法4.1

4.1.2 算法4.2

4.2 数值实验及其结果

4.2.1 对算法4.1的数值实验

4.2.2 对算法4.2的数值实验

4.3 本章小结

第五章总结与展望

参考文献

附录

致谢

作者攻读学位期间发表的学术论文目录

求解新的锥模型信赖域子问题的半正定松弛算法研究

论文摘要

论文目录

相关论文文献