7
$\begingroup$

Assume I have a matrix $(d_{ji})_{ij}$ of distances between points $i$ and $j$. These distances could be anything fulfilling the triangle inequality.

Now I would like to find coordinates $(x_i,y_i)$ for each $i$, so that the Euclidean distances are always less or equal to the real ones:

$$ \varepsilon_{ij} = d_{ij} - \sqrt{(x_i-x_j)^2 + (y_i-y_j)^2} \geq 0$$

Furthermore, the sum $\sum_{ij} \varepsilon_{ij}$ should be minimal.

How could one approach such a non-linear problem?

EDIT: I would also be interested in other, similar objective functions that somehow minimize the $\varepsilon_{ij}$. The important for me is that the "approximation" fulfils the inequalities stated above.

Improve this question
$\endgroup$
4
  • $\begingroup$ How large a problem (dimension) do you need to solve? How quickly do you need to solve it? Would you settle for a local optimum which may or may not be globally optimal? $\endgroup$
    – Mark L. Stone
    May 22, 2020 at 17:34
  • $\begingroup$ The matrix has the maximal size $200\times 200$. To be useful, it should solve in under one minute. A heuristic that finds good solutions would also be of interest. $\endgroup$
    – J Fabian Meier
    May 22, 2020 at 21:04
  • $\begingroup$ This looks a lot like a Euclidean Distance Matrix Completion problem (see lix.polytechnique.fr/~liberti/dgp-siam.pdf for a review). Solving it exactly is equivalent to a low-rank optimization problem, which is currently intractable, but at size 200x200 you can usually get pretty good performance from taking a semidefinite relaxation and minimizing the trace of the Gram matrix. $\endgroup$
    – Ryan Cory-Wright
    May 23, 2020 at 18:18
  • $\begingroup$ If you care about finding the underlying points in addition to the Gram matrix then this paper by Biswas and Ye might also be a good starting point optimization-online.org/DB_FILE/2006/07/1436.pdf $\endgroup$
    – Ryan Cory-Wright
    May 23, 2020 at 18:19

2 Answers 2

Reset to default
4
$\begingroup$

Your problem seems to be similar to Multidimensional Scaling (MDS). In MDS, the goal is to represent multidimensional data as good as possible in fewer dimensions.

If high-dimensional distances are represented in $\mathbb{R}^2$, classical MDS corresponds to the problem $$\min_{x,y} \sum_{ij} \varepsilon_{ij}^2,$$ using your definition of $\varepsilon_{ij}$. This problem allows for a closed-form solution based on eigendecomposition.

In your case, there are two differences. First, you have the additional constraints $\varepsilon_{ij} \ge 0$, which are convex in terms of $x$ and $y$. Second, you have a different objective, which is not convex in $x$ and $y$. I don't know if there are MDS generalizations that specifically consider these things, but it could be a good starting point.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Actually, I would also be interested in similar other objectives (like the one you gave). The conditions need to be as they were stated. $\endgroup$
    – J Fabian Meier
    May 21, 2020 at 16:41
1
$\begingroup$

Your constraint defines a second order cone, which means it is convex. You can solve it with a specialized solver (for example one listed on the Wikipedia page), although any convex solver might work if the problem is not too hard.

The equivalent SOCP formulation would be: \begin{align}\min& \quad\sum_{ij} \varepsilon_{ij}\\\text{s.t.}& \quad\lVert X_i - X_j \rVert_2 \leq d_{ij} - \varepsilon_{ij}\end{align} where $X = (x, y)$.

EDIT: There is nothing in the above formulation that forces $\varepsilon_{ij}$ to be equal to $d_i - \lVert X_i - X_j \rVert_2 \leq d_{ij}$: it doesn't match the original problem. Such a constraint would make it non-convex. Thanks to Mark L. Stone and Paul Rubin for pointing it out in the comments.

Improve this answer
$\endgroup$
11
  • 1
    $\begingroup$ No. Although the constraints are (convex) SOCP constraints, the objective (as currently proposed) is concave. That makes this a Concave Programming problem. There are some specialized solvers, such as KNITRO, which have special processing for SOCP constraints, even for problems which overall are not convex. i don't know whether such specialized treatment of SOCP constraints would help for this problem. $\endgroup$
    – Mark L. Stone
    May 22, 2020 at 17:32
  • $\begingroup$ Thanks for your comment. I don't understand your assertion that the objective is non-convex: it seems to me that the goal to minimize $\sum_{ij} \varepsilon_{ij}$ makes it linear (and therefore convex) $\endgroup$
    – Ggouvine
    May 22, 2020 at 17:38
  • 1
    $\begingroup$ I edited to add the formulation. Could you please elaborate how the LINEAR objective is an issue, or how the constraint does not define a second order cone? $\endgroup$
    – Ggouvine
    May 23, 2020 at 7:49
  • 1
    $\begingroup$ NO!!!! You can not remove the non-convexity like that. Making $\epsilon_{ij}$ decision variables would make the objective linear, but you would need to add non-convex constraint(s) to relate $\epsilon_{ij}$ to the (other) decision variables $x_i,y_j$. Your proposed constraint (i.e., epigraph formulation): $\epsilon \ge d - \|x\|$ is a non-convex constraint, so it does NOT define a convex cone. The inequality is going in the wrong direction to be convex. $\endgroup$
    – Mark L. Stone
    May 23, 2020 at 13:59
  • 2
    $\begingroup$ I don't think this formulation is equivalent to the original problem. The $\epsilon$ variables must be nonnegative (else this version is unbounded). That being the case, $X=0$, $\epsilon=0$ is a trivial optimal solution here, but does not approximate the given distances. $\endgroup$
    – prubin ♦
    May 23, 2020 at 14:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.