Visualizing da a as objec s by DC (di e ence o con ex)
op imiza ion
Emilio Ca izosa1, Vanesa Gue e o1, and Dolo es Rome o Mo ales2
1Ins i u o de Ma em´a icas de la Uni e sidad de Se illa (IMUS), Se ille, Spain
{eca izosa, gue e o}@us.es
2Copenhagen Business School, F ede iksbe g, Denma k
[email p o ec ed]
Abs ac
In his pape we add ess he p oblem o isualizing in a bounded egion a se o indi idu-
als, which has a ached a dissimila i y measu e and a s a is ical alue. This p oblem, which
ex ends he s anda d Mul idimensional Scaling Analysis, is w i en as a global op imiza ion
p oblem whose objec i e is he di e ence o wo con ex unc ions (DC). Sui able DC de-
composi ions allow us o use he DCA algo i hm in a e y e icien way. Ou algo i hmic
app oach is used o isualize wo eal-wo ld da ase s.
Keywo ds: Da a Visualiza ion, DC unc ions, DC algo i hm, Mul idimensional Scaling
Analysis
1 In oduc ion
In he Big Da a e a, Da a Visualiza ion is an a ea o in e es o specialis s om a wide a ie y o
disciplines, [14,15,26,27]. The in o ma ion managed mus be p ocessed and, wha is e en mo e
impo an , unde s ood. Da a Visualiza ion echniques a ise o espond o his equi emen by
de eloping speci ic amewo ks o depic complex da a s uc u es as easy- o-in e p e g aphics,
[40,50].
Ma hema ical Op imiza ion has con ibu ed signi ican ly o he de elopmen o his a ea
du ing ecen yea s, see [13,30,42] and he e e ences he ein. Nowadays, complex da ase s
pose new challenges in o de o isualize he da a in such a way ha pa e ns a e cap u ed and
use ul in o ma ion is ex ac ed. Special a en ion is paid o ep esen he unde lying dissimi-
la i y ela ionships ha da a may ha e. Classical dimensionali y educ ion echniques, such as
P incipal Componen Analysis, [43], o Mul idimensional Scaling (MDS), [29,34,52], ha e been
cus omized o deal wi h mo e complex da a s uc u es, [1,5,16], and o make he in e p e abili y
o he esul s easie ia, o ins ance, spa se models, [9,8,18].
Apa om adap ing exis ing me hods, speci ic p oblems may call also o new app oaches.
Fo ins ance, in addi ion o he dissimila i y measu e, he da a may ha e a ached a s a is ical
a iable, o be ela ed wi h he size o each objec in he g aphical ep esen a ion o he da ase ,
[20]. This is he case o geog aphical da a, o be isualized on a map in which coun ies a e e-
sized acco ding o, o ins ance, popula ion a es, bu main aining he neighbo ing ela ionships
1
o coun ies. This ype o ep esen a ions, known as ca og ams, [51], leads o plo s in which
coun ies a e eplaced by geome ical objec s, equen ly ci cles o ec angles, while he neigh-
bo hood ela ionships and he size o he objec s a e sough o be well ep esen ed. A key issue
is how such p oblems a e exp essed as op imiza ion p og ams, and which op imiza ion ools a e
a ailable o cope wi h hem. Fo uses o op imiza ion applied o ca og ams cons uc ion and
ela ed isualiza ion amewo ks we e e he eade o [6,10,11,20,21,28,31,47,49] and
e e ences he ein.
In his pape we p esen a new ma hema ical p og amming amewo k o build a isualiza ion
map, in which a se o Nindi iduals a e depic ed as con ex objec s in a bounded egion Ω ⊂Rn,
usually n≤3. These objec s mus ha e a olume p opo ional o a gi en s a is ical alue
associa ed wi h he indi iduals, ω= (ω1, . . . , ωN), and hey should be placed acco dingly o
a dissimila i y measu e a ached o he indi iduals, δ= (δij)i,j=1,...,N . In o de o loca e he
objec s in Ω, a e e ence objec Bis used, o be ansla ed and expanded. Howe e , since ou
inal goal is o ob ain a isualiza ion map which allows he analys s o unde s and he da a hey
a e wo king wi h, a c i e ion which somehow con ols he appea ance o he plo needs o be
also conside ed. We will deal wi h his pa adigm by ocusing on how he objec s a e sp ead ou
o e Ω.
Lea ing aside he s a is ical alues ω, he pu pose o ep esen ing dissimila i ies be ween
indi iduals eminds o MDS, [5,16,18,29,34,35,39,52], which aims o ep esen he dissimi-
la i y be ween indi iduals as empi ical dis ances be ween poin s in an unbounded space o lowe
dimension. Al hough ou isualiza ion model may seem e y close o MDS, i has he special
ea u e o ep esen ing in he bounded egion Ω no only dissimila i ies as dis ances be ween
objec s, bu also he s a is ical measu e ω h ough he olumes o he objec s in Ω. Ou isual-
iza ion ool is able o escale he dissimila i ies be ween he indi iduals and he s a is ical alues
associa ed o hem o i in Ω. Obse e ha i ing he objec s in o Ω may yield ep esen a ions
in which he objec s in e sec i hei sizes a e no small enough, bu , on he o he hand, oo
small objec s obs uc he isualiza ion o he s a is ical measu e. Ideally he objec s should be
sp ead ou ac oss he isualiza ion map. This aim will be also aken in o accoun when modeling
he p oblem.
The me hodology p oposed in his pape has applica ions in ields o he s han Da a Visu-
aliza ion, such as o ins ance, Loca ion Analysis o Dis ance Geome y. In loca ion p oblems,
he acili ies o be loca ed a e usually conside ed as poin s. Howe e , a na u al ex ension is o
conside acili ies as dimensional s uc u es, see [19], and DC echniques ha e been speci ically
applied o his gene aliza ion, [3,12]. Ou s can also be seen as a p oblem in Dis ance Geome y
op imiza ion, as ca e ully e iewed in [39]. In Dis ance Geome y, a g aph ealiza ion p oblem
consis s o inding a con igu a ion o poin s such ha hei (Euclidean) dis ances i a gi en
dissimila i y ma ix. Among hem is he Senso Ne wo k Loca ion p oblem, [46,48,54,58], in
which one assumes ha some indi iduals a e ancho s ( hei loca ion is known) and he emain-
ing ones a e senso s, whose loca ion is o be ob ained so ha hei Eculidean dis ances i he
dissimila i ies. Thus, ou me hod can also be applied o he Senso Ne wo k Loca ion p oblem,
in which senso s and ancho s ha e a nonnegligible a ea.
In his pape , he cons uc ion o a isualiza ion map wi h he h ee cha ac e is ics men ioned
abo e is w i en as a global biobjec i e op imiza ion p oblem wi h con ex cons ain s. We show
ha he objec i e unc ion o he agg ega e p oblem can be exp essed as a di e ence o con ex
(DC) unc ion, and hus DC op imiza ion ools can be used o sol e he op imiza ion p og am.
The es o he pape is o ganized as ollows. In Sec ion 2 he biobjec i e op imiza ion
2
p og am o build he isualiza ion map is o malized. In Sec ion 3, s uc u al p ope ies o
he op imiza ion p oblem a e analyzed. In Sec ion 4, we p esen ou algo i hmic app oach.
Nume ical esul s o wo da ase s o di e en size and na u e a e included in Sec ion 5. Some
conclusions and ex ensions a e p esen ed in Sec ion 6.
2 The isualiza ion model
In ou model we ha e a e e ence objec B, which is a compac con ex subse o Rn, symme ic
wi h espec o he o igin, in e io o B. Each indi idual iis associa ed wi h a se o he o m
ci+τ iB, whe e i≥0 is chosen so ha he olume o iBis p opo ional o he s a is ical
alue ωi≥0, ciis a ansla ion ec o and τis a common posi i e escaling o all objec s. We
seek he alues o he a iables ci,i= 1, . . . , N, and τso ha objec s ci+τ iBa e con ained
in Ω. The p e iously desc ibed ep esen a ion is illus a ed in Figu e 1.
Ω
B
ci+τ iB
ci
cj+τ jB
cj
ck+τ kB
ck
Figu e 1: Example in R2o a isualiza ion egion Ω, a e e ence objec Band h ee indi iduals
i,jand kde ined h ough he ansla ion ec o s ci,cjand ck, which a e scaled ia τ i,τ j
and τ k.
Hence o h, we deal wi h a biobjec i e op imiza ion p oblem: he dis ances be ween he
objec s ep esen ing he indi iduals iand jmus esemble he dissimila i ies δij be ween such
indi iduals, and he objec s mus be sp ead ou in Ω o make he isualiza ion easie . The wo
c i e ia a e o malized in wha ollows.
2.1 Fi s objec i e: dis ances esemble dissimila i ies
Rega ding he i s objec i e, a unc ion d, which gi es us a s ic ly posi i e dis ance be ween
wo non-in e sec ing objec s ep esen ing indi iduals iand jand ze o o he wise, needs o be
conside ed. Thus, we de ine he unc ion g, which assigns such dis ance o wo indi iduals iand
3
j, as ollows
g:Rn×Rn×R+−→ R+
(ci,cj, τ)7−→ d(ci+τ iB,cj+τ jB).(1)
Then, o quan i y he esemblance be ween he dis ances in he isualiza ion map and he
dissimila i ies, he summa ion o e all he indi iduals o he squa ed di e ences be ween he
dis ances and he escaled dissimila i ies h ough a posi i e a iable κwill be minimized. Thus,
we conside as i s objec i e he unc ion F1de ined as
F1:Rn×. . . ×Rn×R+×R+−→ R+
(c1,...,cN, τ, κ)7−→ X
i,j=1,...,N
i6=j
[g(ci,cj, τ)−κδij]2.
Obse e ha o simplici y all pai s (i, j) a e conside ed in he summa ion in F1, bu ou
analysis emains alid i only some (i, j) pai s o objec s, as done e.g. in [53].
2.2 Second objec i e: sp ead
To a oid ha he objec s collapse in a small sub egion o Ω, we encou age objec s o be sp ead ou
all o e Ω. The e a e se e al ways o model sp ead. Fo ins ance, we could use he o e all olume
occupied by he objec s, he amoun o in e sec ions be ween hem, o he dis ances be ween
he objec s. This las op ion is he one analyzed in de ail in his pape , and he e o e, ou aim
is o maximize he sum o e all he indi iduals o he dis ances be ween he objec s ep esen ing
hem. Le F2be a unc ion which, gi en he ansla ion ec o s ci, and he escaling pa ame e ,
τ, compu es he sp ead o he isualiza ion map in such way. Then, w i en in minimiza ion
o m, one has
F2:Rn×. . . ×Rn×R+−→ R+
(c1,...,cN, τ)7−→ − X
i,j=1,...,N
i6=j
g2(ci,cj, τ).
No e ha F2does no dis inguish be ween how much he objec s in e sec , since i penalizes
in he same way wo objec s one on op o he o he as wo angen objec s. A possible way
o quan i y he amoun o in e sec ion be ween wo objec s is by measu ing he minimum-no m
ansla ion o such objec s which makes hem no o in e sec . This leads o he concep o
pene a ion dep h, [23,56].
Le k·kbe a no m in Rn. Gi en wo con ex compac se s, A1, A2∈Rn, he pene a ion
dep h o A1, A2is de ined as
π(A1, A2) = min
p{kpk:in (p+A1)∩A2=∅} ,
whe e in deno es he in e io o a se .
Thus, he amoun o in e sec ion be ween he objec s in he isualiza ion map can be quan i-
ied as he sum o e all he indi iduals o he squa ed pene a ion dep h be ween pai s o hem,
yielding he unc ion FΠ
2de ined as
4
FΠ
2:Rn×. . . ×Rn×R+−→ R+
(c1,...,cN, τ)7−→ X
i,j=1,...,N
i6=j
π2(ci+τ iB,cj+τ jB).
Howe e , he pene a ion dep h does no measu e how sepa a ed he objec s a e. Then, an
al e na i e o he wo p e ious sp ead c i e ia, namely F2and FΠ
2, which does ake in o accoun
bo h he amoun o in e sec ion and he sepa a ion o he objec s, consis s o measu ing he
dis ance be ween he cen e s o he objec s. Maximizing he sum o e all he indi iduals o he
squa ed dis ances be ween he cen e s gi es an al e na i e sp ead c i e ion, namely
Fc
2:Rn×. . . ×Rn×R+−→ R+
(c1,...,cN, τ)7−→ − X
i,j=1,...,N
i6=j
kci−cjk2.
2.3 P oblem s a emen
The p oblem o building a isualiza ion map in which a se o con ex objec s in he o m
ci+τ iBa e ep esen ed in a egion Ω, sa is ying ha he dis ances be ween he objec s esemble
he dissimila i ies be ween he indi iduals and he map is sp ead enough, can be s a ed as a
biobjec i e op imiza ion p oblem. By p oceeding in he usual way, we conside he con ex
combina ion o he objec i es and sol e he agg ega e p oblem, see [22]. Thus, gi en λ∈[0,1],
he Visualiza ion Map p oblem, (V M), is s a ed as ollows
min
c1,...,cN,τ,κ λF1(c1,...,cN, τ, κ) + (1 −λ)F2(c1,...,cN, τ)
s. . ci+τ iB ⊆ Ω, i = 1, . . . , N
τ∈T
κ∈K,
(V M)
whe e K, T ⊂R+.
3 P ope ies
In his sec ion we s udy he s uc u e o p oblem (V M). We will p o e ha i s objec i e unc ion
is DC, by conside ing dis ance unc ions d, de ined in he space o compac con ex se s o Rn,
which sa is y he ollowing:
Assump ion 1. The unc ion d, de ined on pai s o compac con ex se s o Rn, sa is ies o
any A1,A2
(i) d≥0and dis symme ic
(ii) d(A1, A2) = d(A1+z, A2+z),∀z∈Rn
(iii) The unc ion dz:z∈Rn7−→ d(z+A1, A2)is con ex and sa is ies o all θ > 0 ha
dz(θA1, θA2) = θd1
θz(A1, A2).
Typical ins ances o dsa is ying (i)-(iii) a e
5

1. The in imum dis ance, de ined as
d(A1, A2) = in {ka1−a2k:a1∈A1, a2∈A2}(d1)
2. The sup emum dis ance, de ined as
d(A1, A2) = sup{ka1−a2k:a1∈A1, a2∈A2}(d2)
3. The a e age dis ance, de ined as
d(A1, A2) = 1
oln(A1) oln(A2)Zka1−a2kdµ1dµ2,(d3)
whe e oln(·) deno es he olume o a se in Rnand µ1, µ2a e p obabili y dis ibu ions wi h
suppo A1and A2.
No e ha he unc ions dde ined in (d1)–(d3). co espond wi h he well-known single linkage,
comple e linkage and he a e age dis ances in Clus e Analysis, [30].
Obse e ha , hanks o he Assump ion 1, he dis ance be ween wo objec s ep esen ing
indi iduals iand j, gi en by he unc ion gin (1), can be exp essed as
g(ci,cj, τ) = τd1
τ(ci−cj)( iB, jB),(2)
and hus gis he pe spec i e o he con ex unc ion (ci,cj) = dci−cj(ωiB, ωjB). Hence, gis
con ex as well, see e.g. [32] o he p oo .
Elemen a y ools o DC op imiza ion enable us o show ha objec i e unc ion in (V M),
namely λF1+ (1 −λ)F2, is DC, and a DC decomposi ion can be gi en. The esul is p esen ed
in P oposi ion 1and he p oo is included in he Appendix o he sake o comple eness.
P oposi ion 1. One has ha λF1+ (1 −λ)F2is DC, and a decomposi ion is gi en by
λF1+ (1 −λ)F2=u−(λF1+ (1 −λ)F2),
whe e
u=X
i,j=1,...,N
i6=j
max{3λ−1,0}g2(ci,cj, τ)+2λ(κδij)2
The wo al e na i e unc ions o he sp ead p esen ed in Sec ion 2, namely FΠ
2and Fc
2, a e
also DC unc ions, as s a ed in he ollowing esul s.
P oposi ion 2. Le hij be de ined as he pene a ion dep h be ween ci+τ iBand cj+τ jB,
namely
hij :Rn×Rn×R+−→ R+
(ci,cj, τ)7−→ π(ci+τ iB,cj+τ jB).
Deno ing as γ◦
B he dual no m wi h uni ball B, one has ha hij is DC, and i has a decomposi ion
in hij =u−(u−hij), whe e
u= max 


max
ξ∈Rn
kξk=1 nξ>(cj−ci)−τ( i+ j)γ◦
B(ξ),0o


,
6
P oo . See Appendix.
Co olla y 1. One has ha he unc ion λF1+ (1 −λ)FΠ
2is DC.
P oo . The unc ion F1is DC. Indeed, i is su icien o ake λ= 1 in P oposi ion 1.FΠ
2is
also DC by using P oposi ion 2and P oposi ion 3.7 in [55]. Then, since he summa ion o DC
unc ion is also DC, he esul holds.
Co olla y 2. One has ha he unc ion λF1+ (1 −λ)Fc
2is DC.
P oo . Since he unc ion F1is DC ( ake λ= 1 in P oposi ion 1) and Fc
2is conca e, since i is
minus he summa ion o squa es o a nonnega i e con ex unc ion, he esul holds.
Co olla ies 1–2s a e ha he unc ions λF1+ (1 −λ)FΠ
2and λF1+ (1 −λ)Fc
2a e DC. DC
decomposi ions o hem a e eadily a ailable om he DC decomposi ion o F1in P oposi ion
1(λ= 1), P oposi ion 2and he conca i y o Fc
2.
Showing ha a unc ion is DC and gi ing explici ly a DC decomposi ion enables us o use
DC op imiza ion algo i hms. I is well known ha he pe o mance o he p ocedu es may
s ongly depend on he choice o he DC decomposi ion, [2,4,24]. We gi e now an al e na i e
DC decomposi ion o he o m o hose add essed in [37,45], namely, a DC decomposi ion
in ol ing a quad a ic con ex sepa able unc ion. In he es o he pape , we wo k wi h he
exp ession o dgi en by (d1), namely he in imum dis ance. We will show in Sec ion 4 ha such
al e na i e decomposi ion yields a simple DCA algo i hm, whose con e gence ollows om he
gene al con e gence esul s o DCA, [36,38,44].
P oposi ion 3. The unc ion λF1+ (1 −λ)F2, whe e dis he in imum dis ance (d1), can be
exp essed as a DC unc ion, λF1+ (1 −λ)F2) = u−(u−λF1+ (1 −λ)F2), whe e he quad a ic
sepa able con ex unc ion uis gi en by
u= max{3λ−1,0} · 


X
i=1,...,N
8kcik2+τ2X
i,j=1,...,N
i6=j
βij



+ 2λκ2X
i,j=1,...,N
i6=j
δ2
ij,
whe e βij sa is ies βij ≥2k ibi− jbjk2 o all bi, bj∈ B.
P oo . See Appendix.
4 The algo i hmic app oach
P oposi ions 1-3and Co olla ies 1-2show ha (V M), as well as i s a ian s, is an op imiza-
ion p oblem wi h a DC objec i e unc ion, wi h a DC decomposi ion a ailable, and simple
cons ain s. Then, DC op imiza ion ools can be used, ei he o exac na u e o e y low di-
mensional p oblems, [2,3], o heu is ics, as he DCA, [36,38,44]. This is he app oach we
a e ollowing in his pape , and we e e he eade o [17,35] o al e na i e ma hema ical
op imiza ion app oaches o MDS.
Roughly speaking, DCA consis s o an i e a i e p ocess in which a sequence o con ex p o-
g ams a e sol ed. Gi en a DC p og am o he o m min{ (x) = u(x)− (x) : x∈Rn}, a each
i e a ion, he conca e pa (− (x)) is eplaced by i s a ine majo iza ion a a ce ain x0∈Rn,
7
and he esul ing con ex p oblem is hen sol ed. Howe e , unning imes would be d ama ically
educed i a DC decomposi ion o he objec i e we e a ailable so ha he con ex op imiza ion
p oblems o be sol ed a each s age we e i ial, in he sense ha an explici exp ession o he
op imal solu ion is a ailable. This idea has been s udied in [37,45] and i will be cus omized o
ou p oblem in wha ollows.
When he DCA scheme is applied o p oblem (V M) wi h he DC decomposi ion gi en in
P oposi ion 3, we see ha he con ex subp oblems o be sol ed a each s age ha e he o m
min
c1,...,cN,τ,κ 

X
i=1,...,N
Mc
ikcik2+Mκκ2+Mττ2+X
i=1,...,N
ci>qc
i+pκκ+pττ


s. . ci+τ iB ⊆ Ω, i = 1, . . . , N
τ∈T
κ∈K,
o scala s Mc
i,Mκ,Mτ≥0, ec o s qc
iand scala s pκand pτ.
Such p oblem is w i en as a wo sepa a e p oblems,
min
κ∈KMκκ2+pκκ+ min
ci+τ iB⊆Ω
τ∈T


X
i=1,...,N
Mci
ikck2
i+ci>qc
i+Mττ2+pττ2


(3)
The i s p oblem in (3) is a con ex p oblem in one a iable, o which a closed o m can
be gi en o i s op imal alue. The second p oblem in (3) is sepa able in he a iables cii he
linking a iable τwe e ixed a τ0. Fo his eason, an al e na ing s a egy seems o be plausible,
in which one al e na es he op imiza ion o τ o c1,...,cN ixed, (and his is a one dimensional
quad a ic p oblem and hus a closed o mula o he op imal solu ion is eadily ob ained), and
hen o τ ixed, he cen e s cia e o be op imized. Bu his is done by sol ing sepa a ely N
op imiza ion p oblems o he o m
min
ci
Mci
ikcik2+ci>qc
i
s. . ci∈Ω−τ iB.(4)
Two pa icula cases o (4) ha e an amenable s uc u e, yielding a closed o mula o he
op imal solu ion, and hus a oiding any call o nume ical op imiza ion ou ines. Indeed, suppose
Ω is a ec angle, o simplici y aken as [0,1]n, and Bis he disc cen e ed a he o igin wi h adius
0. Then, he cons ain in (4) can be ew i en as
τ0 0 i≤cij ≤1−τ0 0 i, j = 1, . . . , n,
and hus (4) is exp essed as
X
j=1,...,n
min
cij Mci
ic2
ij +qc
ijcij :τ0 0 i≤cij ≤1−τ0 0 i(5)
In o he wo ds, (4) is decomposed in o none dimensional quad a ic p oblems on an in e al,
and hus a closed o mula is eadily ob ained o he op imal solu ion o each p oblem o he
o m (5), and hus also o (4).
8
Simila ly, suppose Ω and Ba e discs cen e ed a he o igin, and adius 1 and 0 espec i ely.
Then, (4) is ew i en as
min
ci
Mci
ikcik2+ci>qc
i
s. . kcik ≤ 1−τ0 0 i.(6)
Ka ush-Kuhn-Tucke condi ions immedia ely yield an exp ession o he op imal solu ion o (6).
Summa izing, while DCA could be applied o sol e (V M) o an a bi a y DC decomposi ion
o he objec i e unc ion, we see ha he DC decomposi ion o P oposi ion 3is pa icula ly
a ac i e, since, o some con enien choices o Ω (a ec angle o a disc) and B(a disc) yield a
closed o mula o he op imal solu ion o he subp oblems o be add essed a each s age o he
DCA, hus a oiding he need o using nume ical op imiza ion ou ines. See [37] also o o he
p oblems in which his s a egy has been success ul.
5 Nume ical illus a ions
The me hodology in Sec ion 4is illus a ed using wo eal-wo ld da ase s o di e se na u e, o be
plo ed in wo di e en isualiza ion egions Ω ⊆R2. The DCA algo i hm has been coded in C
and he expe imen s ha e been ca ied ou in a Windows 8.1 PC In el Co eTM i7-4500U, 16GB
o RAM. The i s da ase consis s o N= 11 inancial ma ke s ac oss Eu ope and Asia. The
s a is ical alue ωi ela es o he impo ance o ma ke i ela i e o he wo ld ma ke po olio,
[25], and he dissimila i y δij is based on he co ela ion be ween ma ke s iand j, [5]. The
second da ase is a social ne wo k o N= 200 musicians, modeled as a g aph, whe e he e is an
a c connec ing wo nodes i one musician was in luen ial on he o he , [20]. The s a is ical alue
ωi ep esen s he ou deg ee o node iand he dissimila i y be ween musicians iand jis based
on he sho es dis ance om node i o j.
Th oughou his sec ion, we se λ= 0.9 and Bequal o he ci cle cen e ed a (0,0) wi h
adius equal o one. Since (V M) is a mul imodal p oblem and he DCA may ge s uck a a local
op imum, 100 uns o a mul is a a e execu ed. A each un, 3 s eps o an al e na ing p ocedu e
a e pe o med, whe e each s ep execu es 50 i e a ions o he DCA o op imize c1,...,cN, κ o
τ ixed, and hen τis sol ed analy ically o he so-ob ained c1,...,cN, κ.
Figu e 2plo s he inancial ma ke s da ase on he isualiza ion egion Ω = [0,1] ×[0,1],
wi h he scaling pa ame e s anging in he in e als K=T= [0.4,0.6]. Obse e ha , he
Eu opean ma ke s a e clus e ed abo e he Asian ones, co e ing he uppe hal ec angle. These
wo clus e s a e ep esen ed wi h di e en colou s. Figu e 3plo s he musicians’ social ne wo k
aking a ci cula isualiza ion egion, namely Ω = B, wi h he scaling pa ame e s anging in
he in e als K= [0.075,0.100] and T= [0.015,0.030], espec i ely. In he plo a he op, we
ind all musicians. In he plo a he bo om, we ha e highligh ed one o he mos in luen ial
nodes, he Rolling S ones, and he connec ed nodes: musicians in luencing he Rolling S ones
( espec i ely, hose in luenced by hem) can be ound in a ligh e ( espec i ely da ke ) colou .
6 Concluding ema ks and ex ensions
In his pape we ha e add essed he p oblem o ep esen ing, in a so-called isualiza ion egion
Ω, a se o indi iduals by means o con ex objec s so ha he dis ance be ween he objec s i s
9
[58] Z. Wang, S. Zheng, Y. Ye, and S. Boyd. Fu he elaxa ions o he semide ini e p og amming
app oach o senso ne wo k localiza ion. SIAM Jou nal on Op imiza ion, 19(2):655–673,
2008.
Appendix
P oo o P oposi ion 1
One has
λF1+ (1 −λ)F2=
=X
i,j=1,...,N
i6=j
nλg2(ci,cj, τ)−κδij2−(1 −λ)g2(ci,cj, τ)o
=X
i,j=1,...,N
i6=j(3λ−1)g2(ci,cj, τ)+2λκ2δ2
ij −λ(g(ci,cj, τ) + κδij)2
In Sec ion 2.1, he con exi y o he unc ion gwas s a ed. Mo eo e , since g,λ,δij ≥0, hen
g2(ci,cj, τ), 2λκ2δ2
ij and (g(ci,cj, τ) + Kδij)2a e con ex. Finally, (3λ−1)g2(ci,cj, τ) is con ex
o 3λ−1≥0 and conca e o he wise. 
P oo o P oposi ion 2
Fo con ex se s A1, A2, he condi ion in De ini ion 2.2 is equi alen o he exis ence o a sepa-
a ing hype plane be ween he se s p+A1and A2,i.e., o some ξ6= 0,such ha
ξ>(p+a1)≤ξ>a2∀a1∈A1,a2∈A2.
Wi hou loss o gene ali y, we can conside kξk= 1 and hus we ha e
π(A1, A2) = min
p,ξ∈Rnkpk
s. . ξ>(p+a1)≤ξ>a2∀a1∈A1,a2∈A2
kξk= 1.
Thus, hij can be w i en as ollows
hij(ci,cj, τ) = min
p,ξ∈Rnkpk
s. . ξ>(p+ci+τ ixi)≤ξ>(cj+τ jxj)∀xi,xj∈ B
kξk= 1.
Equi alen ly, he i s cons ain , i.e.,
ξ>(p+ci+τ ixi)≤ξ>(cj+τ jxj)∀xi,xj∈ B,
16

can be w i en as ollows,
ξ>(p+ci) + τ imax
x∈B ξ>x≤ξ>cj+τ jmin
x∈B ξ>x.
Le γ◦
Bdeno e he dual o he no m wi h uni ball B,i.e.,
γ◦
B(z) = max
y{y>z:y∈ B}
Since Bis assumed o be symme ic wi h espec o he o igin, we ha e
max
x∈B ξ>x=γ◦
B(ξ)
min
x∈B ξ>x=−γ◦
B(ξ).
Hence, by eplacing he exp ession o he dual no m in he cons ain abo e, one has
hij(ci,cj, τ) = min
p,ξ∈Rnkpk
s. . ξ>p≤ξ>(cj−ci)−τ( i+ j)γ◦
B(ξ)
kξk= 1.
Fo ξ ixed wi h kξk= 1,le η(ξ) = ξ>(cj−ci)−τ( i+ j)γ◦
B(ξ).I ollows ha he
inne minimum in hij (ci,cj, τ),i.e., o ξ ixed, is he dis ance om he o igin o he hal space
ξ>p≤η(ξ),and such dis ance equals 0, i 0 belongs o he hal space, i.e., i 0 ≤ξ>(cj−ci)−
τ( i+ j)γ◦
B(ξ),and −η(ξ) else. Hence
hij(ci,cj, τ) = min
ξ∈Rn
kξk=1
max n0,−ξ>(cj−ci) + τ( i+ j)γ◦
B(ξ)o
= max 


0,min
ξ∈Rn
kξk=1
−ξ>(cj−ci) + τ( i+ j)γ◦
B(ξ)


Bu , o ξ ixed, he unc ion (ci,cj, τ)7−→ −ξ>(cj−ci) + τ( i+ j)γ◦
B(ξ) is a ine, and
hus he unc ion (ci,cj, τ)7−→ min
ξ∈Rn
kξk=1
−ξ>(cj−ci) + τ( i+ j)γ◦
B(ξ) is he minimum o a ine
unc ions, and is hus conca e. Hence, hij is he maximum be ween 0 and a conca e unc ion,
which is DC, whose decomposi ion is
hij(ci,cj, τ) =
= max 


0,min
ξ∈Rn
kξk=1 n−ξ>(cj−ci) + τ( i+ j)γ◦
B(ξ)o


= max 


−min
ξ∈Rn
kξk=1 n−ξ>(cj−ci) + τ( i+ j)γ◦
B(ξ)o,0


+ min
ξ∈Rn
kξk=1 n−ξ>(cj−ci) + τ( i+ j)γ◦
B(ξ)o
= max 


max
ξ∈Rn
kξk=1 nξ>(cj−ci)−τ( i+ j)γ◦
B(ξ),0o


−max
ξ∈Rn
kξk=1 nξ>(cj−ci)−τ( i+ j)γ◦
B(ξ)o
17
=u(ci,cj, τ)−(u(ci,cj, τ)−hij(ci,cj, τ)).

P oo o P oposi ion 3
Be o e gi ing he p oo o P oposi ion 3, he ollowing echnical esul is needed.
Lemma 1. Le βij ∈Rbe such ha βij ≥2k ibi− jbjk2,∀bi,bj∈ B. Then, g2can be exp essed
as a DC unc ion, g2=u−(u−g2), whe e
u= 2kci−cjk2+βijτ2.
P oo .
g2(ci,cj, τ) =
= min
bi,bj∈B kci−cj+τ( ibi− jbj)k2
= min
bi,bj∈B nkci−cjk2+τ2k ibi− jbjk2+ 2τ(ci−cj)>( ibi− jbj)o
= min
bi,bj∈B kci−cjk2+τ2k ibi− jbjk2
+kci−cjk2+τ2k ibi− jbjk2− kci−cj−τ( ibi− jbj)k2
= 2kci−cjk2+βijτ2+ min
bi,bj∈B −βijτ2+ 2τ2k ibi− jbjk2− kci−cj−τ( ibi− jbj)k2
= 2kci−cjk2+βijτ2+ min
bi,bj∈B τ22k ibi− jbjk2−βij− kci−cj−τ( ibi− jbj)k2
= 2kci−cjk2+βijτ2−max
bi,bj∈B kci−cj−τ( ibi− jbj)k2−τ22k ibi− jbjk2−βij
Obse e ha aking βij ∈Rsuch ha
2k ibi− jbjk2−βij ≤0∀bi,bj∈ B,
he unc ion
(ci,cj, τ)7−→ kci−cj−τ( ibi− jbj)k2−τ22k ibi− jbjk2−βij
is con ex. Since he maximum o con ex unc ions is con ex, hence aking u= 2kci−cjk2+βijτ2,
we ha e ob ained a DC decomposi ion o g2as in he s a emen .
We p oo now P oposi ion 3:
I λ < 1
3, conside ing P oposi ion 1, one has
λF1+ (1 −λ)F2=X
i,j=1,...,N
i6=j2λκ2δ2
ij −λ(g+κδij)2−(3λ−1)g2(ci,cj, τ),
18
and hus u=X
i,j=1,...,N
i6=j
2λκ2δ2
ij holds.
I λ≥1
3, by using he DC decomposi ion o g2ob ained in Lemma 1and P oposi ion 1,
one has
λF1+ (1 −λ)F2=
=X
i,j=1,...,N
i6=j(3λ−1)g2(ci,cj, τ)+2λκ2δ2
ij −λ(g(ci,cj, τ) + κδij)2
=X
i,j=1,...,N
i6=j2(3λ−1)kci−cjk2+ (3λ−1)βijτ2+ 2λκ2δ2
ij −λ(g(ci,cj, τ) + κδij)2
+ (3λ−1) max
bi,bj∈B kci−cj−τ( ibi− jbj)k2−τ22k ibi− jbjk2−βij
=X
i=1,...,N
8(3λ−1)(N−1)kcik2+ (3λ−1)τ2X
i,j=1,...,N
i6=j
βij + 2λκ2X
i,j=1,...,N
i6=j
δ2
ij
−(3λ−1)kci+cjk2+λ(g(ci,cj, τ) + κδij)2
+ (3λ−1) max
bi,bj∈B kci−cj−τ( ibi− jbj)k2−τ22k ibi− jbjk2−βij

19