The nearest \cm\ problem is to find a positive semidefinite matrix with unit diagonal that is nearest in the Frobenius norm to a given symmetric matrix $A$. This problem can be formulated as an optimization problem with a quadratic objective function and semidefinite programming constraints. Using such a formulation, we derive and test a primal-dual interior-exterior-point (p-d i-e-p) algorithm designed specifically for robustness and handling the case where $A$ is sparse. The algorithm is novel in several respects. First, instead of solving the so-called normal equations to obtain the search direction at each iteration, our algorithm eliminates the linear feasibility equations from the start. This means that we maintain exact primal and dual feasibility during the course of the algorithm, and that we use a single bilinear equation to linearize for the search direction at each iteration. Second, the search direction is found using an inexact Gauss-Newton method rather than a Newton method on a symmetrized system, and is computed using a preconditioned conjugate-gradient-type method. We consider two types of preconditioner, an optimal diagonal preconditioner and a block diagonal preconditioner obtained from a partial Cholesky factorization. Finally, once the current iterate is sufficiently close to the optimal solution, we apply a crossover technique that sets the barrier parameter to $0$ and does not maintain interiority of the iterates. The result is a robust algorithm with asymptotic quadratic convergence and the ability to handle {\em warm starts} simply. Preliminary computational results illustrate the robustness of the algorithm and show that sparsity can be successfully exploited.
Article
View A Semidefinite Programming Approach for the Nearest Correlation Matrix Problem