A least-squares approach for discretizable distance geometry problems with inexact distances

被引：0
作者：
Douglas S. Gonçalves
机构：
[1] Universidade Federal de Santa Catarina,
来源：
Optimization Letters | 2020年 / 14卷
关键词：
Distance geometry; EDM; Least-squares; Gram matrix;
D O I：
暂无
中图分类号：
学科分类号：
摘要：
A branch-and-prune (BP) algorithm is presented for the discretizable distance geometry problem in RK\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathbb {R}^K$$\end{document} with inexact distances. The algorithm consists in a sequential buildup procedure where possible positions for each new point to be localized are computed by using distances to at least K previously placed reference points and solving a system of quadratic equations. Such a system is solved in a least-squares sense, by finding the best positive semidefinite rank K approximation for an induced Gram matrix. When only K references are available, a second candidate position is obtained by reflecting the least-squares solution through the hyperplane defined by the reference points. This leads to a search tree which is explored by BP, where infeasible branches are pruned on the basis of Schoenberg’s theorem. In order to study the influence of the noise level, numerical results on some instances with distances perturbed by a small additive noise are presented.
引用
收藏
页码：423 / 437
页数：14
相关论文
共 70 条
  • [11] Drusvyatskiy D(2017)Recent advances on the interval distance geometry problem J. Glob. Optim. 69 525-545
  • [12] Krislock N(2010)Explicit sensor network localization using semidefinite representations and facial reductions SIAM J. Optim. 20 2679-2708
  • [13] Cheung Voronin Y-L(2012)Discretization orders for distance geometry problems Optim. Lett. 6 783-796
  • [14] Wolkowicz H(2012)The discretizable molecular distance geometry problem Comput. Optim. Appl. 52 115-146
  • [15] Dokmanic I(2013)The interval branch-and-prune algorithm for the discretizable molecular distance geometry problem with inexact distances J. Glob. Optim. 56 855-871
  • [16] Parhizkar R(2008)A branch-and-prune algorithm for the molecular distance geometry problem Int. Trans. Oper. Res. 15 1-17
  • [17] Ranieri J(2014)On the number of realizations of certain Henneberg graphs arising in protein conformation Discrete Appl. Math. 165 213-232
  • [18] Vetterli M(2014)Euclidean distance geometry and applications SIAM Rev. 56 3-69
  • [19] Dong Q(2011)Least-squares approximations in geometric buildup for solving distance geometry problems J. Optim. Theory Appl. 149 580-598
  • [20] Wu Z(1985)The best Euclidean fit to a given distance matrix in prescribed dimensions Linear Algebra Appl. 67 1-6
1234567