Visualizing data as objects by DC (difference of convex) optimization

Visualizing data as objects by DC (difference of convex) optimization Emilio Carrizosa1, Vanesa Guerrero1, and Dolores Romero Morales2 1Instituto de Matem´aticas de la Universidad de Sevilla (IMUS), Seville, Spain {ecarrizosa, vguerrero}@us.es 2Copenhagen Business School, Frederiksberg, Denmark [email protected] Abstract In this paper we address the problem of visualizing in a bounded region a set of individuals, which has attached a dissimilarity measure and a statistical value. This problem, which extends the standard Multidimensional Scaling Analysis, is written as a global optimization problem whose objective is the difference of two convex functions (DC). Suitable DC decompositions allow us to use the DCA algorithm in a very efficient way. Our algorithmic approach is used to visualize two real-world datasets. Keywords: Data Visualization, DC functions, DC algorithm, Multidimensional Scaling Analysis 1 Introduction In the Big Data era, Data Visualization is an area of interest to specialists from a wide variety of disciplines, [14,15,26,27]. The information managed must be processed and, what is even more important, understood. Data Visualization techniques arise to respond to this requirement by developing specific frameworks to depict complex data structures as easy-to-interpret graphics, [40,50]. Mathematical Optimization has contributed significantly to the development of this area during recent years, see [13,30,42] and the references therein. Nowadays, complex datasets pose new challenges in order to visualize the data in such a way that patterns are captured and useful information is extracted. Special attention is paid to represent the underlying dissimilarity relationships that data may have. Classical dimensionality reduction techniques, such as Principal Component Analysis, [43], or Multidimensional Scaling (MDS), [29,34,52], have been customized to deal with more complex data structures, [1,5,16], and to make the interpretability of the results easier via, for instance, sparse models, [9,8,18]. Apart from adapting existing methods, specific problems may call also for new approaches. For instance, in addition to the dissimilarity measure, the data may have attached a statistical variable, to be related with the size of each object in the graphical representation of the dataset, [20]. This is the case for geographical data, to be visualized on a map in which countries are resized according to, for instance, population rates, but maintaining the neighboring relationships 1 of countries. This type of representations, known as cartograms, [51], leads to plots in which countries are replaced by geometrical objects, frequently circles or rectangles, while the neighborhood relationships and the size of the objects are sought to be well represented. A key issue is how such problems are expressed as optimization programs, and which optimization tools are available to cope with them. For uses of optimization applied to cartograms construction and related visualization frameworks we refer the reader to [6,10,11,20,21,28,31,47,49] and references therein. In this paper we present a new mathematical programming framework to build a visualization map, in which a set of Nindividuals are depicted as convex objects in a bounded region Ω ⊂Rn, usually n≤3. These objects must have a volume proportional to a given statistical value associated with the individuals, ω= (ω1, . . . , ωN), and they should be placed accordingly to a dissimilarity measure attached to the individuals, δ= (δij)i,j=1,...,N . In order to locate the objects in Ω, a reference object Bis used, to be translated and expanded. However, since our final goal is to obtain a visualization map which allows the analysts to understand the data they are working with, a criterion which somehow controls the appearance of the plot needs to be also considered. We will deal with this paradigm by focusing on how the objects are spread out over Ω. Leaving aside the statistical values ω, the purpose of representing dissimilarities between individuals reminds to MDS, [5,16,18,29,34,35,39,52], which aims to represent the dissimilarity between individuals as empirical distances between points in an unbounded space of lower dimension. Although our visualization model may seem very close to MDS, it has the special feature of representing in the bounded region Ω not only dissimilarities as distances between objects, but also the statistical measure ωthrough the volumes of the objects in Ω. Our visualization tool is able to rescale the dissimilarities between the individuals and the statistical values associated to them to fit in Ω. Observe that fitting the objects into Ω may yield representations in which the objects intersect if their sizes are not small enough, but, on the other hand, too small objects obstruct the visualization of the statistical measure. Ideally the objects should be spread out across the visualization map. This aim will be also taken into account when modeling the problem. The methodology proposed in this paper has applications in fields others than Data Visualization, such as for instance, Location Analysis or Distance Geometry. In location problems, the facilities to be located are usually considered as points. However, a natural extension is to consider facilities as dimensional structures, see [19], and DC techniques have been specifically applied to this generalization, [3,12]. Ours can also be seen as a problem in Distance Geometry optimization, as carefully reviewed in [39]. In Distance Geometry, a graph realization problem consists of finding a configuration of points such that their (Euclidean) distances fit a given dissimilarity matrix. Among them is the Sensor Network Location problem, [46,48,54,58], in which one assumes that some individuals are anchors (their location is known) and the remaining ones are sensors, whose location is to be obtained so that their Eculidean distances fit the dissimilarities. Thus, our method can also be applied to the Sensor Network Location problem, in which sensors and anchors have a nonnegligible area. In this paper, the construction of a visualization map with the three characteristics mentioned above is written as a global biobjective optimization problem with convex constraints. We show that the objective function of the aggregate problem can be expressed as a difference of convex (DC) function, and thus DC optimization tools can be used to solve the optimization program. The rest of the paper is organized as follows. In Section 2the biobjective optimization 2 program to build the visualization map is formalized. In Section 3, structural properties of the optimization problem are analyzed. In Section 4, we present our algorithmic approach. Numerical results for two datasets of different size and nature are included in Section 5. Some conclusions and extensions are presented in Section 6. 2 The visualization model In our model we have a reference object B, which is a compact convex subset of Rn, symmetric with respect to the origin, interior to B. Each individual iis associated with a set of the form ci+τriB, where ri≥0 is chosen so that the volume of riBis proportional to the statistical value ωi≥0, ciis a translation vector and τis a common positive rescaling for all objects. We seek the values of the variables ci,i= 1, . . . , N, and τso that objects ci+τriBare contained in Ω. The previously described representation is illustrated in Figure 1. Ω B ci+τriB ci cj+τrjB cj ck+τrkB ck Figure 1: Example in R2of a visualization region Ω, a reference object Band three individuals i,jand kdefined through the translation vectors ci,cjand ck, which are scaled via τri,τrj and τrk. Henceforth, we deal with a biobjective optimization problem: the distances between the objects representing the individuals iand jmust resemble the dissimilarities δij between such individuals, and the objects must be spread out in Ω to make the visualization easier. The two criteria are formalized in what follows. 2.1 First objective: distances resemble dissimilarities Regarding the first objective, a function d, which gives us a strictly positive distance between two non-intersecting objects representing individuals iand jand zero otherwise, needs to be considered. Thus, we define the function g, which assigns such distance to two individuals iand 3 j, as follows g:Rn×Rn×R+−→ R+ (ci,cj, τ)7−→ d(ci+τriB,cj+τrjB).(1) Then, to quantify the resemblance between the distances in the visualization map and the dissimilarities, the summation over all the individuals of the squared differences between the distances and the rescaled dissimilarities through a positive variable κwill be minimized. Thus, we consider as first objective the function F1defined as F1:Rn×. . . ×Rn×R+×R+−→ R+ (c1,...,cN, τ, κ)7−→ X i,j=1,...,N i6=j [g(ci,cj, τ)−κδij]2. Observe that for simplicity all pairs (i, j) are considered in the summation in F1, but our analysis remains valid if only some (i, j) pairs of objects, as done e.g. in [53]. 2.2 Second objective: spread To avoid that the objects collapse in a small subregion of Ω, we encourage objects to be spread out all over Ω. There are several ways to model spread. For instance, we could use the overall volume occupied by the objects, the amount of intersections between them, or the distances between the objects. This last option is the one analyzed in detail in this paper, and therefore, our aim is to maximize the sum over all the individuals of the distances between the objects representing them. Let F2be a function which, given the translation vectors ci, and the rescaling parameter, τ, computes the spread of the visualization map in such way. Then, written in minimization form, one has F2:Rn×. . . ×Rn×R+−→ R+ (c1,...,cN, τ)7−→ − X i,j=1,...,N i6=j g2(ci,cj, τ). Note that F2does not distinguish between how much the objects intersect, since it penalizes in the same way two objects one on top of the other as two tangent objects. A possible way to quantify the amount of intersection between two objects is by measuring the minimum-norm translation of such objects which makes them not to intersect. This leads to the concept of penetration depth, [23,56]. Let k·kbe a norm in Rn. Given two convex compact sets, A1, A2∈Rn,the penetration depth of A1, A2is defined as π(A1, A2) = min p{kpk:int(p+A1)∩A2=∅} , where int denotes the interior of a set. Thus, the amount of intersection between the objects in the visualization map can be quantified as the sum over all the individuals of the squared penetration depth between pairs of them, yielding the function FΠ 2defined as 4 FΠ 2:Rn×. . . ×Rn×R+−→ R+ (c1,...,cN, τ)7−→ X i,j=1,...,N i6=j π2(ci+τriB,cj+τrjB). However, the penetration depth does not measure how separated the objects are. Then, an alternative to the two previous spread criteria, namely F2and FΠ 2, which does take into account both the amount of intersection and the separation of the objects, consists of measuring the distance between the centers of the objects. Maximizing the sum over all the individuals of the squared distances between the centers gives an alternative spread criterion, namely Fc 2:Rn×. . . ×Rn×R+−→ R+ (c1,...,cN, τ)7−→ − X i,j=1,...,N i6=j kci−cjk2. 2.3 Problem statement The problem of building a visualization map in which a set of convex objects in the form ci+τriBare represented in a region Ω, satisfying that the distances between the objects resemble the dissimilarities between the individuals and the map is spread enough, can be stated as a biobjective optimization problem. By proceeding in the usual way, we consider the convex combination of the objectives and solve the aggregate problem, see [22]. Thus, given λ∈[0,1], the Visualization Map problem, (V M), is stated as follows min c1,...,cN,τ,κ λF1(c1,...,cN, τ, κ) + (1 −λ)F2(c1,...,cN, τ) s.t. ci+τriB ⊆ Ω, i = 1, . . . , N τ∈T κ∈K, (V M) where K, T ⊂R+. 3 Properties In this section we study the structure of problem (V M). We will prove that its objective function is DC, by considering distance functions d, defined in the space of compact convex sets of Rn, which satisfy the following: Assumption 1. The function d, defined on pairs of compact convex sets of Rn, satisfies for any A1,A2 (i) d≥0and dis symmetric (ii) d(A1, A2) = d(A1+z, A2+z),∀z∈Rn (iii) The function dz:z∈Rn7−→ d(z+A1, A2)is convex and satisfies for all θ > 0that dz(θA1, θA2) = θd1 θz(A1, A2). Typical instances of dsatisfying (i)-(iii) are 5 1. The infimum distance, defined as d(A1, A2) = inf{ka1−a2k:a1∈A1, a2∈A2}(d1) 2. The supremum distance, defined as d(A1, A2) = sup{ka1−a2k:a1∈A1, a2∈A2}(d2) 3. The average distance, defined as d(A1, A2) = 1 voln(A1)voln(A2)Zka1−a2kdµ1dµ2,(d3) where voln(·) denotes the volume of a set in Rnand µ1, µ2are probability distributions with support A1and A2. Note that the functions ddefined in (d1)–(d3). correspond with the well-known single linkage, complete linkage and the average distances in Cluster Analysis, [30]. Observe that, thanks to the Assumption 1, the distance between two objects representing individuals iand j, given by the function gin (1), can be expressed as g(ci,cj, τ) = τd1 τ(ci−cj)(riB, rjB),(2) and thus gis the perspective of the convex function f(ci,cj) = dci−cj(ωiB, ωjB). Hence, gis convex as well, see e.g. [32] for the proof. Elementary tools of DC optimization enable us to show that objective function in (V M), namely λF1+ (1 −λ)F2, is DC, and a DC decomposition can be given. The result is presented in Proposition 1and the proof is included in the Appendix for the sake of completeness. Proposition 1. One has that λF1+ (1 −λ)F2is DC, and a decomposition is given by λF1+ (1 −λ)F2=u−(λF1+ (1 −λ)F2), where u=X i,j=1,...,N i6=j max{3λ−1,0}g2(ci,cj, τ)+2λ(κδij)2 The two alternative functions for the spread presented in Section 2, namely FΠ 2and Fc 2, are also DC functions, as stated in the following results. Proposition 2. Let hij be defined as the penetration depth between ci+τriBand cj+τrjB, namely hij :Rn×Rn×R+−→ R+ (ci,cj, τ)7−→ π(ci+τriB,cj+τrjB). Denoting as γ◦ Bthe dual norm with unit ball B, one has that hij is DC, and it has a decomposition in hij =u−(u−hij), where u= max    max ξ∈Rn kξk=1 nξ>(cj−ci)−τ(ri+rj)γ◦ B(ξ),0o   , 6 Proof. See Appendix. Corollary 1. One has that the function λF1+ (1 −λ)FΠ 2is DC. Proof. The function F1is DC. Indeed, it is sufficient to take λ= 1 in Proposition 1.FΠ 2is also DC by using Proposition 2and Proposition 3.7 in [55]. Then, since the summation of DC function is also DC, the result holds. Corollary 2. One has that the function λF1+ (1 −λ)Fc 2is DC. Proof. Since the function F1is DC (take λ= 1 in Proposition 1) and Fc 2is concave, since it is minus the summation of squares of a nonnegative convex function, the result holds. Corollaries 1–2state that the functions λF1+ (1 −λ)FΠ 2and λF1+ (1 −λ)Fc 2are DC. DC decompositions for them are readily available from the DC decomposition of F1in Proposition 1(λ= 1), Proposition 2and the concavity of Fc 2. Showing that a function is DC and giving explicitly a DC decomposition enables us to use DC optimization algorithms. It is well known that the performance of the procedures may strongly depend on the choice of the DC decomposition, [2,4,24]. We give now an alternative DC decomposition of the form of those addressed in [37,45], namely, a DC decomposition involving a quadratic convex separable function. In the rest of the paper, we work with the expression of dgiven by (d1), namely the infimum distance. We will show in Section 4that such alternative decomposition yields a simple DCA algorithm, whose convergence follows from the general convergence results of DCA, [36,38,44]. Proposition 3. The function λF1+ (1 −λ)F2, where dis the infimum distance (d1), can be expressed as a DC function, λF1+ (1 −λ)F2) = u−(u−λF1+ (1 −λ)F2), where the quadratic separable convex function uis given 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, where βij satisfies βij ≥2kribi−rjbjk2for all bi, bj∈ B. Proof. See Appendix. 4 The algorithmic approach Propositions 1-3and Corollaries 1-2show that (V M), as well as its variants, is an optimization problem with a DC objective function, with a DC decomposition available, and simple constraints. Then, DC optimization tools can be used, either of exact nature for very low dimensional problems, [2,3], or heuristics, as the DCA, [36,38,44]. This is the approach we are following in this paper, and we refer the reader to [17,35] for alternative mathematical optimization approaches to MDS. Roughly speaking, DCA consists of an iterative process in which a sequence of convex programs are solved. Given a DC program of the form min{f(x) = u(x)−v(x) : x∈Rn}, at each iteration, the concave part (−v(x)) is replaced by its affine majorization at a certain x0∈Rn, 7 and the resulting convex problem is then solved. However, running times would be dramatically reduced if a DC decomposition of the objective were available so that the convex optimization problems to be solved at each stage were trivial, in the sense that an explicit expression for the optimal solution is available. This idea has been studied in [37,45] and it will be customized to our problem in what follows. When the DCA scheme is applied to problem (V M) with the DC decomposition given in Proposition 3, we see that the convex subproblems to be solved at each stage have the form min c1,...,cN,τ,κ   X i=1,...,N Mc ikcik2+Mκκ2+Mττ2+X i=1,...,N ci>qc i+pκκ+pττ   s.t. ci+τriB ⊆ Ω, i = 1, . . . , N τ∈T κ∈K, for scalars Mc i,Mκ,Mτ≥0, vectors qc iand scalars pκand pτ. Such problem is written as a two separate problems, min κ∈KMκκ2+pκκ+ min ci+τriB⊆Ω τ∈T   X i=1,...,N Mci ikck2 i+ci>qc i+Mττ2+pττ2   (3) The first problem in (3) is a convex problem in one variable, for which a closed form can be given for its optimal value. The second problem in (3) is separable in the variables ciif the linking variable τwere fixed at τ0. For this reason, an alternating strategy seems to be plausible, in which one alternates the optimization of τfor c1,...,cNfixed, (and this is a one dimensional quadratic problem and thus a closed formula for the optimal solution is readily obtained), and then for τfixed, the centers ciare to be optimized. But this is done by solving separately N optimization problems of the form min ci Mci ikcik2+ci>qc i s.t. ci∈Ω−τriB.(4) Two particular cases of (4) have an amenable structure, yielding a closed formula for the optimal solution, and thus avoiding any call to numerical optimization routines. Indeed, suppose Ω is a rectangle, for simplicity taken as [0,1]n, and Bis the disc centered at the origin with radius r0. Then, the constraint in (4) can be rewritten as τ0r0ri≤cij ≤1−τ0r0ri, j = 1, . . . , n, and thus (4) is expressed as X j=1,...,n min cij Mci ic2 ij +qc ijcij :τ0r0ri≤cij ≤1−τ0r0ri(5) In other words, (4) is decomposed into none dimensional quadratic problems on an interval, and thus a closed formula is readily obtained for the optimal solution of each problem of the form (5), and thus also for (4). 8 Similarly, suppose Ω and Bare discs centered at the origin, and radius 1 and r0respectively. Then, (4) is rewritten as min ci Mci ikcik2+ci>qc i s.t. kcik ≤ 1−τ0r0ri.(6) Karush-Kuhn-Tucker conditions immediately yield an expression for the optimal solution of (6). Summarizing, while DCA could be applied to solve (V M) for an arbitrary DC decomposition of the objective function, we see that the DC decomposition of Proposition 3is particularly attractive, since, for some convenient choices of Ω (a rectangle or a disc) and B(a disc) yield a closed formula for the optimal solution of the subproblems to be addressed at each stage of the DCA, thus avoiding the need of using numerical optimization routines. See [37] also for other problems in which this strategy has been successful. 5 Numerical illustrations The methodology in Section 4is illustrated using two real-world datasets of diverse nature, to be plotted in two different visualization regions Ω ⊆R2. The DCA algorithm has been coded in C and the experiments have been carried out in a Windows 8.1 PC IntelrCoreTM i7-4500U, 16GB of RAM. The first dataset consists of N= 11 financial markets across Europe and Asia. The statistical value ωirelates to the importance of market irelative to the world market portfolio, [25], and the dissimilarity δij is based on the correlation between markets iand j, [5]. The second dataset is a social network of N= 200 musicians, modeled as a graph, where there is an arc connecting two nodes if one musician was influential on the other, [20]. The statistical value ωirepresents the out degree of node iand the dissimilarity between musicians iand jis based on the shortest distance from node ito j. Throughout this section, we set λ= 0.9 and Bequal to the circle centered at (0,0) with radius equal to one. Since (V M) is a multimodal problem and the DCA may get stuck at a local optimum, 100 runs of a multistart are executed. At each run, 3 steps of an alternating procedure are performed, where each step executes 50 iterations of the DCA to optimize c1,...,cN, κ for τfixed, and then τis solved analytically for the so-obtained c1,...,cN, κ. Figure 2plots the financial markets dataset on the visualization region Ω = [0,1] ×[0,1], with the scaling parameters ranging in the intervals K=T= [0.4,0.6]. Observe that, the European markets are clustered above the Asian ones, covering the upper half rectangle. These two clusters are represented with different colours. Figure 3plots the musicians’ social network taking a circular visualization region, namely Ω = B, with the scaling parameters ranging in the intervals K= [0.075,0.100] and T= [0.015,0.030], respectively. In the plot at the top, we find all musicians. In the plot at the bottom, we have highlighted one of the most influential nodes, the Rolling Stones, and the connected nodes: musicians influencing the Rolling Stones (respectively, those influenced by them) can be found in a lighter (respectively darker) colour. 6 Concluding remarks and extensions In this paper we have addressed the problem of representing, in a so-called visualization region Ω, a set of individuals by means of convex objects so that the distance between the objects fits 9 [58] Z. Wang, S. Zheng, Y. Ye, and S. Boyd. Further relaxations of the semidefinite programming approach to sensor network localization. SIAM Journal on Optimization, 19(2):655–673, 2008. Appendix Proof of Proposition 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 Section 2.1, the convexity of the function gwas stated. Moreover, since g,λ,δij ≥0, then g2(ci,cj, τ), 2λκ2δ2 ij and (g(ci,cj, τ) + Kδij)2are convex. Finally, (3λ−1)g2(ci,cj, τ) is convex for 3λ−1≥0 and concave otherwise.  Proof of Proposition 2 For convex sets A1, A2, the condition in Definition 2.2 is equivalent to the existence of a separating hyperplane between the sets p+A1and A2,i.e., of some ξ6= 0,such that ξ>(p+a1)≤ξ>a2∀a1∈A1,a2∈A2. Without loss of generality, we can consider kξk= 1 and thus we have π(A1, A2) = min p,ξ∈Rnkpk s.t. ξ>(p+a1)≤ξ>a2∀a1∈A1,a2∈A2 kξk= 1. Thus, hij can be written as follows hij(ci,cj, τ) = min p,ξ∈Rnkpk s.t. ξ>(p+ci+τrixi)≤ξ>(cj+τrjxj)∀xi,xj∈ B kξk= 1. Equivalently, the first constraint, i.e., ξ>(p+ci+τrixi)≤ξ>(cj+τrjxj)∀xi,xj∈ B, 16 can be written as follows, ξ>(p+ci) + τrimax x∈B ξ>x≤ξ>cj+τrjmin x∈B ξ>x. Let γ◦ Bdenote the dual of the norm with unit ball B,i.e., γ◦ B(z) = max y{y>z:y∈ B} Since Bis assumed to be symmetric with respect to the origin, we have max x∈B ξ>x=γ◦ B(ξ) min x∈B ξ>x=−γ◦ B(ξ). Hence, by replacing the expression of the dual norm in the constraint above, one has hij(ci,cj, τ) = min p,ξ∈Rnkpk s.t. ξ>p≤ξ>(cj−ci)−τ(ri+rj)γ◦ B(ξ) kξk= 1. For ξfixed with kξk= 1,let η(ξ) = ξ>(cj−ci)−τ(ri+rj)γ◦ B(ξ).It follows that the inner minimum in hij (ci,cj, τ),i.e., for ξfixed, is the distance from the origin to the halfspace ξ>p≤η(ξ),and such distance equals 0, if 0 belongs to the halfspace, i.e., if 0 ≤ξ>(cj−ci)− τ(ri+rj)γ◦ B(ξ),and −η(ξ) else. Hence hij(ci,cj, τ) = min ξ∈Rn kξk=1 max n0,−ξ>(cj−ci) + τ(ri+rj)γ◦ B(ξ)o = max    0,min ξ∈Rn kξk=1 −ξ>(cj−ci) + τ(ri+rj)γ◦ B(ξ)   But, for ξfixed, the function (ci,cj, τ)7−→ −ξ>(cj−ci) + τ(ri+rj)γ◦ B(ξ) is affine, and thus the function (ci,cj, τ)7−→ min ξ∈Rn kξk=1 −ξ>(cj−ci) + τ(ri+rj)γ◦ B(ξ) is the minimum of affine functions, and is thus concave. Hence, hij is the maximum between 0 and a concave function, which is DC, whose decomposition is hij(ci,cj, τ) = = max    0,min ξ∈Rn kξk=1 n−ξ>(cj−ci) + τ(ri+rj)γ◦ B(ξ)o   = max    −min ξ∈Rn kξk=1 n−ξ>(cj−ci) + τ(ri+rj)γ◦ B(ξ)o,0   + min ξ∈Rn kξk=1 n−ξ>(cj−ci) + τ(ri+rj)γ◦ B(ξ)o = max    max ξ∈Rn kξk=1 nξ>(cj−ci)−τ(ri+rj)γ◦ B(ξ),0o   −max ξ∈Rn kξk=1 nξ>(cj−ci)−τ(ri+rj)γ◦ B(ξ)o 17 =u(ci,cj, τ)−(u(ci,cj, τ)−hij(ci,cj, τ)).  Proof of Proposition 3 Before giving the proof of Proposition 3, the following technical result is needed. Lemma 1. Let βij ∈Rbe such that βij ≥2kribi−rjbjk2,∀bi,bj∈ B. Then, g2can be expressed as a DC function, g2=u−(u−g2), where u= 2kci−cjk2+βijτ2. Proof. g2(ci,cj, τ) = = min bi,bj∈B kci−cj+τ(ribi−rjbj)k2 = min bi,bj∈B nkci−cjk2+τ2kribi−rjbjk2+ 2τ(ci−cj)>(ribi−rjbj)o = min bi,bj∈B kci−cjk2+τ2kribi−rjbjk2 +kci−cjk2+τ2kribi−rjbjk2− kci−cj−τ(ribi−rjbj)k2 = 2kci−cjk2+βijτ2+ min bi,bj∈B −βijτ2+ 2τ2kribi−rjbjk2− kci−cj−τ(ribi−rjbj)k2 = 2kci−cjk2+βijτ2+ min bi,bj∈B τ22kribi−rjbjk2−βij− kci−cj−τ(ribi−rjbj)k2 = 2kci−cjk2+βijτ2−max bi,bj∈B kci−cj−τ(ribi−rjbj)k2−τ22kribi−rjbjk2−βij Observe that taking βij ∈Rsuch that 2kribi−rjbjk2−βij ≤0∀bi,bj∈ B, the function (ci,cj, τ)7−→ kci−cj−τ(ribi−rjbj)k2−τ22kribi−rjbjk2−βij is convex. Since the maximum of convex functions is convex, hence taking u= 2kci−cjk2+βijτ2, we have obtained a DC decomposition for g2as in the statement. We proof now Proposition 3: If λ < 1 3, considering Proposition 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 thus u=X i,j=1,...,N i6=j 2λκ2δ2 ij holds. If λ≥1 3, by using the DC decomposition for g2obtained in Lemma 1and Proposition 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−τ(ribi−rjbj)k2−τ22kribi−rjbjk2−β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−τ(ribi−rjbj)k2−τ22kribi−rjbjk2−βij  19