论文部分内容阅读
本文主要研究最优低秩相关系数矩阵问题及与其相关的两类问题:带简单上界约束的最优相关系数矩阵问题和具有因子结构的最优相关系数矩阵问题.
最优低秩相关系数矩阵问题来源于金融领域,在组合优化、机器学习、数据分析等方面也有重要应用.目前已经有很多方法可以来求解它.其中,优化算法是很受欢迎的一种方法.在本文的第二章到第四章中,我们将提出序列半光滑牛顿算法.由于该问题是一个非凸约束优化问题,为了处理非凸的秩约束条件,在第二章中,我们首先将原问题转化为一个等价的非线性半定规划问题(NSDPr).这主要是基于一个著名的结果:对称矩阵的前r个最大特征值之和可以写成一个半定规划问题.(NSDPr)也是一个非凸优化问题,它含有两个矩阵变量和三个对称半正定锥约束.为避免直接求解,我们通过求解一系列最小二乘子问题来求解(NSDPr),称之为外层算法.我们证明,外层算法产生的点列收敛于问题(NSDPr)的稳定点.在第三章中针对每一个最小二乘子问题,我们设计了半光滑牛顿算法,称为内层算法.内层算法可以快速有效地求解子问题,而且我们证明它具有二次收敛速度.值得指出的是,该算法的关键在于两个方面.第一是秩约束的连续等价变换,第二是采用半光滑牛顿法求解子问题的最小二乘形式.第四章的大量数值结果表明,所提出的序列半光滑牛顿算法在求解该问题时非常有效.
本文的另一个研究内容是最优相关系数矩阵问题.我们研究带简单上界约束的最优相关系数矩阵问题.简单上界约束出现在很多实际问题中,例如具有给定条件数的最优相关系数矩阵问题,秩约束问题中寻找搜索方向矩阵问题等.在第五章中,我们对Qi和Sun提出的半光滑牛顿法加以改进,用于求解此问题,并对问题的非退化性进行了深入分析.我们证明在某些情形下,非退化性并不成立.通过建立非退化性和对偶问题的广义Hessian阵的对称正定性的等价关系,我们证明算法的二次收敛性.数值结果表明,尽管非退化性在某些情形下不成立,本文所提出的算法(即使对大规模问题)仍然非常有效.
在第六章中我们研究另一类秩约束问题:具有因子结构的最优相关系数矩阵问题.该问题源于很多实际问题,如资产收益的因子模型、多元时间序列等.对该问题,我们提出了两种数值方法:块松弛法和优化法.在块松弛法中,子问题是标准的信赖域问题,可采用Steighaug的截断共轭梯度法或信赖域方法的软件包LSTRS求解.而在优化法中,其子问题具有闭形式解.我们又将优化法拓展到带有非负因子约束的问题上.同时还考虑了不同初始点对算法的影响.数值试验说明两类算法都有较好的数值表现.