基于新的搜索方向求解凸二次半定优化问题的内点算法

摘要

自从1984年，著名学者Karmarker提出了势函数投影变换算法—Karmarker算法以来，由于该算法不仅有多项式收敛性，而且具有良好的实际计算效果，备受学者的关注.经过三十几年的研究，关于内点算法的研究已经取得了丰硕的成果.现如今，内点算法已经成功地被推广到求解半定优化(SDO)问题、互补问题、凸二次半定优化(CQSDO)问题、锥规划等优化问题。CQSDO问题是由线性优化和凸二次优化问题推广而来的，由于CQSDO问题在最近关联矩阵问题(Nearest correlation matrix problem)和最近欧拉距离矩阵问题(Nearest Euclidean distance matrix problem)中有着非常重要的作用.因此，研究CQSDO问题有十分重要的意义.本文主要研究了基于新的搜索方向求解CQSDO问题的原始-对偶内点算法，探讨了算法的迭代复杂性，且通过数值实验验证了算法具有良好的实际计算效果。　　本研究分为五个部分：第一章介绍了内点算法相关的一些基本概念、算法模型、产生背景、研究现状以及基本符号约定；第二章提出了基于核函数求解CQSDO问题的大步校正原始-对偶内点算法，给出了算法的迭代复杂性阶，并用数值实例验证了算法有良好的实际计算效果；第三章用新的搜索方向代替经典的牛顿方向，提出了基于核函数求解SDO问题的全-Newton步内点算法，给出了算法迭代复杂性的证明；第四章是将第三章所提出的算法推广到求解CQSDO问题的情形，但本章所定义的邻近度量与第三章不同，通过应用新的技术性结果，我们证明了算法的多项式的迭代复杂性；第五章对本文工作进行总结并对后续研究工作进行了展望。

目录

封面

声明

中文摘要

英文摘要

目录

引言

1 绪论

1.1 基本概念

1.2 内点算法产生的背景

1.3 内点算法的现状分析

1.4 基本记号

2 基于核函数求解CQSDO问题的原始-对偶内点算法

2.1 算法描述

2.2 核函数的性质

2.3 算法分析

2.4 迭代复杂性

2.5 数值实验

2.6 小结

3 基于核函数求解SDO问题的全-Newton步内点算法

3.1 预备知识

3.2 算法描述

3.3 算法分析

3.4 小结

4 基于核函数求解CQSDO问题的全-Newton步内点算法

4.1 算法描述

4.2 算法复杂性分析

4.3 小结

5 全文总结与展望

参考文献

后记

附录：攻读硕士学位期间发表的部分学术论著