- A Semidefinite Programming Approach for the Nearest Correlation Matrix Problem Miguel F. Anjos (anjosstanfordalumni.org) Nicholas J. Higham (highamma.man.ac.uk) Pawoumodom L. Takouda (takoudamip.ups-tlse.fr) Henry Wolkowicz (hwolkowiczuwaterloo.ca) Abstract: 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. Keywords: Category 1: Linear, Cone and Semidefinite Programming (Semi-definite Programming ) Category 2: Applications -- OR and Management Sciences (Finance and Economics ) Category 3: Optimization Software and Modeling Systems Citation: Download: [Postscript][Compressed Postscript][PDF]Entry Submitted: 09/16/2003Entry Accepted: 09/16/2003Entry Last Modified: 09/16/2003Modify/Update this entry Visitors Authors More about us Links Subscribe, Unsubscribe Digest Archive Search, Browse the Repository Submit Update Policies Coordinator's Board Classification Scheme Credits Give us feedback Optimization Journals, Sites, Societies Optimization Online is supported by the Mathematical Programming Society and by the Optimization Technology Center.