optimization – Algorithm for optimizing the distance between points in N-dimensional space

Question:

I need to optimize the distance between points, but some points cannot be changed.

Example (3D):

X : входные данные
X[1] = 0.25, 0.8, 0.4 - const
X[2] = 0.11, 0.5, 0.3 - const
X[3] = 0.43, 0.3, 0.1 - mutable(генерируем рандомно 0...1)
X[4] = 0.11, 0.4, 0.2 - mutable(генерируем рандомно 0...1)
X[5] = 0.23, 0.3, 0.3 - mutable(генерируем рандомно 0...1)

dm : Матрица расстояний
0 0.345832 0.393372 0.172916 0.393775
0.345832 0 0.393775 0.172916 0.393372
0.393372 0.393775 0 0.353553 0.707107
0.172916 0.172916 0.353553 0 0.353553
0.393775 0.393372 0.707107 0.353553 0

X : результат
X[1] = 0.25, 0.8, 0.4 - const
X[2] = 0.11, 0.5, 0.3 - const
X[3] = 0.??, 0.?, 0.? - mutable
X[4] = 0.??, 0.?, 0.? - mutable
X[5] = 0.??, 0.?, 0.? - mutable

It turns out the points X [1] and X [2] are already in place, the distance between them is equal to the value in the distance matrix, they cannot be changed. You just need to change {x, y, z} in X [3], X [4], X [5]. Perhaps there is an algorithm with which you can solve this problem?

Number of points ~ 200

Dimension of space> = 3D

Answer:

In other words, your task is formulated like this:

Points X_1, X_2, …, X_m are given in a space of dimension D, and a symmetric matrix L of size NxN is given, where N> m. It is necessary to choose the points X_ {m + 1}, …, X_N so that the corresponding matrix of distances M differs minimally from L: | M – L | = min.

I will not ask what measure in matrix space you are going to use to determine the distance between matrices, this is not essential for a solution.

The dimension of the problem is fundamental. 200 points are 200 D parameters. Even if 100 points are fixed, finding the rest is equivalent to solving the optimization problem in a space of 100 N.

I suspect that none of the application packages will be able to solve the problem of this dimension, since the process will generate Jacobians of size (100 N) x (100 N). So I would solve like this:

  1. Reduce the dimension of the problem from 100 unknown points to 1. we take 100 points and look for one point that will give the optimal matrix of 101 by 101 size. As a solution method, you can take Monte Carlo, or solve numerically the problem of finding an extremum for a function with D variables.
  2. Having fixed 101 points, we are looking for the 102nd point.
  3. Having fixed 102 points, we are looking for the 103rd point. …
  4. Having fixed 199 points, we are looking for 200 points.

Stopudov this will be a suboptimal solution. You can take it as an initial value and try to refine it with gradient descent. As a result, you will get some minimum.

My instinct tells me that this problem will have a sea of ​​local minima, and from a practical point of view, the problem of finding a global minimum will be insoluble.

Post Views: 1
Scroll to Top