Convex Optimization · Problem 2.36

Convex functions — Boyd & Vandenberghe

Mathematics — Optimization · euclidean-distance-matrices

Problem

Euclidean distance matrices. Let

x_1, \ldots, x_n \in \mathbf{R}^k

. The matrix

D \in \mathbf{S}^n

defined by

D_{ij} = \|x_i - x_j\|_2^2

is called a Euclidean distance matrix. It satisfies some obvious properties such as

D_{ij} = D_{ji}

D_{ii} = 0

D_{ij} \geq 0

, and (from the triangle inequality)

D_{ik}^{1/2} \leq D_{ij}^{1/2} + D_{jk}^{1/2}

. We now pose the question: When is a matrix

D \in \mathbf{S}^n

a Euclidean distance matrix (for some points in

\mathbf{R}^k

, for some

k

)? A famous result answers this question:

D \in \mathbf{S}^n

is a Euclidean distance matrix if and only if

D_{ii} = 0

and

x^T D x \leq 0

for all

x

with

\mathbf{1}^T x = 0

. (See §8.3.3.) Show that the set of Euclidean distance matrices is a convex cone.

Intuitive explanation

A Euclidean distance matrix is defined by a simple algebraic constraint: $D_{ii} = 0$ and $x^T D x \leq 0$ for all centered vectors $x$ . To show this set forms a convex cone, you need to verify two closure properties: that non-negative scalar multiples of any EDM stay in the set, and that sums of any two EDMs remain EDMs. Both properties follow directly from the linearity of the constraints—scaling and adding preserve the zero diagonal and the inequality condition for all centered vectors.

Intuitive explanation

Related theory

Distance And Shortest Distance

Browse the problem library