Let $(C_i)_{i=1}^m$ be nonempty closed convex subsets of a real Hilbert space $\mathcal{H}$. I am interested in proving (or finding a counterexample to) the following conjecture on the $m$-fold product space $H=\mathcal{H}\times\cdots\times\mathcal{H}$ equipped with the inner product $\langle x\,|\,y\rangle=\sum_{i=1}^m\omega_i\langle x_i\,|\,y_i\rangle$ (for convex weights $\{\omega_i\}_{i=1}^m\subset]0,1]$ satisfying $\sum_{i=1}^m\omega_i=1$). For convenience, set $D=\{x\in H\,|\,(\forall i,j\in\{1,\ldots,m\})\quad x_i=x_j\}$ (sometimes called the diagonal subspace).

The conjecture is the following inequality of distance functions

$$(\forall x\in \times_{i=1}^m C_i)\quad \textrm{dist}_{\bigcap_{i=1}^mC_i}\left(\sum_{i=1}^m\omega_i x_i\right)\leq\textrm{dist}_{D}(x).$$

Based on the geometry, it looks like as soon as this inequality is violated, it necessitates that at least one component of $x$ is no longer in $C_i$. However, I have not been able to prove this by contradition yet.

Further comments:

These two distances form the the smaller legs of a right triangle, with endpoints $x$, $P_Dx$, and $P_{D\cap\times_{i=1}^m(\bigcap_{j=1}^mC_j)}x$. It is a right triangle because the leg $x-P_Dx$ (whose magnitude is $\textrm{dist}_D(x)$) is orthogonal to $P_Dx-P_{D\cap\times_{i=1}^m(\bigcap_{j=1}^mC_j)}x$ (whose magnitude is $\textrm{dist}_{\bigcap_{i=1}^mC_i}\left(\sum_{i=1}^m\omega_i x_i\right)$).

Here is an (updated) example graph -- the conjecture is saying that, as long as $x\in \times_{i=1}^m C_i$, the length of the segment between $x$ and the projection $P_Dx$ is always larger than the length of the segment connecting $P_Dx$ to $P_{(C_1\cap C_2)\times(C_1\cap C_2)}(P_Dx)$.

It may be convenient to note that the projection onto $D$ is given by the average repeated in every component, i.e., $P_Dx=(\sum_{i=1}^m\omega_i x_i)_{j\in\{1,\ldots,m\}}$, so $\textrm{dist}^2_D(x)=\sum_{i=1}^m\omega_i\|x_i-\sum_{j=1}^m\omega_jx_j\|^2$. Even if we could prove (or disprove) this for $\omega_i\equiv 1/m$, I would be happy.


1 Answer 1


The conjecture is false, even in $2$D:

Consider two skew lines, $\omega_1=\omega_2=1/2$.

$$C_1=\{(x,y)\in\mathbb{R}^2\,|\,y=0.1x-1\}\quad C_2=\{(x,y)\in\mathbb{R}^2\,|\,y=-0.1+1\}.$$

Then $x=((0,1),(0,-1))\in C_1\times C_2$. However, $\textrm{dist}_{D}(x)=\|P_Dx-x\|=2$ while $\textrm{dist}_{C_1\cap C_2}(\frac{x_1+x_2}{2})=10$.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .