How Pareto optimizations of distances relate to closed convex hulls

Introduction

For a real normed space , let and . Define (specially, ), where denote the respectively open and closed ball centered at with radius , and This article studies the four properties: where denotes the closed convex hull of .

Based on the property of , the four properties multiply to sixteen properties: means holds for all finite ; means holds for all compact ; means holds for all bounded ; means holds for all ; and similarly for .

We assume throughout. For , all sixteen properties then hold trivially, so proofs involving may assume it is nonempty. If and empty sets of ideal points are allowed, fails for .

Some of the properties are stronger than others. First, all finite sets are compact, and all compact sets are bounded. Second, we can easily see that . Therefore,

The established characterizations and the remaining gaps are summarized in the following table:

Here, a plane means a two-dimensional real normed space. See Definition for balanced tangent chords.

If we only consider the characterizations of spaces satisfying both and (or both and ), then there are no open gaps:

In the following sections, a vector space is assumed to be over the real numbers unless otherwise specified.

Background

The background of this study is in economics, where preference relations and Pareto efficiency are studied.

My motivation of studying the properties originates from my previous article on voting systems, dates back to more than three years ago.

In the end of that article, I used an example of this preference relation: an agent prefers points nearer to the ideal point. Mathematically, it says that in the metric space , for an agent with ideal point , iff . Such a preference relation is what I call a distance preference relation.

That article also focuses on the concept of Pareto efficiency, or particularly, weak Pareto efficiency. Suppose that we have a set of agents, and we denote the preference relation of each agent as , and suppose all preference relations are complete over a space . Then, we say is a strong Pareto improvement of iff ; is a weak Pareto improvement of iff . Note the terminological quirk: a strong Pareto optimal has no weak Pareto improvement, and a weak Pareto optimal has no strong Pareto improvement. Note that neither concept is the actual definition of Pareto improvement used in economics, which says that is an (economic) Pareto improvement of iff and . However, since the weak Pareto improvement and the strong Pareto improvement have simpler mathematical definitions, they will be the focus of this article.

The set of all strong Pareto improvements of is denoted as . We say is weak Pareto optimal iff , and the weak Pareto set is the set of all weak Pareto optimals, denoted as . Similarly, we can denote the set of weak Pareto improvements as . We say is strong Pareto optimal iff , and the strong Pareto set is the set of all strong Pareto optimals. When is a metric space and the preference relations are distance preference relations, the definitions of , , , and match exactly with the definitions in Equation and Equation .

In the end of my previous article referenced here, there was an example taking as a Euclidean plane as an example. There was a figure visualizing the weak Pareto sets for finite numbers of agents, but I never explained how I derived the weak Pareto sets. From the figure, it seems that the weak Pareto set is the convex hull of the ideal points of the agents. I originally planned to prove this in that article, but it turned out that it was too difficult, so I just left it without justification.

Questions of the same type were raised and answered by Durier (1987). In his paper, he called the strictly efficient points, the weakly efficient points, and the economic Pareto set the efficient points. He also studied another type of optimal points called the properly efficient points.

Preliminaries

Theorem 1. If a normed space is not strictly convex, then it does not satisfy .

Proof

Let be a normed space that is not strictly convex. Its unit sphere contains a nontrivial line segment, so there exist distinct unit vectors such that . Set .

Suppose for contradiction that We then have and . The triangle inequality gives a contradiction. Therefore, , so .

Suppose for contradiction that Then there exists such that . Taking the norm on both sides gives These two inequalities imply . This then gives , which implies . This contradicts with . Therefore, .

Thus, we have found a counterexample to .

Theorem 2. If a normed space is not strictly convex, then it does not satisfy .

Proof

Let be a normed space that is not strictly convex. Its unit sphere contains a nontrivial line segment, so there exist distinct unit vectors such that . Set and . Obviously we have . We have

Now set . Because are distinct vectors, we have . We also have Therefore, . We have found a counterexample to .

Theorem 3. Let be a strictly convex space and . Then, .

Proof

We obviously have , so it is sufficient to prove .

Let . Then there exists , which satisfies . Let . For each , because otherwise would force . If , the triangle inequality gives . If the two norms are equal, their vectors are distinct, so strict convexity gives Therefore, , so .

Other preliminaries

Definition 4. Let be a normed space. The (open) Voronoi cell w.r.t. of is the set Also denote , called the Voronoi cell of . Similarly, the closed Voronoi cell w.r.t. of is and denote .

Theorem 5. We can equivalently rewrite and as follows:

Proof

By Definition , we have . Then, can be rewritten as Translate by , and rename the translated set . Since translation preserves finiteness, boundedness, and closed convex hulls, this gives Using some first-order logic, we can rewrite this as Now dictate it to be true for all finite, bounded, or arbitrary , and we get By the same argument, we have

One of the equivalent definitions of the convex hull is the set of all convex combinations of finitely many points in the set. Notice that for finite , is exactly the set of convex combinations of . Therefore, we have Thus,

When can be any set such that , one case is to have . We then have Thus,

By the same arguments, we have

Definition 6. Let be a normed space. Then, the subdifferential at is defined as An element of is called a subgradient at . Moreover, is said to be smooth at if there is a unique subgradient at , and we say is smooth if it is smooth at every nonzero point.

Theorem 7. Let be a normed space. For any , is a nonempty weak*-compact convex subset of , and it has the following properties:

Proof

When , is the closed unit ball of . It is weak*-compact by the Banach–Alaoglu theorem. All other properties are trivial. From now on, we assume .

To prove that is nonempty, we define a linear functional on the one-dimensional subspace of as . We can easily find that this functional has norm . By the norm-preserving Hahn–Banach continuous extension theorem, we can extend it to a linear functional with . We can easily see that , so is nonempty.

To prove that is convex, let and . By definition of , we can easily see that .

To prove that is weak*-compact, first note that is a weak*-continuous linear functional on by the definition of the weak* topology. Its preimage of any closed set on is then weak*-closed. Then, from we see that is the intersection of a weak*-compact set and a weak*-closed set, so is weak*-compact.

Equation is easy to verify from the definition of .

To prove Equation , write

All properties have been proven.

Definition 8. Let be a vector space, , and be a function defined on a subset . The directional derivative of in the direction of is a function defined as The domain is all points where this expression makes sense (i.e., such that is a limit point of ) and the limit exists.

Theorem 9. Let be a normed space and . Then, is defined on all of , and it satisfies

Proof

For fixed , define as By Definition , we have .

First prove that exists. By the triangle inequality, when , we have so is a monotonically non-decreasing function on . Also, we have so is bounded below. Therefore, exists.

To prove that , note that this statement is exactly , which follows from the monotonicity of .

Then prove that exists. This follows by maximizing the weak*-continuous function over the nonempty weak*-compact set .

By Equation , we have , which simplifies to . Maximize over and taking infimum over on both sides to get

Now we will explicitly construct a linear functional such that and later show that . To construct it, we will use the Hahn–Banach dominated extension theorem, for which we need to construct a sublinear functional as the dominating functional. For that we use .

First, we prove that is sublinear. The positive homogeneity, i.e., , is obvious from the definition. For subadditivity, convexity gives Subtract , divide by , and take to obtain .

Then, define a linear functional defined as . We can check that so that is dominated by on . The check is trivial for . For , noticing that , we have

We can thus apply the Hahn–Banach dominated extension theorem to extend to a linear functional such that and that is dominated by on all of .

Now we need to show that . For any , we have where the first inequality is because is dominated by and the second inequality is because is monotonically non-decreasing.

Substitute with in Equation to get . Substitute with in Equation to get . We then have .

Substitute with in Equation to get . Substitute with in Equation to get . We then have , which means .

With and , we have .

Theorem 10. Let be a normed space. If there exist such that and , then is not strictly convex.

Proof

Let . Define and . Then, . Because , we have On the other hand, by the triangle inequality, we have Squeezing by the two inequalities, we have . This means is not strictly convex.

Theorem 11. Let be a strictly convex space and . Then, , where is the closure of .

Proof

Because and is closed, we have . Suppose for contradiction that there exists .

Note that so . Because , there exists such that . In other words, For any and , we have Take the right derivatives of both sides w.r.t. at . Theorem guarantees that the derivatives exist: Because is weak*-compact and convex by Theorem , we have ; otherwise the Hahn–Banach separation theorem breaks the inequality above.

Why

Suppose for contradiction that there exists . Because is weak*-compact and convex, by the Hahn–Banach separation theorem, there exists (the set of weak*-continuous linear functionals on ) such that This is a contradiction.

We then have . Here and are distinct nonzero vectors of equal norm, so their normalizations are distinct. By Theorem , is not strictly convex, a contradiction.

Definition 12 (Birkhoff, 1935). Let be a normed space, and let . We say is Birkhoff–James orthogonal to , denoted as , if For a set , one denotes if .

Theorem 13. Let be a normed space such that . For any , there always exists such that . Such always satisfies that are linearly independent. Specially, when is a strictly convex plane, is unique up to a scalar multiple.

Proof

First prove the existence. Choose such that are linearly independent. Then, is a continuous function of . By the triangle inequality, we have , so as . Such a continuous function must have a global minimum at some . Define , which must be nonzero as are linearly independent. Then, for any , so .

Then prove that and imply that are linearly independent. Suppose for contradiction that are linearly dependent, i.e., for some . Then, by definition of the Birkhoff–James orthogonality, for any , Divide both sides by to get for any , which is false. By contradiction, are linearly independent.

Finally, prove the uniqueness in a strictly convex plane. Suppose that and and that . Because are linearly independent and the space is a plane, they form a coordinate system. Then, we can express for some . We must have because otherwise and are linearly dependent. By , we have for any . Divide both sides by and substitute to get On the other hand, by , we have for any . Substitute to get Combining Equations and , we have Suppose by contradiction that . Then, are two distinct points on the unit sphere. Because the space is strictly convex, . On the other hand, where the inequality is by . This is a contradiction, so we must have . Therefore, for some , which proves the uniqueness of up to a scalar multiple.

Inner product spaces

Lemmas

Lemma 14 (Kakutani, 1939, Theorem 4). Let be a 3-dimensional normed space. If every 2-dimensional vector subspace of is the range of a linear projection of norm , then is an inner product space.

Lemma 15. Let be a Hilbert space, be nonempty, closed, and convex, and . Then, there exists such that .

Proof

By the Hilbert projection theorem, there exists such that Because is convex, . Substitute into Equation and square both sides to get Subtract from both sides and divide both sides by (assuming ) to get Take infimum over on both sides, and we have .

Lemma 16. Let be a finite-dimensional normed space. For any nonempty compact convex set , there exists a finite set such that .

Proof

If is a singleton, take . Otherwise, let and choose a basis on . Fix and interpret on as the affine function . For each , choose that minimizes and choose that maximizes . Such points must exist because is compact.

Define . Suppose . Obviously, . For every , we have The two inequalities forces , so .

Theorem 17. An inner product space satisfies .

Proof

Let be an inner product space. Suppose for contradiction that does not satisfy . By Theorem , there exists such that . Therefore, there exists a sequence of finite sets such that for any and that , where, for any , for any , and .

By Definition , we have for any . Square both sides and simplify, and we get . Therefore, On the other hand, because the inner product is continuous, which is a contradiction.

Theorem 18. If a normed space with is not an inner product space, then it does not satisfy .

Proof

Suppose for contradiction that satisfies . Pick a non-inner-product 3-dimensional subspace .

Why exists

The Jordan–von Neumann theorem states that a normed space is an inner product space if the norm satisfies the parallelogram law. Therefore, because is not an inner product space, there exist failing the parallelogram law. Pick . Then, is a 3-dimensional subspace of that is not an inner product space.

For any , consider . Since is open in , is open in . By and Theorem , , so . By the Hahn–Banach separation theorem, there exists a continuous linear functional such that . Since , we have . Define Then, is a linear projection from onto with .

Why is a projection onto

First, for any because

Then, is a projection because

Finally, maps onto every point in because for any , we have .

Why

Generally, any nonzero bounded linear projection has norm at least by submultiplicativity, so we just need to show .

For any , we have , which means . Similarly, for any and , we also have , which means , or equivalently . This inequality obviously also holds for .

Because , we have . Therefore, for any , there exist unique and such that . Then, we have This shows .

Then, the adjoint is a linear projection from onto , and . Noticing that , we have that is onto .

In general, any hyperplane in can be expressed as for some . Therefore, by Lemma , is an inner product space, so is an inner product space. This contradicts with the choice that is not an inner product space.

Therefore, does not satisfy .

Theorem 19. A Hilbert space satisfies .

Proof

Let be a Hilbert space. Let and . By Lemma , there exists such that . Consider Subtract from both sides to get Therefore, , so , proving .

Theorem 20. An inner product space that is not a Hilbert space does not satisfy .

Proof

Let be an inner product space that is not a Hilbert space. Let be the completion of , which is a Hilbert space, and choose . Let , which is a nonempty closed affine hyperplane in .

Why is nonempty and closed

Suppose for contradiction that is empty. Then, . Because is dense in , we have , which implies . This contradicts with . Therefore, is nonempty.

To see that is closed, notice that is a bounded linear functional on , so it is a bounded linear functional on .

Obviously, . Now suppose for contradiction that , which means . Expanding the square gives . Therefore, the linear functional is bounded below on the affine hyperplane , so is constant on , so is zero on the linear hyperplane parallel to . This means , so is parallel to . However, while , so this is impossible for , a contradiction. Therefore, .

Therefore, we find a counterexample to .

Theorem 21. An inner product space satisfies .

Proof

Let be an inner product space and . Let be bounded and . Because is bounded, is bounded, so there exists such that .

Denote the completion of , which is a Hilbert space. Then, , either. By Lemma , there exists such that . Add both sides by to get .

Now, choose close enough to such that which is always possible because is dense in . Then, for any , we have

By the triangle inequality, We can then choose to get Therefore, , so , proving .

Theorem 22. Let be a normed space with . If is not an inner product space, then does not satisfy .

Proof

Because is not an inner product space, is not an inner product space. By Theorem , does not satisfy . This means there exists and a finite set such that . There exists such that for every , that , and that . Without loss of generality, we can assume for every because we can always discard such that from .

For every , define where is the closed unit ball in . We then have where the last inequality is by .

Because is finite-dimensional, is compact, so every is a nonempty compact convex set. By Lemma , there exists finite set such that . Define . By Equation , we then have . Therefore, .

Now let . We then have . On the other hand, for , Therefore, . Then, forces . Then, for any , we have and , which means . We now have , implying .

Therefore, we have . This gives a counterexample to .

Theorem 23. Let be a normed space with . If is not an inner product space, then it does not satisfy .

Proof

Because is not an inner product space, is not an inner product space. By Theorem , does not satisfy . By Theorem , there exists such that . There then exists a finite set and positive numbers such that and . We can always choose such that .

Why we can make

Because is open, it contains a neighborhood of . Therefore, there exists a small enough such that . There then exists a finite set and positive numbers such that and . Therefore, where

For every , define , where the inequality is because . Choose a sequence in , the unit sphere of , such that and that for every . Such a sequence always exists because of the definition of the norm on and the definition of sequence limit. Then,

Define . Because , it is bounded. Because , we have .

Let . For any , we then have Take , and we have . Then, forces . Therefore, .

Therefore, . Now consider two cases, and . For the first case, we have , which is a counterexample to .

For the case , we pick a fixed and define where is the unit sphere in . Since , has the same positive lower bound as , so .

Let . Suppose for contradiction that . Define and . We then have .

Pick some subgradient . Then, Therefore, . Then, This contradicts with . Therefore, , so , which is a counterexample to .

Planes

Definition 24. A normed space has balanced tangent chords at if there exist , , and such that and We say has balanced tangent chords if this holds at every .

Definitions and lemmas

Definition 25. Let be a normed plane, and let such that . Then, is a basis of , forming a coordinate system to express every vector in as for some . The number is called the bisector coordinate, and the number is called the descent coordinate. In this context, is called the bisector direction, and is called the descent direction. In a context where a bisector coordinate system is already set up, we denote the coordinate projection of the bisector coordinate as and the coordinate projection of the descent coordinate as , i.e., and .

Definition 26. Let be a normed space, and let such that . Define the bisector function as When a bisector coordinate system with basis is already set up in the context, we abbreviate as .

Definition 27. A normed space is said to be positively bisectable at if there exists nonzero such that Moreover, is said to be positively bisectable if it is positively bisectable at every .

Lemma 28. The bisector function is nonnegative. Furthermore, if is nonzero and is the only nonzero vector in such that up to scalar multiples, then .

Proof

Let be a normed space, and let such that . If or , the result is trivial. We assume from here and use a bisector coordinate system with basis in their spanned plane.

By the triangle inequality, for any , the function is convex. Difference on a fixed interval of a convex function is monotonic, so is monotonically non-decreasing in . By Definition , we can easily see that . Therefore, is nonpositive on .

By Definition , we have , where By the previous paragraph, we have , so . Therefore, .

Now, if is the only nonzero vector such that up to scalar multiples, we prove that . We have the strict inequalities and because otherwise or would be Birkhoff–James orthogonal to . We can then easily see that and . Because is continuous and non-decreasing, we then have . Therefore, .

Lemma 29. In a normed plane with a bisector coordinate system with basis , the Voronoi cell .

Proof

Choose such that . Let be the basis of the bisector coordinate system. By the triangle inequality, for any , the function is convex. Difference on a fixed interval of a convex function is monotonic, so is monotonically non-decreasing in . By Definition , we have . Therefore, .

Now, for any , we can express it as in the bisector coordinate system. Substitute it in the definition of , and we have . By Definition , we have . Therefore, This means .

Lemma 30. The bisector function is positive in a neighborhood of .

Proof

Let be a normed space, and let such that . If or , the result is trivial. We assume from here and use a bisector coordinate system with basis in their spanned plane.

By Definition , we have . By the triangle inequality, we have Therefore, . Solving this inequality for gives (taking into account that by Lemma )

Solving for

Rearrange the inequality to get The left-hand side is We do not need to consider the case because . Because , the inequality is always satisfied when . The only nontrivial case is when , where the inequality becomes . Therefore, the full solution to the inequality is

This implication relation then translates to the inequality Noting that the right-hand side is positive when is in a neighborhood of , we get that is positive when is in a neighborhood of .

Lemma 31. Let be a normed space and . If there exists two linearly independent vectors such that and that are linearly dependent, then has balanced tangent chords at .

Proof

The case when is trivial, and we assume from here.

Because are linearly dependent, we can express for some . We know are linearly independent by Theorem , so . Because are linearly independent, we have . Now define We then have and . Obviously, we have , and all of them are nonzero.

Notice that forces to be non-increasing on , which is equivalent to being non-increasing on . On the other hand, forces to be non-decreasing on . Simultaneously satisfying both monotonicity conditions forces to be constant on . Define and we then have Therefore, which means that .

We have whenever . Pick . This satisfies the condition for all . Therefore, has balanced tangent chords at .

Lemma 32. For a normed space, positive bisectability at is equivalent to having balanced tangent chords at .

Proof

The case is immediate, so assume . For a nonzero , write . This convex function has its minimum at , so it is non-decreasing along either ray from .

First prove that having balanced tangent chords at implies positive bisectability at . Suppose that for . Define For , we have . For , the triangle inequality gives Thus .

Set . For , we have Therefore, . Also . Therefore, positive bisectability at is proven.

Conversely, prove that positive bisectability at implies having balanced tangent chords at . Define . The fact that means that . This reduces to The same inequality holds at . This proves balanced tangent chords, with .

Theorem 33. A normed plane satisfies .

Proof

Let be a normed plane and be a bounded set such that . Suppose for contradiction that . By Definition , we have .

Because is bounded in a finite-dimensional space, we have , where is the closure of . Therefore, . By Carathéodory’s theorem, there exists at most points such that is a convex combination of , i.e., there exists such that and . We can further dictate that because we can simply discard any with .

Why

The closure is a closed bounded set in a finite-dimensional space, so it is compact by the Heine–Borel theorem. Because is the image of a compact set (where is the 2-dimensional unit simplex embedded in ) under the continuous map , is also compact, so it is closed.

Now, taking the convex hull preserves set inclusion, and we have , so . Because is closed, it must contain the closure of , so we have .

On the other hand, taking the closure preserves set inclusion, and we have , so . Because is convex, it must contain the convex hull of , so we have .

We then have .

Set up a bisector coordinate system with as the descent direction. Denote the bisector direction as . We can always choose so that .

Why we can choose so that

Let such that . By Definition , we have . Define . Because is continuous, is closed. Define . We can easily see that and .

Because , we have , where is the closure of . By Lemma and Lemma , we have Take the closure to get Therefore, all has nonnegative -coordinates, i.e., for all . On the other hand, acting on the convex combination gives . Because for all , we must have for all . We then have for all .

Consider two cases. For the first case, all are the same point. Because their convex combination is , we then have for all . We then have , which means , so . However, cannot contain by definition, so this is a contradiction.

For the second case, at least two are different points. Because , there must exist with and another with . Without loss of generality, suppose that . Then, because , we have . On the other hand, since , we have This gives a contradiction.

Either way, we have a contradiction, so .

Theorem 34. A strictly convex plane satisfies .

Proof

Let be a strictly convex plane and be a bounded set such that . Suppose for contradiction that . By Definition , we have . Because is already a closed set, we have , where is the closure of .

Set up a bisector coordinate system with as the descent direction. Denote the bisector direction as . By Lemma and Lemma , we have Take the closure to get By Theorem , we have , so we have .

All the rest of the proof is almost the same as the proof of Theorem . However I will repeat it here for completeness.

Because is bounded in a finite-dimensional space, we have . Therefore, . By Carathéodory’s theorem, there exists at most points such that is a convex combination of , i.e., there exists such that and . We can further dictate that because we can simply discard any with .

Because , all has nonnegative -coordinates, i.e., for all . On the other hand, acting on the convex combination gives . Because for all , we must have for all . We then have for all .

Consider two cases. For the first case, all are the same point. Because their convex combination is , we then have for all . We then have , which means , so , contradicting with .

For the second case, at least two are different points. Because , there must exist with and another with . Without loss of generality, suppose that and . Then, because , we have and . Adding them together gives By the triangle inequality, Therefore, we have , which means is also on since is strictly convex, but this is impossible because we dictate to be linearly independent in the definition of the bisector coordinate system, so this is a contradiction.

Either way, we have a contradiction, so .

Theorem 35. A normed plane with balanced tangent chords satisfies .

Proof

Let be a normed plane with balanced tangent chords. By Theorem , to prove that satisfies , it is equivalent to prove that for any , where is the Voronoi cell of . The case where is trivial, and we assume from here.

By Lemma , is positively bisectable. This means we can choose a nonzero such that .

Set up a bisector coordinate system with basis . Then, by Lemma . By the bound, we have , so . We then obviously have .

Theorem 36. A strictly convex plane with balanced tangent chords satisfies .

Proof

Let be a strictly convex plane with balanced tangent chords. By Theorem , to prove that satisfies , it is equivalent to prove that for any , where is the closed Voronoi cell of .

By Lemma , is positively bisectable. This means we can choose a nonzero such that .

Set up a bisector coordinate system with basis . Then, by Lemma . By the bound, we have . Take the closure to get . By Theorem , we have , so . We then obviously have .

Theorem 37. A normed plane without balanced tangent chords does not satisfy .

Proof

Let be a normed plane without balanced tangent chords. By Theorem , to prove that does not satisfy , it is equivalent to prove that there exists such that .

By Lemma , is not positively bisectable. Choose at which positive bisectability fails. For every nonzero , nonnegativity of the bisector function then gives . Fix one such . Since trivially cannot satisfy this condition, we assume from here. Set up a bisector coordinate system with basis .

By Lemma , is the only nonzero vector in such that up to scalar multiples. Therefore, by Lemma , we have for all .

The zero infimum of means there exists a sequence such that . Define Because by Lemma , we have . Then, the convex combination The limit of is then in , so .

Theorem 38. A strictly convex plane satisfies .

Proof

Let be a strictly convex plane. We need to prove that for any and such that , we have .

Define , and we have . Because is a closed convex set, by the Hahn–Banach separation theorem, there exists and such that . Define , and we have .

Pick any . By Theorem , there exists . Pick any . Then, by Equation , we have . Therefore, . By Theorem , are linearly independent, so . Define .

Set up a bisector coordinate system with basis . We have and , so . Then, is equivalent to . By Lemma , we have for all . By Lemma , we have . Therefore, By Definition , we can easily see .

Theorem 39. A normed plane satisfies .

Proof

Let be a normed plane. We need to prove that for any and such that , we have .

Define , and we have . Because is a closed convex set, by the Hahn–Banach separation theorem, there exists and such that . Define , and we have