Optimization Online


A Semidefinite Programming Approach for the Nearest Correlation Matrix Problem

Miguel F. Anjos (anjos***at***stanfordalumni.org)
Nicholas J. Higham (higham***at***ma.man.ac.uk)
Pawoumodom L. Takouda (takouda***at***mip.ups-tlse.fr)
Henry Wolkowicz (hwolkowicz***at***uwaterloo.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.


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


Download: [Postscript][Compressed Postscript][PDF]

Entry Submitted: 09/16/2003
Entry Accepted: 09/16/2003
Entry Last Modified: 09/16/2003

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society