  


A Semidefinite Programming Approach for the Nearest Correlation Matrix Problem
Miguel F. Anjos (anjosstanfordalumni.org) 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 primaldual interiorexteriorpoint (pd iep) 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 socalled 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 GaussNewton method rather than a Newton method on a symmetrized system, and is computed using a preconditioned conjugategradienttype 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 (Semidefinite 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/2003 Modify/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  