求解最佳相关矩阵问题的数值算法

发布时间：2018-07-05 08:48

本文选题：相关矩阵问题 + 半光滑牛顿法　；参考：《湖南大学》2015年硕士论文

【摘要】：最佳相关矩阵问题是指在Frobenius范数下寻找与给定的对称矩阵最接近的相关矩阵.最佳相关矩阵问题一般有不带权、带W权、带H权、带Q权等类型.本文主要针对前三种类型的理论和数值解法展开进一步的研究.本文首先介绍了最佳相关矩阵问题的研究现状和进展,在此基础上提出了本文的工作构想.同时,为方便后面的研究,本文给出了最优化的一些基础知识以及相关的优化算法.在第二章,我们首先研究了W权问题的特殊形式—不带权问题的理论与数值解法.对于不带权问题,我们分析了它与它的对偶问题之间的关系—原问题的解可用其对偶问题的解表示.由于对偶问题等价于一个半光滑方程组,在求解半光滑方程组的牛顿法的基础上,利用正则化策略修改牛顿方程,我们提出了求解半光滑方程组的正则化牛顿法.它的优点是计算出的搜索方向一定是目标函数的下降方向,有效克服了半光滑牛顿法的固有缺陷.为了提高正则化牛顿法的效率,我们研究了求解牛顿方程的共轭梯度法(即内层迭代)的预处理策略、内层迭代控制变量取值的优化处理,然后我们提出了一个改善的正则化牛顿法,并分析了它的全局收敛性和二次收敛速度.最后,我们研究了改善的正则化牛顿法的计算解的相关性处理,使得最终计算出的解更接近相关矩阵,并分析了它与最优解的误差估计.由于一般的W权问题可以通过简单的变换转化为不带权问题,因此上面关于不带权问题的研究工作可推广到一般的W权问题的求解.在第三章,我们分析了带H权问题的理论和数值解法.首先我们给出了这类问题的约束非退化性质和强二阶充分条件,以及广义Jacobi的计算公式,然后在此基础上我们对求解H权问题的牛顿—共轭梯度法(Newton-CG法)进行了改善.在内层迭代中,利用目标函数在迭代点处的一阶、二阶信息对控制变量的取值进行重新定义,均衡内外层迭代的计算量,有效提高算法的效率.通过简单的分析得出改善后的Newton-CG法仍然具有二次收敛性.文章最后对本文提出的所有算法进行了数值测试.数值实验结果表明,本文所提出的算法具有很好的数值效果.
[Abstract]:The optimal correlation matrix problem is to find the most close correlation matrix to the given symmetric matrix under Frobenius norm. There are three kinds of optimal correlation matrix problems: no weight, W weight, H weight, Q weight and so on. This paper focuses on the first three types of theoretical and numerical solutions to further research. This paper first introduces the research status and progress of the optimal correlation matrix problem, and then puts forward the working conception of this paper. At the same time, in order to facilitate the following research, this paper gives some basic knowledge of optimization and related optimization algorithms. In the second chapter, we first study the special form of W weight problem, the theory and numerical solution of unweighted problem. For the unweighted problem, we analyze the relationship between it and its dual problem, the solution of the original problem can be represented by the solution of its dual problem. Since the duality problem is equivalent to a semi-smooth system of equations, on the basis of Newton's method for solving semi-smooth equations, we propose a regularized Newton method for solving semi-smooth equations by using regularization strategy to modify Newton's equations. Its advantage is that the calculated search direction must be the descent direction of the objective function, which effectively overcomes the inherent defects of the semi-smooth Newton method. In order to improve the efficiency of regularization Newton method, we study the preprocessing strategy of conjugate gradient method (I. E. inner iteration) for solving Newton equation, and optimize the value of inner iteration control variable. Then we propose an improved regularization Newton method and analyze its global convergence and quadratic convergence rate. Finally, we study the correlation treatment of the computational solution of the improved regularized Newton method, which makes the final solution closer to the correlation matrix, and analyzes the error estimates between the solution and the optimal solution. Since a general W weight problem can be transformed into a non weighted problem by a simple transformation, the above research work on the non weighted problem can be extended to the solution of the general W weight problem. In the third chapter, we analyze the theory and numerical solution of H-weighted problem. First of all, we give the constrained nondegenerate property, strong second order sufficient condition and generalized Jacobi formula for this kind of problems. Then we improve the Newton-CG method for solving H-weight problems. In the inner layer iteration, the first order and second order information of the objective function at the iteration point is used to redefine the value of the control variable, to balance the computation of the inner and outer layer iteration, and to improve the efficiency of the algorithm effectively. A simple analysis shows that the improved Newton-CG method still has quadratic convergence. Finally, all the algorithms proposed in this paper are numerically tested. The numerical results show that the proposed algorithm has a good numerical effect.
【学位授予单位】：湖南大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：O224

【参考文献】