Optimization Online


Euclidean Distance Matrix Completion Problems

Haw-ren Fang(hrfang***at***yahoo.com)
Dianne P. O'Leary(oleary***at***cs.umd.edu)

Abstract: A Euclidean distance matrix is one in which the $(i,j)$ entry specifies the squared distance between particle $i$ and particle $j$. Given a partially-specified symmetric matrix $A$ with zero diagonal, the Euclidean distance matrix completion problem (EDMCP) is to determine the unspecified entries to make $A$ a Euclidean distance matrix. We survey three different approaches to solving the EDMCP. We advocate expressing the EDMCP as a nonconvex optimization problem using the particle positions as variables and solving using a modified Newton or quasi-Newton method. To avoid local minima, we develop a randomized initialization technique that involves a nonlinear version of the classical multidimensional scaling, and a dimensionality relaxation scheme with optional weighting. Our experiments show that the method easily solves the artificial problems introduced by Mor\'{e} and Wu. It also solves the 12 much more difficult protein fragment problems introduced by Hendrickson, and the 6 larger protein problems introduced by Grooms, Lewis, and Trosset.

Keywords: distance geometry, Euclidean distance matrices, global optimization, dimensionality relaxation, modified Cholesky factorizations, molecular conformation

Category 1: Global Optimization (Applications )

Category 2: Applications -- Science and Engineering (Chemical Engineering )

Citation: unpublished manuscript, Department of Computer Science and Engineering, University of Minnesota, and Department of Computer Science, University of Maryland, June 2010.

Download: [PDF]

Entry Submitted: 06/10/2010
Entry Accepted: 06/10/2010
Entry Last Modified: 06/10/2010

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