# Some Remarks on Convex Network Flows forK-Spiders

Authors: Maria Mălin; Ionel Rovenţa
Journal: Mathematical Problems in Engineering
 (2015)

---

## Abstract

We consider convex functions modeling flows in an arborescent network. The notion of majorization on trees is used to study some classical convexity results in this framework.


---

## Body

## 1. Introduction

In the last years, the majorization theory has been used in different research areas, as engineering, Lorenz or dominance ordering in economics, optimization, networks, and graph theory.The results of this paper can be used in the framework of modeling some practical engineering problems. More precisely, since the convex cost functions defined on trees can model the network flows from communication networks, the distribution of goods with the corresponding costs, or transport between different factories, it is interesting to study which classical inequalities hold true in this framework.In the following sentences we present a brief introduction in graph theory and we discuss a special concept of majorization introduced in Dahl [1].LetT=(V,E) be a tree, where V is the set of vertices of the tree and E is the set of edges of the tree.Letd(u,v) be the distance between two vertices u and v in a tree T, which is defined as the number of edges in the unique path from u to v. For u∈V we define the distance vector of u as d(u,·)=(d(u,v):v∈V)∈Z+N.Let us denote byx[i] the ith largest component of the vector x∈RN.Definition 1.
Ifx,y∈RN one says that x is weakly majorized by y and denoted by x≺∗y, provided that(1)∑i=1kxi≤∑i=1kyi,k=1,…,N.
Moreover, if∑i=1N‍x[i]=∑i=1N‍y[i] holds, then we say that xis majorized byy and is denoted by x≺y.Definition 2 (see [1]).
Letu,v be two vertices in a tree T. One says that u isweakly majorized by v and denoted by u≺∗v, if d(u,·)≺∗d(v,·). One says that u and v are majorization equivalent if u≺∗v and v≺∗u.In general, there exist at most two adjacent majorization equivalent vertices, and in this case we say thatT is m-symmetric. Consider two adjacent vertices u and v in T. If we remove the edge [u,v] we obtain two subtrees T(u;v) and T(v;u), where u∈T(u;v) and v∈T(v;u). Also denote by V(u,v) the set of vertices of T(u,v).In [1] it was proved that if u≺∗v then we have u≺∗v≺∗v′, for all v′∈V(v,u).Definition 3.
The majorization center is a vertex set, denoted byMT, and defined as follows.(i)
IfT is m-symmetric, then MT={u,v}, where u and v are the two adjacent majorization equivalent vertices.(ii)
IfT is not m-symmetric, then MT is the intersection of all vertex sets V(u;v) taken over all adjacent vertices u and v for which the majorization u≺∗v holds.More details about graph theory and special vertices in a tree can be found in [2, 3]. Based on the above approach, a special case of a strong concept of majorization is treated in [4]. In this paper we consider other concepts of majorization on trees, deriving from the possibility to extend the classical majorization to a general class of metric spaces, namely, global nonpositive curvature spaces. Such spaces contain some particular class of trees, the K-spiders, when are endowed with a special metric.Majorization theory is intimately related with matrix theory, more exactly with doubly stochastic matrices; that is, nonnegative matrices with all rows and columns sums are equal to one. A complex theoretical approach and interesting applications about majorization theory can be found in Marshall et al. [5]. We mentioned here an important theorem in majorization theory from [5].Theorem 4.
Letx,y∈RN. The following statements are equivalent.(i)
Considerx≺y.(ii)
There is a doubly stochastic matrixA=(aij)1≤i,j≤n such that x=Ay.(iii)
The inequality∑i=1N‍f(xi)≤∑i=1N‍f(yi) holds for each convex function f:R→R.Statement (iii) is precisely Hardy-Littlewood-Polya’s inequality. A slide generalization of (iii) is presented in Tomić [6] and Weyl [7].Remark 5.
Note thatx≺y means that (2)xi=arg⁡min⁡y∈R⁡∑j=1Naijy-yj2,i=1,…,N.Theorem 6.
The weak majorizationx≺∗y holds if and only if for every nondecreasing convex function f:R→R one has (3)∑i=1Nfxi≤∑i=1Nfyi.Our aim is to study some properties of a convex function defined on aK-spider, which is a tree endowed with a special metric verifying (4). More precisely, we study some minimization properties of a convex function defined on a K-spider. The main ingredient of our paper is given by the majorization concept, which was extended in the context of spaces with global nonpositive curvature (see [8, 9]). The study of majorization in the context of Popoviciu’s inequality on a K-spider is also considered.The outline of the paper is the following: Section2 is devoted to some preliminaries on metric spaces of global nonpositive curvature. In Section 3 we study a characterization of convex functions defined on a K-spider and Popoviciu’s inequality. In Section 4 we are dealing with the localization of minimum and maximum of a convex function defined on a K-spider.


## 2. Convexity, Barycenters, and Majorization on Global NPC Spaces

A formal definition of the spaces with global nonpositive curvature (abbreviated, global NPC spaces) is as follows.Definition 7.
A global NPC space is a complete metric spaceE=(E,d) for which the following inequality holds true: for each pair of points x0,x1∈E there exists a point y∈E such that, for all points z∈E,(4)d2z,y≤12d2z,x0+12d2z,x1-14d2x0,x1.These spaces are also known as the Cat 0 spaces. See [10]. In a global NPC space, each pair of points x0, x1∈E can be connected by a geodesic (i.e., by a rectifiable curve γ:[0,1]→E such that the length of γ|[s,t] is d(γ(s),γ(t)) for all 0≤s≤t≤1). Moreover, this geodesic is unique. The point y that appears in Definition 7 is themidpoint of x0 and x1 and has the property(5)dx0,y=dy,x1=12dx0,x1.Every Hilbert space is a global NPC space. Its geodesics are the line segments. The upper half-planeH=z∈C:Im⁡z>0, endowed with the Poincaré metric, constitutes another example of a global NPC space. In this case the geodesics are the semicircles in H perpendicular to the real axis and the straight vertical lines ending on the real axis.A Riemannian manifold(M,g) is a global NPC space if and only if it is complete and simply connected and of nonpositive sectional curvature. Besides manifolds, other important examples of global NPC spaces are the Bruhat-Tits buildings (in particular, the trees). See [10]. More pieces of information on global NPC spaces are available in [9, 11–13]. We recall the basic convexity notions in a global NPC space.Definition 8.
A setC⊂E is calledconvex if γ([0,1])⊂C for each geodesic γ:[0,1]→C joining γ(0),γ(1)∈C.
A functionφ:C→R is called convex if the function φ∘γ:[0,1]→R is convex for each geodesic γ:[0,1]→C, γ(t)=γt, that is,(6)φγt≤1-tφγ0+tφγ1for all t∈[0,1]. The function φ is called concave if -φ is convex.Note that the functionsd2(z,·) are convex (more precisely, uniformly convex). Moreover, one can prove that the distance function d is convex in each of its variables (and also with respect to both variables), a fact which implies that every ball in a global NPC space is a convex set.We denote byP1(E) the set of all Borel probability measures μ on E with separable support, which verify the condition ∫E‍d(x,y)dμ(y)<∞ for all x∈E. The set P2(E) is given by the family of all square integrable probability measures with separable support; that is, ∫E‍d2(x,y)dμ(y)<∞.The barycenter of a measureμ∈P1(E) is the unique point z∈E which minimizes the uniformly convex function (7)Fyx=∫Ed2z,x-dy,xdμx.This minimizer is independent ofy∈E and it denotes b(μ). In the case of a square integrable measure Sturm [9] shows that the barycenter can be alternatively characterized by(8)bμ=argmin⁡z∈E⁡∫Ed2z,xdμx.Remark 9.
Note that if the support ofμ is included in a convex closed set K, then b(μ)∈K.Definition 10.
Givenx=(x1,…,xn)∈En and some positive real weights λ=(λ1,…,λn) with ∑i=1n‍λi=1, one defines(9)Mnλ,x≔arg⁡min⁡z∈E⁡∑i=1nλid2z,xi.In general the minimizer may fail to exist or is not unique, but the existence and the uniqueness always hold for NPC spaces, since the metric is uniformly convex.Remark 11.
If we considerμ=∑i=1n‍λiδxi then (10)bμ=arg⁡min⁡z∈E⁡∫Ed2z,xdμx=Mnλ,x.In the following we prove that Definition7 is well posed.Proposition 12.
For eachx0,x1∈E the midpoint y∈E given by Definition 7 and the mean point y′=(x1+x2)/2 given by Definition 10 are the same.Proof.
Taking into account the fact that(11)d2y′,x0+d2y′,x1≤d2z,x0+d2z,x1z∈E,we obtain that (12)d2y,y′≤12d2y′,x0+12d2y′,x1-14d2x0,x1≤d2z,x0+d2z,x1-14d2x0,x1z∈E.Now, if we choose z=y, that is, d(z,x0)=d(z,x1)=1/2d(x0,x1), it follows that d2(y,y′)=0, which gives that y=y′.Lawson and Lim [14] show that, for each x=(x1,…,xn), y=(y1,…,yn)∈En and some positive real weight λ=(λ1,…,λn) with ∑i=1n‍λi=1, we have(13)dMnλ,x,Mnλ,y≤∑i=1nλidxi,yi,where μ=∑i=1n‍λiδxi and ν=∑i=1n‍λiδyi are two finitely supported probability measures. In particular, this proves the fact that the least square mean Mn is continuous for each weight λ.We define the following concept of majorization in a global NPC space as in [8].Definition 13.
Letx,y∈En. One says that x≺y if there is a doubly stochastic matrix A=(aij)1≤i,j≤n such that (14)xi=arg⁡min⁡z∈E⁡∑j=1naijd2z,yji=1,…,n.Remark 14.
By using Definition10, it is easy to see that for each x=(x1,…,xn)∈En we have that(15)Mnλ,x,…,Mnλ,x≺x1,…,xn,where λ=1/n,…,1/n.Note that in [8] the following extension of Hardy-Littlewood-Polya inequality on global NPC spaces was proved.Theorem 15.
Letx, y∈En such that x≺y. Then, for each convex function f:E→R, the following inequality holds: (16)∑i=1nfxi≤∑i=1nfyi.Remark 16.
Note that ifx≺y then the barycenters of the measures p=∑i=1n‍1/nδxi and q=∑i=1n‍1/nδyi are not the same in general; that is, (x1+⋯+xn)/n≠(y1+⋯+yn)/n.
Anyway, ifλ=1/n,…,1/n, since for each convex function f:E→R we have that (17)fMnλ,x≤fx1+⋯+fxnn≤fy1+⋯+fynn=∫Efdp,fMnλ,y≤fy1+⋯+fynn=∫Efdp,by applying Proposition 7.3, pp.28, from Sturm [9], we obtain that (18)Mnλ,x=Mnλ,y.


## 3. Popoviciu’s Inequality onK-Spiders

LetK be an arbitrary set and for each i∈K we denote by Ni={(i,r):r∈R} a duplicate of R+ with the usual metric. We define the K-spider (N,d), as the reunion of the spaces Ni,i∈K, in their origins, which means that (19)N=i,r:i∈K,r∈R/~,wherei,0~j,0i,j∈K,(20)di,r,j,s=r-s,ifi=j,r+s,otherwise.The sets Ni can be seen as closed subsets of N. The intersection of each two sets Ni and Nj, with i≠j, is given by the origin o:=(i,0)=(j,0). The K-spider N depends only on the cardinality of K. If the set K={1,2,…,k} the K-spider is called k-spider. The tripod is a 3-spider.Proposition 17 (see [9]).
EachK-spider (N,d) endowed with the metric given by (20) is a global NPC space.In order to present Popoviciu’s inequality onK-spiders we need to characterize the convex functions on the global NPC spaces. We consider a tripod N, with the arms given by N1, N2, and N3, and let f:N→R be a convex function. The restrictions of f to each arm are convex functions, denoted by f1, f2, and f3.The problem consists of finding the conditions which will be imposed to the convex functionsf1, f2, and f3 such that f is a convex function on N. More precisely, let f1, f2, f3:[0,∞)→R be convex functions which satisfy the properties(21)f1d′0+f3d′0≥0,f1d′0+f2d′0≥0,f2d′0+f3d′0≥0.Since the above derivatives of a convex function are finite we suppose without losing the generality thatf1(0)=f2(0)=f3(0)=0. In fact, conditions (21) are equivalent to the fact that the functions f1+f2, f1+f3, f2+f3 are nondecreasing. For more details see [15].Let us considerx1=(1,a)∈N1, a>0, x2=(2,b)∈N2, b>0, and x3=(3,c)∈N3, c>0 belonging to a tripod (3-spider). We consider the measure (22)μ=λ1δx1+λ2δx2+λ3δx3,with λ1+λ2+λ3=1, λi>0, i=1,2,3.In [15] it was proved that if the above conditions are fulfilled then f is a convex function on the tripod (N,d), which means that we have the following inequality: (23)fbμ≤λ1fx1+λ2fx2+λ3fx3,where bμ is the barycenter of the measure μ.In our case, we have thatf(x1)=f1(a), f(x2)=f2(b), and f(x3)=f3(c) and the barycenter is given by(24)bu=argminz⁡∫Nd2z,x-d2y,xdμx=argminz⁡∫Nd2z,xdμx.We are now able to prove the following result.Theorem 18.
Let(N,d) be a tripod and x1,x2,x3∈N. Then for each convex function f:N→R one has the following inequality:(25)fx1+fx2+fx3+3fx1+x2+x33≥2fx1+x22+2fx1+x32+2fx2+x32.Proof.
The proof can be managed by using only majorization tools, as in the classical proof of Popoviciu’s inequality but for convenience of the reader we present a more detailed proof.
If the pointsx1,x2,x3 are belonging to one or two arms of the tripod, the proof is obvious. Without losing the generality, we suppose that f(o)=0; otherwise we consider the function f-f(o).
Hence, we consider only the case when the pointsx1,x2,x3 belong to three different arms N1,N2,N3. In our case, we have that f(x1)=f1(a), f(x2)=f2(b), f(x3)=f3(c).
In order to find the pointr=(x1+x2+x3)/3, we need to compute the minimizers of the following expressions, depending on which arms we are looking for: (26)argmin3,r,r≥0⁡13r+a2+13r+b2+13c-r2;argmin2,r,r≥0⁡13r+a2+13b-r2+13r+c2;argmin1,r,r≥0⁡13a-r2+13r+b2+13r+c2.
It follows that we have the following cases.(i)
Ifc≥a+b then (27)r=3,c-a-b3.(ii)
Ifb≥a+c then (28)r=2,b-a-c3.(iii)
Ifa≥b+c then (29)r=1,a-b-c3.(iv)
Otherwiser=o.Suppose that a≥b≥c. Hence, by a similar computation we have that (x1+x2)/2=1,(a-b)/2, (x1+x3)/2=1,(a-c)/2, and (x2+x3)/2=2,(b-c)/2. If a≥b+c we are in the third case and we have that (30)x1+x2+x33=1,a-b-c3.
Popoviciu’s inequality given by (25) is reduced to the following form:(31)f1a+f2b+f3c+3f1a-b-c3≥2f1a-b2+f1a-c2+f2b-c2.
It can be easily seen that(a-c)/2,(a-c)/2,(a-b)/2,(a-b)/2≺a,(a-b-c)/3,(a-b-c)/3,(a-b-c)/3, where ≺ denotes the classical majorization from R4. Hence, we have that(32)f1a+3f1a-b-c3≥2f1a-b2+2f1a-c2.
Since the juxtaposition of the two armsf2:N2→R and f3:N3→R gives a convex function given by f~:R→R, with f~(x)=f2(x) and f~(-x)=f3(x), ∀x≥0, we deduce that(33)2f2b-c2=2f′b-c2≤f′b+f′-c=f2b+f3c.
Summing the estimates (32) and (33) we obtain (31). Hence, the proof of (25) is finished in each of the first three cases.
It remains to study the fourth case, that is,b+c>a≥b≥c and (x1+x2+x3)/3=o. In this case, we need to prove that(34)f1a+f2b+f3c+3f0≥2f1a-b2+2f1a-c2+2f2b-c2.The proof is similar and uses only the convexity hypotheses.


## 4. Extreme Points of Convex Functions Defined onK-Spiders

This section is devoted to the study of the minimizers and maximizers of a convex function defined on aK-spider.In a metric space with global nonpositive curvature the notion of convex hull is introduced via the formula(35)co⁡⁡F=⋃n=0∞Fn,where F0=F and for n≥1 the set Fn consists of all points in E which lie on geodesics which start and end in Fn-1.Note that the closed convex hull of every nonempty finite family of points ofE has the fixed point property. This fact can be used to prove the analogue of the Schauder fixed point theorem; see [13].Definition 19.
One says thatx∈A is an extremal point for the convex set A⊂N if x does not belong to the interior of some geodesic segment with the ends in A.Remark 20.
Note that the convex hull of subset of aK-spider N is also a K-spider included in N.Taking into account the above definitions, it follows that the classical Minkowski’s theorem holds in the context ofK-spiders. Minkowski’s theorem says that each point from a closed convex set can be written as a “convex combination” of extremal points; more precisely, it belongs to the convex hull of the extremal points. In global NPC space this result is a very difficult problem. In the context of K-spiders, since the geodesics are too similar to line segments, the proof follows in the same manner as in the classical case. For more details, see [16].We are now in position to prove our first result of this section.Theorem 21.
Let(N,d) be a K-spider and let f:A→R be a convex function defined on a closed convex subset A⊂N. Then f attains its supremum on an extremal point. As a consequence, if f attains its maximum in an interior point, then f is a constant function.Proof.
The convexity of the functionf gives us the possibility to consider a point xM∈A such that (36)fxM=sup⁡x∈A⁡fx.By using Minkowski’s theorem it follows that there exist some extremal points e1,…,en of the set A and λi>0, i=1,…,n, with ∑i=1n‍λi=1 such that (37)xM=argminz∈A⁡∑i=1nλid2z,ei.
Jensen’s inequality gives that(38)fek≤fxM≤∑i=1nλifei≤max⁡i=1,…,n⁡feik=1,…,n.
Hence, we have thatf(xM)=max⁡i=1,…,nf(ei) and the proof is finished.The following results are devoted to the minimizing properties of a convex function defined on aK-spider.Theorem 22.
Let(N,d) be a K-spider and let f:A→R be a convex function defined on a convex subset A⊂N. If xm∈A is a local minimum for the function f then xm is a global minimum of f; that is, (39)fxm=inf⁡x∈A⁡fx.Proof.
Sincexm is a local minimum, there exists r>0 such that (40)fxm≤fxx∈Brxm.
Letx∈A∖Br(xm) arbitrarily fixed. If we choose a point x~≠xm, x~∈Br(xm)∩co⁡{x,xm} then there exists λ∈(0,1) such that (41)x~=argminz∈N⁡1-λd2z,x+λd2z,xm.
From Jensen’s inequality we have that(42)fxm≤fx~≤1-λfx+λfxm;hence, we have that f(xm)≤f(x) and the proof is finished.We need to mention that we hope that the present results can be used in a future paper to treat some problems for difference equations involving convex nonlinearities as in [17]. In this context, the points of discretization can be viewed as the origins of some K-spiders verifying some special gluing conditions.In the same context, the existence of a minimizer is proved in Proposition 2 from [1] when the majorization is introduced as in Definition 2. This existence result gives an interesting application of majorization at equity in location analysis. For instance, when locating a public facility, the majorization concept offers a good strategy to optimize the distribution of the distances to its customers. In Erkut [18] several different inequalities measures are studied, for the distribution d=(di(x):i≤N) of the distances between a facility x and its customers i=1,2,…,N. In this sense, an example is given by the measure ∑i=1N‍(di-dm)2, where dm is the average d=1/N∑i=1N‍di. One may then look for a facility location which minimizes the selected inequality measure, in some sense, the result says that the distances to the different customers are as equals as possible.



---

*Source: 710516-2015-05-14.xml*