Finding the principal points of a random variable

RAIRO Operations Research RAIRO Oper. Res. 35 (2001) 315-328 FINDING THE PRINCIPAL POINTS OF A RANDOM VARIABLE ∗ Emilio Carrizosa1, E. Conde1,A.Casta ˜ no2and D. Romero–Morales1,3 Communicated by Erol Gelenbe Abstract.Thep-principal points of a random variable Xwith finite second moment are those ppoints in R minimizing the expected squared distance from Xto the closest point. Although the determination of principal points involves in general the resolution of a multiextremal optimization problem, existing procedures in the literature provide just a local optimum. In this paper we show that standard Global Optimization techniques can be applied. Keywords: Principal points, d.c. functions, branch and bound. 1. Introduction Given a random variable Xwith finite second moment, consider the function Φ:Rp−→ R, Φ(c1,... ,c p)=Emin 1≤i≤p(X−ci)2. Received December, 1999. Accepted April, 2001. ∗The research of the two first authors has been supported by Grant PB96-1416-C02-02 of DGES, Spain. 1Facultad de Matem´aticas, Universidad de Sevilla, C/ Tarfia s/n, 41012 Sevilla, Spain. 2Departamento de Matem´aticas, E.U. Empresariales, Universidad de C´adiz, C/ Por Vera, N. 54, Jerez de la Frontera, C´adiz, Spain. 3Faculty of Economics and Business Administration, Maastricht University, P.O. Box 616, 6200 MD Maastricht, The Netherlands. c EDP Sciences 2002 316 E. CARRIZOSA ET AL. Ap-uple c∗=(c∗ 1,c ∗ 2,... ,c ∗ p) such that Φ(c∗ 1,... ,c ∗ p)≤Φ(c1,... ,c p)∀(c1,... ,c p)∈Rp(1) is said to be a set of p-principal points of X[3,4,9,11,12,14–17]. Observe that, for p= 1, Φ becomes the classical expected squared distance, thus the unique 1-principal point is the mean of X. This shows that the concept of p-principal point constitutes a generalization to ppoints of the mean, thus representing a natural way to partition a population into pclusters (according to the attraction regions), see [10]. The literature addressing computational aspects of the problem of determination of principal points is rather scarce, and mainly limited to the statement of sufficient conditions under which the nonlinear equation ∇Φ(c) = 0 has as unique solution the principal points of X[10,13,17]. This requires assumptions as strong as existence and symmetry of the density function of X, conditions which are unlikely to hold just when the use of principal points is most natural, namely, when Xis a mixture of ppopulations [10]. However, as shown in this paper no assumptions on Xother than the existence of its second moment are required in order to solve the problem by standard global optimization procedures. The rest of the paper is structured as follows. In Section 2 we state some general properties on the function Φ. In Section 3 we show how to construct a bounded polyhedron in Rpwhich is known to contain an ε-optimal solution. This polyhedron can be used as starting region for a Branch and Bound procedure. Some conclusions are given in Section 4 to end the paper. 2. General properties Finding p-principal points amounts to finding an optimal solution to the optimization problem (PP), inf c∈RpΦ(c).(PP) In this section we address the important, though non-trivial question of existence of principal points, i.e., the attainment of the infimum of (PP). Since the usual sufficient conditions for existence of optimal solutions, namely the compactness of the level sets {c∈Rp:Φ(c)≤α}, do not hold, an ad-hoc analysis is needed. To do that we start showing that Φ can easily be expressed as a d.c. function (difference of convex functions). Property 2.1. Let f:Rp−→ Rbe the convex quadratic function defined as follows f(c1,... ,c p)= p X i=1 c2 i.(2) FINDING PRINCIPAL POINTS 317 Then f−Φis a convex function and Φ=f−(f−Φ) defines a d.c. decomposition of Φ. Proof. Since p X i=1 (x−ci)2−min 1≤i≤p(x−ci)2=max 1≤i≤pX j6=i (x−cj)2, it follows that f(c1,... ,c p)−Φ(c1,... ,c p)=Zmax 1≤i≤pX j6=i (x−cj)2dF(x) which is a convex function. Thus, the results holds by observing that fis a convex function. For any α, β ∈R∪{±∞},α≤β,letS[α,β]denote the polyhedron S[α,β]={(c1,... ,c p)∈Rp:α≤c1≤c2≤...≤cp≤β}· Observe that S[α,β]is bounded iff α>−∞ and β<+∞. Moreover, when −∞ <α<β<+∞,S[α,β]is a simplex which, rewritten in terms of its extreme points, leads to the expression S[α,β]=(p X i=0 λivi:λi≥0∀i, p X i=0 λi=1 ),(3) where v0=(α,α,... ,α,α) v1=(α,α,... ,α,β) . . .. . .. . . vp=(β,β,... ,β,β). Due to the symmetry of Φ in its arguments, it follows: Proposition 2.1. One has: inf c∈RpΦ(c)= inf c∈S[−∞,+∞] Φ(c). This result can be strengthened when Xhas compact support. Indeed, one has: Proposition 2.2. If Xhas compact support [m, M],thenS[m,M]contains a set of p-principal points. 318 E. CARRIZOSA ET AL. Proof. For any c=(c1,c 2,... ,c p)∈S[−∞,+∞], define c∗=(c∗ 1,... ,c ∗ p)∈S[m,M] as c∗ i=   m, if ci<m M, if ci>M ci,else. By construction one has (ci−x)2≥(c∗ i−x)2∀x∈[m, M],∀i=1,2,...,p thus min 1≤i≤p(ci−x)2≥min 1≤i≤p(c∗ i−x)2∀x∈[m, M]. Since Xhas zero mass outside [m, M], one has Φ(c)=Z[m,M] min 1≤i≤p(ci−x)2dF(x)≥Z[m,M] min 1≤i≤p(c∗ i−x)2dF(x)=Φ(c∗). This shows that inf c∈S[−∞,+∞] Φ(c)= inf c∈S[m,M] Φ(c).(4) But S[m,M]is compact, and, by Property 2.1, Φ continuous on compact sets, thus there exists some ¯c∈S[m,M]such that Φ(¯c)≤Φ(c)∀c∈S[m,M], then, by Proposition 2.1 and (4), Φ(¯c)≤Φ(c)∀c∈Rp. The following example illustrates a simple case of compact support of Xand shows how local search methods might yield suboptimal solutions. Example 2.1. Let Xbe the discrete random variable with support at points xi and probability mass pi,i=1,2,... ,9, given in Table 1. Figure 1 depicts a detail of the level sets and graph of the corresponding Φfor two principal points, clearly showing the multiextremal character of Φ. Following Proposition 2.2 the set S[0,20] contains a set of principal points and consequently, could be used as starting region of a global optimization method. Instead of this, we build a direct AMPL code [5] for solving (PP), taking as starting point in the local-search procedure a random pair in (0,20) ×(0,20), as described in the Appendix (Tab. 2). FINDING PRINCIPAL POINTS 319 Table 1. Xwith mass at 9 points. i123456789 xi02381015161820 pi 1 15 1 15 1 15 4 15 4 15 1 15 1 15 1 15 1 15 Figure 1. Level curves and graph of Φ. The solution proposed by AMPL as optimal is (9.733,9.733) (which is not even a local minimum!) with Φ(9.733,9.733) = 30.196. However, it is easily checked that the 2-principal points for this problem are (7,17.25), with Φ(7,17.25) = 9.65. A Branch and Bound algorithm was implemented using a bisection subdivision [7, 8], and replacing (2), the convex component of the objective function, by its linear minorant, as bounding scheme, [8]. It required 280 iterations to detect that an ε-optimal solution (ε=0.0001) had been found: (6.99707,17.25098), with Φ(6.99707,17.25098) = 9.650006552. 3. Existence and localization of ε-optimal solutions It has been shown in Section 2 that (PP) admits an optimal solution for random variables with bounded support. This result can be extended for unbounded supports. First, a technical lemma is given. Lemma 3.1. One has: lim N→+∞Z(−N,N) min{(x+N)2,(x−N)2}dF(x)=+∞.(5) 320 E. CARRIZOSA ET AL. Proof. Z(−N,N) min{(x+N)2,(x−N)2}dF(x)≥Z(−N 2,N 2) min{(x+N)2,(x−N)2}dF(x) ≥Z(−N 2,N 2) (N/2)2dF(x) =N2/4P[X∈(−N/2,N/2)], thus lim N→+∞Z(−N,N) min{(x+N)2,(x−N)2}dF(x) ≥lim N→+∞N2/4P[X∈(−N/2,N/2)] = +∞. Proposition 3.1. There exists a set of p-principal points. Proof. If Xhas bounded support, the result follows from Proposition 2.2, so that we assume that Xhas unbounded support. Since Φ is bounded below ∃inf c∈S[−∞,+∞] Φ(c)=I∈[0,+∞).(6) To show that an optimal solution exists, suppose that, on the contrary, such infimum is never attained. Hence, I<Φ(c)∀c∈S[−∞,+∞].(7) Hence, by (6) and (7), there exists some unbounded sequence {cn}n⊂S[−∞,+∞] such that Φ(cn) converges to I.Letcn 0=−∞ and cn p+1 =+∞. By construction of S[−∞,+∞], there exist i0,i 1, with 0 ≤i0<i 1≤p+1such that cn i7−→ −∞ ∀i≤i0 cn i7−→ +∞∀i≥i1 {cn i}nis bounded ∀i, i0+1≤i≤i1−1. Moreover, since for each i∈{i0+1,... ,i 1−1}the sequence {cn i}nis bounded, it has some convergent subsequence. Without loss of generality we assume that each {cn i}n(i=i0+1,... ,i 1−1) is convergent. Two cases may then happen, 1. {cn}nhas at least one component bounded, i.e., i0<i 1−1; (8) FINDING PRINCIPAL POINTS 321 2. all the components of {cn}ndiverge, i.e., i0=i1−1.(9) We consider separately the two cases above. Suppose first that (8) holds. Then, for any none has Φ(cn)≥ p X j=1 Z(cn j−1+cn j 2,cn j+cn j+1 2] (x−cn j)2dF(x) ≥ i1−1 X j=i0+1 Z(cn j−1+cn j 2,cn j+cn j+1 2] (x−cn j)2dF(x). Denote by c∗∈Rpthe vector with components c∗ i=   limn→+∞cn i0+1,if i≤i0+1 limn→+∞cn i1−1,if i≥i1−1 limn→+∞cn i,else. It then follows that I= lim n→+∞Φ(cn)≥lim n→+∞ i1−1 X j=i0+1 Z(cn j−1+cn j 2,cn j+cn j+1 2] (x−cn j)2dF(x) ≥Φ(c∗), which contradicts (7). Hence, the result holds. Suppose now that (9) holds, thus any component of {cn}ndiverges. Hence, by (5), for any M>0, there exists N>0 such that Z(−N,N) min{(x+N)2,(x−N)2}dF(x)>M. Moreover, given N>0, there exists n0∈Nsuch that, for any n≥n0, cn i<−N∀i≤i0 cn i>N ∀i≥i0+1. Hence, Φ(cn)≥Z(−N,N) min 1≤i≤p(x−cn i)2dF(x) ≥Z(−N,N) min{(x+N)2,(x−N)2}dF(x)>M, 322 E. CARRIZOSA ET AL. thus I= lim n→+∞Φ(cn)=+∞, which contradicts (6). Hence, the result holds. For the case in which Xhas zero mass outside an interval [m, M], we have shown in Proposition 2.2 that the search of an optimal solution can be reduced to the bounded polyhedron S[m,M]. Now we address the general case and show how to explicitly construct a bounded polyhedron in Rpof the form S[L,U]that contains an ε-optimal solution cεto (PP). The following result is easily shown: Lemma 3.2. One has: •the function R7−→ R[R,+∞)(x−R)2dF(x)is nonincreasing, and lim R→+∞Z[R,+∞) (x−R)2dF(x) = 0; (10) •the function R7−→ R(−∞,R](x−R)2dF(x)is nondecreasing, and lim R→−∞ Z(−∞,R] (x−R)2dF(x)=0.(11) Lemma 3.2 implies that, for any ε1,ε 2>0 one can construct real constants L≤U such that Z(−∞,L] (x−L)2dF(x)≤ε1(12) Z[U,+∞) (x−U)2dF(x)≤ε2.(13) Proposition 3.2. Given L≤Uverifying (12)-(13), there exists ¯c∈S[L,U]which is an (ε1+ε2)-optimal solution of (PP). Proof. One just needs to show that, for any c∈S[−∞,+∞], there exists ¯c∈S[L,U] such that Φ(¯c)≤Φ(c)+ε1+ε2. To show this, we first show that for any c∈S[−∞,+∞]there exists ˆc∈S[−∞,U], such that Φ(ˆc)≤Φ(c)+ε1.(14) FINDING PRINCIPAL POINTS 323 Let c=(c1,c 2,... ,c p)∈S[−∞,+∞].Ifcp≤U, we are done (take ˆc=c), thus we can assume that cp>U.Letc0=−∞,cp+1 =+∞and let i∗be given by i∗=max{i:ci≤U}, which, by assumption, verifies i∗<p. Let ˆc∈S[−∞,U]be given by ˆci=min{ci,U}=ci,if i≤i∗ U, else. Then, Φ(ˆc)≤ p X i=1 Z(ci−1+ci 2,ci+ci+1 2] (x−ˆci)2dF(x) = i∗ X i=1 Z(ci−1+ci 2,ci+ci+1 2] (x−ci)2dF(x) + p X i=i∗+1 Z(ci−1+ci 2,ci+ci+1 2] (x−U)2dF(x) =Φ(c)− p X i=i∗+1 Z(ci−1+ci 2,ci+ci+1 2] (x−ci)2dF(x) +Z(ci∗+ci∗+1 2,+∞) (x−U)2dF(x). Then, either ci∗+ci∗+1 2>U (15) or ci∗+ci∗+1 2≤U. (16) If (15) holds, then by (13), Φ(ˆc)≤Φ(c)+Z(ci∗+ci∗+1 2,+∞) (x−U)2dF(x)≤Φ(c)+ε1, and (14) holds.