Nearest Low-Rank Correlation Matrix Problem

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ε.