Optimization Online


Parallel Implementation of Successive Sparse SDP Relaxations for Large-scale Euclidean Distance Geometry Problems

Sunyoung Kim(skim***at***ewha.ac.kr)
Masakazu Kojima(kojima***at***is.titech.ac.jp)
Makoto Yamashita(makoto***at***is.titech.ac.jp)

Abstract: The Euclidean distance geometry problem (EDGP) includes locating sensors in a sensor network and constructing a molecular configuration using given distances in the two or three-dimensional Euclidean space. When the locations of some nodes, called anchors, are given, the problem can be dealt with many existing methods. An anchor-free problem in the three-dimensional space, however, is a more challenging problem and can be handled with only a few methods. We propose an efficient and robust numerical method for large-scale EDGPs with exact and corrupted distances including anchor-free three-dimensional problems. The method is based on successive application of the sparse version of full semidefinite programming relaxation (SFSDP) proposed by Kim, Kojima, Waki and Yamashita, and can be executed in parallel. Numerical results on large-scale anchor-free three-dimensional problems with more than 10000 nodes demonstrate that the proposed method performs better than the direct application of SFSDP and the divide and conquer method of Leung and Toh in terms of efficiency and/or effectiveness measured in the root mean squared distance.

Keywords: Euclidean distance geometry problem, molecular conformation, the successive sparse SDP relaxations, parallel implementation.

Category 1: Linear, Cone and Semidefinite Programming (Semi-definite Programming )

Citation: Research report, B-470, Department of Mathematical and Computing Sciences, Tokyo Institute of Technology, 2-12-1 Oh-Okayama, Meguro-ku, Tokyo 152-8552 Japan.

Download: [PDF]

Entry Submitted: 11/29/2012
Entry Accepted: 11/29/2012
Entry Last Modified: 11/29/2012

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 Optimization Society