最优低秩相关系数矩阵问题

本文主要研究最优低秩相关系数矩阵问题及与其相关的两类问题：带简单上界约束的最优相关系数矩阵问题和具有因子结构的最优相关系数矩阵问题.最优低秩相关系数矩阵问题来源于金融领域,在组合优化、机器学习、数据分析等方面也有重要应用.目前已经有很多方法可以来求解它.其中,优化算法是很受欢迎的一种方法.在本文的第二章到第四章中,我们将提出序列半光滑牛顿算法.由于该问题是一个非凸约束优化问题,为了处理非凸的秩约束条件,在第二章中,我们首先将原问题转化为一个等价的非线性半定规划问题(NSDPr).这主要是基于一个著名的结果：对称矩阵的前r个最大特征值之和可以写成一个半定规划问题.(NSDPr)也是一个非凸优化问题,它含有两个矩阵变量和三个对称半正定锥约束.为避免直接求解,我们通过求解一系列最小二乘子问题来求解(NSDPr),称之为外层算法.我们证明,外层算法产生的点列收敛于问题(NSDPr)的稳定点.在第三章中针对每一个最小二乘子问题,我们设计了半光滑牛顿算法,称为内层算法.内层算法可以快速有效地求解子问题,而且我们证明它具有二次收敛速度.值得指出的是,该算法的关键在于两个方面.第一是秩约束的连续等价变换,第二是采用半光滑牛顿法求解子问题的最小二乘形式.第四章的大量数值结果表明,所提出的序列半光滑牛顿算法在求解该问题时非常有效.本文的另一个研究内容是最优相关系数矩阵问题.我们研究带简单上界约束的最优相关系数矩阵问题.简单上界约束出现在很多实际问题中,例如具有给定条件数的最优相关系数矩阵问题,秩约束问题中寻找搜索方向矩阵问题等.在第五章中,我们对Qi和Sun提出的半光滑牛顿法加以改进,用于求解此问题,并对问题的非退化性进行了深入分析.我们证明在某些情形下,非退化性并不成立.通过建立非退化性和对偶问题的广义Hessian阵的对称正定性的等价关系,我们证明算法的二次收敛性.数值结果表明,尽管非退化性在某些情形下不成立,本文所提出的算法(即使对大规模问题)仍然非常有效.在第六章中我们研究另一类秩约束问题：具有因子结构的最优相关系数矩阵问题.该问题源于很多实际问题,如资产收益的因子模型、多元时间序列等.对该问题,我们提出了两种数值方法：块松弛法和优化法.在块松弛法中,子问题是标准的信赖域问题,可采用Steighaug的截断共轭梯度法或信赖域方法的软件包LSTRS求解.而在优化法中,其子问题具有闭形式解.我们又将优化法拓展到带有非负因子约束的问题上.同时还考虑了不同初始点对算法的影响.数值试验说明两类算法都有较好的数值表现.此博士论文得到了国家自然科学基金(10771057)和教育部重大项目(309023)的资助.此博士论文用LATEX2ε软件打印.
工业羊毛毡
In this thesis, we study the nearest low-rank correlation matrix problem as well as another two related problems:nearest correlation matrix problem with a simple upper bound, nearest correlation matrix problem with factor structure.Nearest low-rank correlation matrix problem comes from finance and has im-portant applications in many areas such as combinatorial optimization, machine learning and data analysis. Different methods have been proposed, among which majorization method is a popular method. In Chapter 2-Chapter 4, we propose a numerical method called’ sequential semismooth Newton method’to solve it. In Chapter 2, noting that the nearest low-rank correlation matrix problem is a typical nonconvex optimization problem due to the rank constraint, we first for-mulate it as an equivalent nonlinear semidefinite programming problem (NSDPr). This is based on the well known result that the sum of the largest r eigenvalues of a symmetric matrix can be represented as a semidefinite programming problem. (NSDPr) is a nonconvex optimization problem with two matrix variables and three positive semidefinite cone constraints. Keeping that in mind, we solve it by solving a sequence of least-square problems rather than solving it directly, we refer it as the outer algorithm. The outer algorithm is guaranteed to produce a stationary point of (NSDPr). In Chapter 3, each of the least-square problems is efficiently solved by a specifically designed semismooth Newton method (referred as inner al-gorithm), which is shown to be quadratically convergent. It is worth pointing out the two key points in the proposed method. One is the equivalent reformulation of the rank constraint, the other is the semismooth Newton method which is applied to the least square form of the subproblem. Our numerical results in Chapter 4 demonstrate the high efficiency of the proposed method.Next, for the nearest correlation matrix problem, we investigate the nearest correlation matrix problem with a simple upper bound. Such simple bound con-straint arises from many applications such as the nearest correlation matrix with a prescribed condition number, and finding the search direction matrix in rank con-straint problems. In Chapter 5, we extend semismooth Newton method proposed by Qi and Sun to solve it. We also show among others that constraint nondegen-eracy does not always hold. By establishing the equivalence between constraint nondegeneracy and the positive definiteness of the generalized Hessian of the dual problem, we prove the quadratic convergence rate of the extended method. De- spite this, the numerical results show that the extended method is still extremely efficient even for large scale problems.In Chapter 6, we investigate the nearest correlation matrix problem with fac-tor structure, which is another kind of rank constraint problems. Such problem arises in different areas, such as factor models of asset returns, multivariate time series. We propose two numerical methods:block relaxation method and ma-jorization method to solve it. In the block relaxation method, the subproblem is of the standard trust region problem, which is solved by Steighaug’s truncated conju-gate gradient method or by the trust region package LSTRS. In the majorization method, the subproblem has a closed-form solution. We then extend majorization method to deal with the case with more nonnegativity constraints. We also inves-tigate the role that different starting points play in the methods. The numerical results confirm the good performance of the proposed methods.This dissertation is supported by the National Natural Science Foundation of China (10771057) and the Major Project of Ministry of Education of China granted (309023).This dissertation is typeset by software LATEX2ε.