Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Question: Let $S$ be a convex weakly compact set in Banach space $H$. Propose a natural way to define the unique center $O \in S$.

Motivation: A lot! For example, in game theory $S$ can be a set of possible (fair) allocations, and we need to suggest a natural method to choose one.

Discussion. If S consists of 2 points, or line in $\mathbb R^2$, we have no natural way to select a center, thus $S$ should be convex and weakly compact. To define these properties, we need vector space and topology, thus the natural setting is Bahach space. If $H$ is $\mathbb R^n$, the natural choice is centroid (center mass), but to define it for general case, we need a natural notion of "uniform density" in a Banach space. Is this someting standard which I do not know? My main example is $H = L^1$, space of all intergable functions $[0,1]\to \mathbb R$. In this case if $S$ consists of all functions with range in $[a,b]$, the center should naturally be a constant function $f(x)\equiv (a+b)/2$. Also, $O$ should be tractable to compute, at least for such a simple examples of $H$ and $S$. A good axiomatic foundation ($O$ is the unique point saisfying axioms A1, A2, and A3) would be a plus.

share|improve this question
    
You might also ask the same question for norm-compact subsets of Banach spaces. The definition of centroid is somewhat more likely to exist in that more restricted case (but I still don't know how it would go). –  André Henriques Jun 14 '12 at 18:06
2  
In the L1 setting you can still define a Chebyshev center, but it may sometimes lie outside of your closed convex set, and it may not be unique. If you want the center to be preserved by isometries then likely the best that can be done is Theorem A in: Bader, Gelander, Monod: A fixed point theorem for L1 spaces. (springerlink.com/content/fv17437n8v104867) –  Jesse Peterson Jun 14 '12 at 23:40
1  
For my applications, it is absolutely crutial for the center to belong to the set. This is not the case in Theorem A you mention, as well as for Chebyshev center... –  Bogdan Jun 15 '12 at 8:10

3 Answers 3

I propose the axiom that any isometry between two such sets must take the center of one onto the center of the other. This axiom by itself is consistent with the existence of a center for every weakly compact convex set by the Ryll-Nardzewski fixed point theorem (we need the group of isometries of $S$ onto itself to always have a fixed point), and it alone already uniquely determines the center in some cases. For example, let $S$ be the positive part of the unit ball of $l^p({\bf Z})$ for $1 < p < \infty$. Translation (taking the sequence $(a_n)$ to the sequence $(a_{n-1})$) is an isometry of this set onto itself, and the only fixed point is the origin.

This example shows that the center will sometimes be an extreme point, which may be counterintuitive. But it's actually reasonable if you look at the center of mass of the positive part of the unit ball of $l^p_n$; as $n \to \infty$ it does converge to the origin (weakly, regarding $l^p_n$ as sitting inside $l^p$).

share|improve this answer
1  
Yes, this axiom makes sence. However, the non-uniqueness is very serious. Actually, for generic convex compact set S in R^2 there is no nontrivial isometry preserving S, thus any point can be a center! Theorem 1 in Teck-Cheong Lim: The center of a convex set (1981) ams.org/journals/proc/1981-081-02/S0002-9939-1981-0593489-7/… defines the unique center, and it satisfies your axiom. What I do not like is that 1) this construction uses transivite induction and thus can be hardly applied on practice; 2) in case of R^n it does not coincide with centroid. –  Bogdan Jun 15 '12 at 8:26

For the sake of readability, I am going to make this a separate answer. In response to my other answer, Bogdan points out that preservation under isometries need not determine the center. I suppose in most cases it wouldn't.

What I want to say here is that it doesn't seem possible to have a good infinite dimensional generalization of the centroid in ${\bf R}^n$, even for norm compact convex sets, for the following reason: already in finite dimensions we can have convex sets $A \subset B$ such that $B$ is contained in the $\epsilon$-neighborhood of $A$ but the centroid of $B$ is far away from the centroid of $A$. For instance, let $A$ be the line segment $[0,1]$ in ${\bf R}^1$ cross a ball about the origin of radius $\epsilon^2$ in ${\bf R}^n$, and let $B$ be the convex hull of $A$ together with the ball about the origin of radius $\epsilon$ in ${\bf R}^{n+1}$. If $n >> 1/\epsilon$ then every point of $B$ is close to $A$, but because of the way volume scales in large dimensions (the volume of a ball goes like its radius to the $n$) almost all of the mass of $B$ is near the origin. But the centroid of $A$ is halfway along the line segment.

We can use this phenomenon to construct a sequence of finite dimensional sets $A_1 \subset A_2 \subset \cdots$ in $l^2$ such that each $A_{n+1}$ is contained in the $2^{-n}$-neighborhood of $A_n$, but the centroid of $A_{n+1}$ is far from the centroid of $A_n$. We can make the centroid bounce back and forth on a line segment. So where should the centroid of ${\overline{\bigcup A_n}}$ be? It looks like we have to take the limit of a sequence that doesn't converge. There won't be any canonical way to do this.

I could add that there is a simple procedure that will sometimes work. For each finite dimensional subspace $V$ let $x_V$ be the centroid of $S \cap V$. Then consider the net $(x_V)$ with the finite dimensional subspaces ordered by inclusion. If this net converges, that seems like a good definition for the centroid of $S$.

share|improve this answer

I believe that, at least in the case of a weakly compact convex set $K$ in a uniformly convex Banach space $X$, the circumcenter could be a possible good candidate. By circumcenter I mean a point which is a solution to the following minimization problem: $$ \bar r := \inf_{x\in K} \min\{ r\geq0 \mid K\subseteq\bar B(x,r) \}, $$ where $\bar B(x,r)$ denotes the closed ball.

It is immediate to verify that the problem has a solution. Indeed, if $(x_n)_{n\in\mathbb N}\subset K$ is a minimizing sequence, that is, there exist $r_n\to\bar r$ such that $K\subseteq\bar B(x_n,r_n)$, possibly extracting a subsequence we can assume that $x_n\rightharpoonup\bar x$, then we have $$ |y-\bar x| \leq \liminf_{n\to\infty} |y-x_n| \leq \liminf_{n\to\infty} r_n = \bar r \qquad \text{for all $y\in K$}, $$ which implies that $K\subseteq\bar B(\bar x,\bar r)$.

The remaining problem is the uniqueness. Assume that $x_1$ and $x_2$ are two circumcenters and set $\varepsilon=|x_1-x_2|$. By the uniform convexity, there exists $\delta>0$ such that $|u|\leq\bar r$, $|v|\leq\bar r$ and $|u-v|\geq\varepsilon$ imply $\left|\frac{u+v}2\right|\leq\bar r-\delta$. Now, if we take $y\in K$, we have $|x_1-y|\leq\bar r$, $|x_2-y|\leq\bar r$ and $|(x_1-y)-(x_2-y)|=\varepsilon$, therefore $\left|\frac{x_1+x_2}2-y\right|\leq\bar r-\delta$. But this contradicts the minimality of $\bar r$, because we have found $K\subseteq\bar B\left(\frac{x_1+x_2}2,\bar r-\delta\right)$.

To tackle the non uniformly convex case, I just have an idea, but I'm not sure if it's going to work. Maybe someone else can think about it. Given a weakly compact convex set $K_0$, we define $r_0$ as the optimal radius above and we consider the set $K_1=\{ x\in K \mid K\subseteq\bar B(x,r_0) \}$. The set $K_1$ is non-empty, convex (thanks to the convexity of the norm) and closed (I believe, by the same reasoning used for the existence). Thus, we have found another weakly compact convex set $K_1\subseteq K_0$. By iterating this argument, we find a nested family of compact sets $K_{n+1}\subseteq K_n$. Then the intersection $K_\infty=\bigcap_{n\in\mathbb N}K_n$ is non-empty. The hope is that one could get that $K_\infty$ is a singleton by proving something like $r_{n+1}\leq r_n/2$, or $\mathop{\mathrm{diam}}(K_{n+1})\leq\mathop{\mathrm{diam}}(K_n)/2$.

Note to future self for improvement

We have $\mathop{\mathrm{diam}}(K_{n+1}) \leq r_n \leq \mathop{\mathrm{diam}}(K_n) \leq 2r_n$.

  • The first inequality is sharp. Example: $K_0=[0,1]\times[-1,1]\subset\mathbb R^2$ with the $\lvert\,\cdot\,\rvert_\infty$ norm. $r_0=1$ and $K_1=[0,1]\times\{0\}$.
  • The third inequality is simply useless.
  • The second inequality is the one to be improved.

Existing literature

The improvement of the second inequality is related to the Jung's constant of a metric space $(X,d)$, given by $$ J(X) = \sup\left\{\frac{2\mathrm{rad}(A)}{\mathrm{diam}(A)} \bigg\vert A\subseteq X\right\} $$ where $$ \mathrm{rad}(A) = \inf_{x\in X}\sup_{y\in A} d(x,y), \qquad\qquad \mathrm{diam}(A) =\sup_{x,y\in A} d(x,y). $$ We have already noted that $1\leq J(X)\leq 2$. If $J(X)<2$, then we get $$ \mathrm{diam}(K_{n+1})\leq r_n\leq J(X)/2 \mathrm{diam}(K_n), $$ therefore $\mathrm{diam}(K_n) \leq \left(\frac{J(X)}2\right)^n \mathrm{diam}(K_0)$ converges geometrically to $0$.

This gives us another criterion for the uniqueness of the center: it is sufficient that $J(X)<2$. For example, $J(L^\infty)=1$ [Pichugov 1988] and we have the uniqueness of the center, even though $L^\infty$ is not uniformly convex.

See also this paper and this.

Failure in $L^1$

It is known that $J(L^1)=2$. I have found a nice example that proves this and that proves also that, unfortunately, the iterative procedure suggested above fails in $L^1$.

Consider in $L^1([0,1],\mathrm{leb}^1)$ the family $W=(w_n)_{n\in\mathbb N}$ of the wavelet functions $$ w_n(x) = \begin{cases} 1 & \frac i{2^n}\leq x<\frac{i+1}{2^n},\ \text{$i$ even}, \\ -1 & \frac i{2^n}\leq x<\frac{i+1}{2^n},\ \text{$i$ odd}, \end{cases} $$

It is immediate to compute $\lVert w_m-w_n\rVert_1=1$ for every $m\neq n$. Therefore $\mathrm{diam}(W)=1$. We want to show that also $\mathrm{rad}(W)=1$. Given a function $f\in L^1([0,1],\mathrm{leb}^1)$ and $\varepsilon>0$ we can find $n\in\mathbb N$ and a function $$ f_n = \sum_{i=0}^{2^n-1} a_i \chi_{\left[\frac i{2^n},\frac{i+1}{2^n}\right)} $$ such that $\lVert f-f_n\rVert_1\leq\varepsilon$. (This can be done in many different ways: by hand, or using the fact that $W$ is complete in $L^2([0,1],\mathrm{leb}^1)$). Then $$ \lVert f_n-w_{n+1}\rVert_1 = \sum_{i=0}^{2^n-1} \int_{\frac i{2^n}}^{\frac{i+1}{2^n}} \frac{|a_i-1|+|a_i+1|}2 dx \geq \sum_{i=0}^{2^n-1} \int_{\frac i{2^n}}^{\frac{i+1}{2^n}} 1\,dx = 1, $$ hence $\lVert f-w_{n+1}\rVert_1 \geq \lVert f-f_n\rVert_1 - \lVert f_n-w_{n+1}\rVert_1 > 1-\varepsilon$. This proves that a ball containing $W$ must have radius at least $1$.

Furthermore, if we take $K=\mathrm{co}(W)$, then the ball of radius $1$ covering $K$ can be centered at any point of $K$, which means that $H=K$ and the procedure described above doesn't converge to a single point.

share|improve this answer
    
Really cute! Of course this is nothing like the centroid, even in $\mathbb{R}^n$, for the reason pointed out in my second answer. –  Nik Weaver Oct 4 at 21:52
    
This seems relevant: encyclopediaofmath.org/index.php/Chebyshev_centre. It points out that uniqueness of the center is related to the uniform convexity in every direction, a condition (slightly) weaker than uniform convexity. I don't know if uniform convexity in every direction implies reflexivity, but certainly $L^1$ is not uniform convex in every direction. –  Federico Oct 7 at 17:21

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.