Gauge Distances and Median Hyperplanes

JOURNAL OF OPTIMIZATION THEORY AND APPLICATIONS: Vol. 110, No. 1, pp. 173–182, JULY 2001 Gauge Distances and Median Hyperplanes 1,2 F. P LASTRIA 3 AND E. C ARRIZOSA 4 Communicated by J. P. Crouzeix Abstract. A median hyperplane in d-dimensional space minimizes the weighted sum of the distances from a finite set of points to it. When the distances from these points are measured by possibly different gauges, we prove the existence of a median hyperplane passing through at least one of the points. When all the gauges are equal, some median hyperplane will pass through at least dA1 points, this number being increased to dwhen the gauge is symmetric, i.e. the gauge is a norm. Whereas some of these results have been obtained previously by different methods, we show that they all derive from a simple formula for the distance of a point to a hyperplane as measured by an arbitrary gauge. Key Words. Gauges, distance to a hyperplane, hyperplane fitting. 1. Gauge Distance to a Hyperplane Let γ be a gauge on ⺢ d with unit ball B; i.e., Bis a compact convex set containing the origin in its interior such that γ (x)Gmin{t¤0兩x∈tB}; see e.g. Refs. 1–2. Given a hyperplane Hin ⺢ d , the γ -distance of a point a∈⺢ d to His defined as d γ (a,H)G def min{ γ (xAa)兩x∈H}. 1 The research of the second author was partially supported by a DGES Grant, Madrid, Spain. 2 The authors thank two anonymous referees for many suggestions which helped streamline this paper. 3 Professor, Department of Management Informatics, Vrije Universiteit, Brussels, Belgium. 4 Professor, Facultad de Matema ´ticas, Universidad de Sevilla, Sevilla, Spain. 173 0022-3239兾01兾0700-0173$19.50兾02001 Plenum Publishing Corporation JOTA: VOL. 110, NO. 1, JULY 2001174 Let γ °be the dual (or polar) gauge of γ , given by γ °(û)G def max{〈û;y〉兩 γ (y)⁄1}, which is well-defined and also a gauge on (the dual space of) ⺢ d ; see e.g. Ref. 3. This definition implies directly the following well-known generalized Cauchy–Schwartz inequality (see e.g. Ref. 3, p. 129): 〈û;y〉⁄ γ °(û) γ (y), ∀û,y∈⺢ d , (1) in which for any fixed û≠0 equality holds iff yG λ z, for some λ ¤0 and some z∈∂ γ °(û), where ∂ γ °(û) denotes the (nonempty) subdifferential of the dual gauge at û; see e.g. Ref. 2. Note that equality in (1) for û,y≠0 also implies 〈û;y〉H0. We will denote the hyperplane of equation 〈u;x〉G β ,u≠0, by H(u, β ), and the set of all hyperplanes in ⺢ d by H. The following theorem gives a simple expression for the gauge distance to a hyperplane. The use of (1) enables us to simplify the proof given in Ref. 4 for a similar problem. Theorem 1.1. For any gauge γ and any hyperplane H(u, β ), we have d γ (a,H(u, β ))G 冦 [ β A〈u;a〉]兾 γ °(u), when 〈u;a〉⁄ β , [〈u;a〉A β ]兾 γ °(−u), when 〈u;a〉H β . Any γ -closest point of H(u, β )toais found as the unique intersection point of H(u, β ) with the line through ahaving as direction any subgradient of γ ° at uwhen 〈u;a〉⁄ β , and at Auwhen 〈u;a〉H β . Proof. Let u≠0, and assume first that 〈u;a〉⁄ β . For any x∈H(u, β ), after substituting ûby u(≠0) and yby xAain the generalized Cauchy–Schwartz inequality (1), we have that γ (xAa)¤〈u;xAa〉兾 γ °(u)G[ β A〈u;a〉]兾 γ °(u), where equality happens at x∈H(u, β ) iff xAais of the form λ z, for some z∈∂ γ °(u). (2) Moreover, such an xexists. Indeed, since u≠0, for any given z∈∂ γ °(u)we have γ °(z)G1, JOTA: VOL. 110, NO. 1, JULY 2001 175 so that by (1) 〈u;z〉G γ (z) γ °(u)G γ °(u)H0; thus, the function λ ¤0>〈u;aC λ z〉A β G〈u;a〉A β C λ 〈u;z〉 has a unique root in [0, CS[. In other words, there exist some λ ¤0 and x∈H(u, β ) satisfying (2). The same reasoning can be used for the case 〈u;a〉H β and will not be repeated here. 䊐 When γ is symmetric [ γ (−x)G γ (x), for all x∈⺢ d ], i.e. γ is a norm, then its dual enjoys the same property, and the following simplified formula arises directly (compare with Ref. 5, which uses a proof based on the Kuhn– Tucker conditions). Corollary 1.1. For any norm ν , we have d ν (a,H(u, β ))G兩 β A〈u;a〉兩兾 ν °(u). Note also that, for the particular case of the l p -distances, 1⁄p⁄CS, this also proves directly the formula (painstakingly derived by Ref. 6) d l p (a,H(u, β ))G兩 β A〈u;a〉兩兾l q (u), 1兾pC1兾qG1, by the well-known duality l° p Gl q , with 1兾pC1兾qG1, including their limits pG1, qG+Sor pG+S,qG1. The proof above also shows that in fact this is a direct consequence of the Ho ¨lder inequality 〈û;y〉⁄l q (û)l p (y). 2. Median Hyperplanes Given a finite set A⊂⺢ d , together with corresponding positive weights w a (a∈A) and gauges γ a on ⺢ d , any hyperplane H* minimizing the weighted sum of the gauge distances from Ais called a median hyperplane; i.e., H*∈arg min{ f(H)兩H∈H}, JOTA: VOL. 110, NO. 1, JULY 2001176 where f(H)G ∑ a∈A w a d γ a (a,H). Since for any λ ≠0, we have H( λ u, λβ )GH(u, β ), the function H: ⺢ d \{0}B⺢ → H:(u, β )>H(u, β ) is surjective, with the property that, for each one-dimensional linear space Xin ⺢ d B⺢,X≠{0}B⺢, the set H(X\{0}) is reduced to a singleton; i.e., all the nonzero points in Xare mapped to the same hyperplane. It is a well-established fact from topology that no continuous bijective mapping may exist between a subset of ⺢ d B⺢and the projective space H. Several continuous and bijective restrictions of H may however be considered. For example, consider the restriction of H on the cylinder in ⺢ d B⺢ with base some unit sphere of ⺢ d (i.e., S dA1 B]0; +S[), where S dA1 G def {u∈⺢ d 兩兩兩u兩兩G1}, and where 兩兩·兩兩 denotes the standard Euclidean norm (or any other norm). This is an injection, the image of which contains all Hexcept the hyperplanes through the origin, i.e. of type H(u, 0). Note that allowing also β G 0 leads to loss of injectivity, since H(u,0)GH(−u, 0). Restriction of H to some nonvertical hyperplane in ⺢ d B⺢(which we will rather call a superplane, to distinguish it from hyperplanes in ⺢ d ) not passing through the origin, and excepting its single point on the β -axis, yields another continuous injection to H: consider the superplane S(c, λ , µ ), µ ≠0, λ ≠0, with equation 〈c;u〉C λβ G µ , from which the point (0, µ 兾 λ ) is deleted; then, the only hyperplanes not represented will be those of form H(û, µ 兾 λ ), where û≠0 is any vector orthogonal to c. The set of all hyperplanes in ⺢ d normal to some fixed u≠0 is denoted by H u G{H(u, β )兩 β ∈⺢}. JOTA: VOL. 110, NO. 1, JULY 2001 177 Lemma 2.1. For any fixed u∈⺢ d \{0}, there exists a hyperplane H* u minimizing fon H u which passes through some point a∈A. Proof. For fixed u≠0, Theorem 1.1 shows that, for any a∈A, the distance γ a (a,H(u, β )) is a convex piecewise linear function of β : it consists of two unbounded pieces with breakpoint β a u G〈u;a〉, linearly decreasing with slope A1兾 γ °(−u)on]−S; β a u ] and linearly increasing with slope 1兾 γ °(u) on [ β a u ;CS[. Note also that it is coercive, i.e. asymptotically equal to +S in any direction. It follows that, as the positively weighted sum over all a∈Aof such distance functions, f(H(u, β )) is convex, coercive, and piecewise linear, with breakpoints β a u ,a∈A, and therefore reaches its minimum at least at one of these breakpoints, say β a 0 u with a 0 ∈A. But 〈u;a 0 〉G β a 0 u means that the corresponding minimizing hyperplane, H* u GH(u, β a 0 u ), passes through a 0 .䊐 Let us introduce the notations A # (u, β ) for any #∈{F,⁄,H,¤}by A # (u, β )G{a∈A兩〈u;a〉 #β }. In fact, the problem of minimizing fon H u may be seen as a onedimensional asymmetric distance Weber problem (Ref. 7), min β ∈⺢ ∑ a∈A H (u, β ) [w a 兾 γ ° a (−u)]兩〈u;a〉A β 兩C ∑ a∈A F (u, β ) [w a 兾 γ ° a (u)]兩〈u;a〉A β 兩, (3) for which a fixed-point optimality property was derived. This interpretation of the problem also enables us to state an important property of median hyperplanes. Definition 2.1. The hyperplane H(u, β ) halves Aif ∑ a∈A ¤ (u, β ) w a 兾 γ ° a (−u)¤ ∑ a∈A F (u, β ) w a 兾 γ ° a (u), (4) ∑ a∈A H (u, β ) w a 兾 γ ° a (−u)⁄ ∑ a∈A ⁄ (u, β ) w a 兾 γ ° a (u). (5) The following result generalizes analogous results in Ref. 8, and the first part proves a conjecture made there on p. 182. JOTA: VOL. 110, NO. 1, JULY 2001178 Theorem 2.1. There exists a median hyperplane which passes through some point a∈A. Moreover, any median hyperplane halves A. Proof. Lemma 2.1 shows that, for every fixed u≠0, the minimum of f(H) is reached on H u at some hyperplane H(u, β ) with β ∈[ β l u , β h u ], where β l u Gmin{ β a u 兩a∈A}, β h u Gmax{ β a u 兩a∈A}. The values β l u and β h u are clearly continuous in u, so they reach their extreme values β l Gmin{ β l u 兩u∈S dA1 }, β h Gmax{ β h u 兩u∈S dA1 } on the (compact) unit sphere S dA1 . It follows that finding the minimum of fon His equivalent to finding the minimum of f(H(u, β )) on S dA1 B[ β l , β h ], which is compact. Since fis continuous, this minimum will be reached, establishing the existence of a median hyperplane. Then, the existence of a median hyperplane which meets Afollows immediately from Lemma 2.1. Finally, if H(u 0 , β 0 )defines a median hyperplane, then β 0 must solve (3) for uGu 0 . The left and right directional derivatives of this convex function of β are respectively ∑ a∈A F (u 0 , β 0 ) w a 兾 γ ° a (u 0 )A ∑ a∈A ¤ (u 0 , β 0 ) w a 兾 γ ° a (−u 0 ), ∑ a∈A ⁄ (u 0 , β 0 ) w a 兾 γ ° a (u 0 )A ∑ a∈A H (u 0 , β 0 ) w a 兾 γ ° a (−u 0 ). A necessary and sufficient condition for a minimum is that the first should be nonpositive and the second nonnegative; in other words, (u 0 , β 0 ) should satisfy (4)–(5). 䊐 Observe that, when there exists a hyperplane in ⺢ d containing A, then this is clearly a median hyperplane with objective value 0. Therefore, we further assume that this is not the case; i.e. dim(A)Gd, meaning that Acontains at least dC1affinely independent points. When all gauges are symmetric and equal (i.e., when all distances are measured by a same norm), we may then derive a much stronger result which was obtained already by other means in Refs. 8–9. In the sequel, we will write f′for f°H, i.e., f′(u, β )G def f(H(u, β )), JOTA: VOL. 110, NO. 1, JULY 2001 179 and consider the median hyperplane determination as the problem of minimizing f′on ⺢ d B⺢. Theorem 2.2. For distances measured by a fixed norm, i.e. γ a G ν , a∈A, with ν (−x)G ν (x) for all x∈⺢ d , when dim(A)Gd, some median hyperplane passes through daffinely independent points of A. Proof. Let H(u 0 , β 0 ) be a median hyperplane, the existence of which follows from Theorem 2.1. Without loss of generality, we may assume that ν °(u 0 )G1. Define T⊂⺢ d B⺢by (u, β )∈Tiff 冦 〈u;a〉¤ β ,∀a∈A ¤ (u 0 , β 0 ), 〈u;a〉⁄ β ,∀a∈A F (u 0 , β 0 ), and the following linear function: g:⺢ d B⺢ → ⺢ :(u, β )> ∑ a∈A ¤ (u 0 , β 0 ) w a (〈u;a〉A β )C ∑ a∈A F (u 0 , β 0 ) w a ( β A〈u;a〉). Consider the set Pin ⺢ d B⺢defined as PG{(u, β )∈T兩g(u, β )Gg(u 0 , β 0 )}. Pis a closed polyhedral set in ⺢ d B⺢:itisdefined by linear inequalities and one linear equality in dC1 variables. Pis also bounded. Indeed, if unbounded, there would exist some (u, β )≠(0, 0) such that ( λ uCu 0 , λβ C β 0 )∈P, for all λ ¤0. This means that we would have 〈u;a〉A β ¤0, ∀a∈A ¤ (u 0 , β 0 ), 〈u;a〉A β ⁄0, ∀a∈A F (u 0 , β 0 ), g(u, β )G0, which by the definition of gimplies that 〈u;a〉A β G0, for all a∈A; in other words, A⊂H(u, β ), which contradicts the assumption dim(A)Gd. Therefore, Pis a polytope of (at most) dimension d. It contains the optimal solution (u 0 , β 0 ), so any solution optimizing f′on Pis also a global optimal JOTA: VOL. 110, NO. 1, JULY 2001180 solution. Moreover, f′(u, β )Gg(u, β )兾 ν °(u)Gg(u 0 , β 0 )兾 ν °(u), ∀(u, β )∈P. Hence, minimizing f′on Pturns out to be equivalent to maximizing the function (u, β )> ν °(u)onP. Since this function is convex, it attains its maximum on the polytope Pat some extreme point (u 1 , β 1 ). Since (u 1 , β 1 )is obtained as the point common to dhyperplanes bounding linearly independent halfspaces defining P, it corresponds to the hyperplane H(u 1 , β 1 ) passing through daffinely independent points of A.䊐 That the previous theorem does not hold for an asymmetric gauge is shown by the counterexample in Ref. 8. However, we may show the following only slightly weaker result. Theorem 2.3. For distances measured by a fixed gauge (i.e. γ a G γ ,a∈ A), when dim(A)Gd, some median hyperplane passes through dA1affinely independent points of A. Proof. Let H(u 0 , β 0 ) be a median hyperplane, and define the functions f 0 and gon ⺢ d B⺢, f 0 (u, β )G1 γ °(u) 冤 ∑ a∈A ¤ (u 0 , β 0 ) w a (〈u;a〉A β ) 冥 C1 γ °(−u) 冤 ∑ a∈A F (u 0 , β 0 ) w a ( β A〈u;a〉) 冥 G def f ¤ (u, β )Cf F (u, β ), g(u, β )G1 γ °(u 0 ) 冤 ∑ a∈A ¤ (u 0 , β 0 ) w a (〈u;a〉A β ) 冥 C1 γ °(−u 0 ) 冤 ∑ a∈A F (u 0 , β 0 ) w a ( β A〈u;a〉) 冥 . Observe that gis linear, f 0 is nonlinear, while g(u 0 , β 0 )Gf 0 (u 0 , β 0 )Gf′(u 0 , β 0 ). Let the subset P⊂⺢ d B⺢be defined by the constraints 〈u;a〉¤ β ,∀a∈A ¤ (u 0 , β 0 ), 〈u;a〉⁄ β ,∀a∈A F (u 0 , β 0 ), g(u, β )Gf′(u 0 , β 0 ). JOTA: VOL. 110, NO. 1, JULY 2001 181 It is easy to see by similar arguments as those used in Theorem 2.2 that P is a polytope of (at most) dimension d. Since for all (u, β )∈P, we have A # (u, β )GA # (u 0 , β 0 ), # ∈{¤,F}, it follows that on Pwe have f 0 Gf′. But Pcontains the optimal solution (u 0 , β 0 )off′on ⺢ d B⺢, so any minimum of f 0 on Pwill also be a global optimum of f′and yield a median hyperplane. Since f 0 Gf ¤ Cf F , any solution minimizing f 0 on Pis an efficient solution to the biobjective problem of minimizing both f ¤ and f F on P. Each of the functions f ¤ and f F is quasiconcave on P(see e.g. Ref. 10), since their upper level sets at level α are given respectively by inequalities of the form αγ °(u)A ∑ a∈A ¤ (u 0 , β 0 ) w a (〈u;a〉A β )⁄0, αγ °(−u)A ∑ a∈A F (u 0 , β 0 ) w a ( β A〈u;a〉)⁄0, which, by the convexity of γ °,define convex sets in ⺢ d B⺢. It was shown in Ref. 11 that, in this case, the set of edges (one-dimensional faces) of Pconstitutes a dominator of P; i.e., for any (u, β )∈P, there exists some (u′, β ′) on some edge of Pwith f ¤ (u′, β ′)⁄f ¤ (u, β ), f F (u′, β ′)⁄f F (u, β ), and hence f 0 (u′, β ′)⁄f 0 (u, β ). And any edge of Pis the intersection of dA1 hyperplanes bounding linearly independent halfspaces defining P. Therefore, there exists some minimum of f 0 on P(and hence a global minimum of f′) satisfying as equality dA1 linearly independent inequalities among those defining P. But this corresponds to a hyperplane Hpassing through dA1affinely independent points of A.䊐 References 1. D URIER , R., and M ICHELOT ,C.,Geometrical Properties of the Fermat–Weber Problem, European Journal of Operational Research, Vol. 20, pp. 332–343, 1985.