The problem of recovering (x,y,z) coordinates given partial pairwise distance information is a famous problem in the optimization community and has attracted the attention of many top people. It is sometimes called the 'Euclidean distance matrix completion' problem by mathematicians and the 'sensor localization' problem by engineers. If you search in google scholar on either of these terms, you'll find many papers. Jon Dattorio wrote an entire book on the problem.
-- Steve Vavasis On Tuesday, October 20, 2015 at 11:12:44 PM UTC-4, Spencer Russell wrote: > > I have a bunch of points in 3D whose positions I know approximately, with > low-noise distance measurements between them (not necessarily fully > connected). I want to improve my estimate of their 3D coordinates. This > smells like an optimization problem so I’m thinking of using it as an > excuse to learn JuMP. The model variables (coordinates) and objective > function seem pretty straightforward (probably sum of squared distance > errors for the objective?) but I don’t know enough about the various > solvers to know which one to use. I know a tiny bit about optimization > (I’ve implemented simplex, L-M, and conjugate GD for a class) but get > quickly outside my depth when it gets theoretical. > > Without any known positions the system is underconstrained because the > whole collection could can translate, rotate, and reflect, but if I set 3 > non-colinear points at known positions it should be solvable. I can also > supply pretty good guesses for initial values on locations, at least close > enough that the closest minima is the one I want (I think). > > so in short my questions boil down to: > > 1. What solver is appropriate for this sort of problem? (or should I just > go with a spring-force algorithm like in GraphLayout.jl?) > 2. (JuMP Specific) - Should I specify my known positions as model > variables with equality constraints, or just normal julia variables that > show up in my objective function? > > Thanks! > > -s
