Efficient Positive Semidefinite Matrix Approximation by Iterative Optimisations and Gradient Descent Method

We devise two algorithms for approximating solutions of PSDisation, a problem in actuarial science and finance, to find the nearest valid correlation matrix that is positive semidefinite (PSD). The first method converts the PSDisation problem with a positive semidefinite constraint and other linear constraints into iterative Linear Programmings (LPs) or Quadratic Programmings (QPs). The LPs or QPs in our formulation give an upper bound of the optimal solution of the original problem, which can be improved during each iteration. The biggest advantage of this iterative method is its great flexibility when working with different choices of norms or with user-defined constraints. Second, a gradient descent method is designed specifically for PSDisation under the Frobenius norm to measure how close the two metrices are. Experiments on randomly generated data show that this method enjoys better resilience to noise while maintaining good accuracy. For example, in our experiments with noised data, the iterative quadratic programming algorithm performs best in more than 41% to 67% of the samples when the standard deviation of noise is 0.02, and the gradient descent method performs best in more than 70% of the samples when the standard deviation of noise is 0.2. Examples of applications in finance, as well as in the machine learning field, are given. Computational results are presented followed by discussion on future improvements.