forked from jump-dev/JuMP.jl
-
Notifications
You must be signed in to change notification settings - Fork 0
/
mindistortion.jl
60 lines (50 loc) · 1.7 KB
/
mindistortion.jl
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#############################################################################
# JuMP
# An algebraic modeling langauge for Julia
# See http://github.com/JuliaOpt/JuMP.jl
#############################################################################
# mindistortion.jl
#
# This example arises from computational geometry, in particular the problem
# of embedding a general finite metric space into a euclidean space.
#
# It is known that the 4-point metric space defined by the star graph:
# x
# \
# x — x
# /
# x
# where distances are computed by length of the shortest path between
# vertices, cannot be exactly embedded into a euclidean space of any
# dimension.
#
# Here we will formulate and solve an SDP to compute the best possible
# embedding, that is, the embedding f() that minimizes the distortion c such
# that (1/c)*D(a,b) ≤ ||f(a)-f(b)|| ≤ D(a,b) for all points (a,b), where
# D(a,b) is the distance in the metric space.
#
# Any embedding can be characterized by its Gram matrix Q, which is PSD,
# and ||f(a)-f(b)||^2 = Q[a,a] + Q[b,b] - 2Q[a,b]
# We can therefore constrain
# D[i,j]^2 ≤ Q[i,i] + Q[j,j] - 2Q[i,j] ≤ c^2*D[i,j]^2
# and minimize c^2, which gives us the SDP formulation below.
#
# For more detail, see
# "Lectures on discrete geometry" by J. Matoušek, Springer, 2002, pp. 378-379.
using JuMP
m = Model()
D = [0.0 1.0 1.0 1.0
1.0 0.0 2.0 2.0
1.0 2.0 0.0 2.0
1.0 2.0 2.0 0.0]
@defVar(m, cSq >= 1.0)
@defVar(m, Q[1:4,1:4], SDP)
for i in 1:4
for j in (i+1):4
@addConstraint(m, D[i,j]^2 <= Q[i,i] + Q[j,j] - 2Q[i,j])
@addConstraint(m, Q[i,i] + Q[j,j] - 2Q[i,j] <= D[i,j]^2*cSq )
end
end
@setObjective(m, Min, cSq)
solve(m)
println(getValue(cSq))