# A counter example for the set mean objective

Let $$\mathcal{P} = \{P_1, \cdots,P_n\}$$ be a family of finite point sets in $$\mathbb{R}^d$$, each having at most $$m$$ points. Consider the following objective function

\begin{align} cost(\mathcal{P},c) = \sum_{i\in[n]}\max_{p\in P_i}\Vert p-c\Vert^2 \end{align}

Let $$c^\star$$ be the point which minimizes the above objective function and the optimal cost is $$opt(\mathcal{P}) = cost(\mathcal{P},c^\star)$$.

For a point $$c\in\mathbb{R}^d$$ and $$i \in [n]$$, let $$p_i^{(c)}$$ be the point of $$P_i$$ farthest from $$c$$, i.,e. \begin{align*} \Vert p_i^{(c)} -c\Vert^2 = \max_{p\in P_i}\Vert p-c\Vert^2 \end{align*} Define $$c$$-mean to be the mean of these farthest points \begin{align*} \mu^{(c)} = \frac{1}{n}\sum_{i=1}^n p_i^{(c)} \end{align*}

So we have \begin{align*} cost_2(\mathcal{P},c) = \sum_{i=1}^n \Vert p_i^{(c)} -c\Vert^2 \end{align*} For ease of notation, let $$p_i^\star = p_i^{(c^\star)}$$ and $$\mu^\star = \mu^{(c^\star)}$$. So \begin{align*} opt_2(\mathcal{P}) = \sum_{i=1}^n \Vert p_i^\star - c^\star\Vert^2 \end{align*}

Note that if every set in $$\mathcal{P}$$ is singleton, then this is the well-known $$k$$-means objective and $$c^\star = \mu^\star$$.

It is easy to show the following, for any $$c\in \mathbb{R}^d$$ \begin{align} cost(\mathcal{P},c) \leq opt(\mathcal{P}) + n\Vert c - \mu^{(c)}\Vert^2 \end{align}

It follows that if there is a point $$c$$ such that $$c = \mu^{(c)}$$, then $$c$$ is an optimum center. This already helps to find the optimal solution in some simple scenarios, such as $$\mathcal{P} = \{P_1,P_2\}$$, where $$P_1=\{(1,1),(1,-1)\}$$ and $$P_2=\{(-1,1),(-1-1)\}$$. However it seems to me that the reverse direction may not hold: meaning for any optimal center $$c^\star$$, it may not be the case that $$c^\star = \mu^{(c^\star)}$$. So far I have not been able to come up with a counter example.

Does anyone have some idea as to finding a counter example.

P.s. Is this objective function already known?

• Yes, this objective function is known. Check Definition 1.1. of this paper. Yours is a special case for $k = 1$, $p = \infty$, and $q = 1$. Commented Dec 1, 2021 at 17:16
• @InuyashaYagami thanks for the reference. I have seen this paper but did not read it. Commented Dec 2, 2021 at 3:33

## 1 Answer

I have not verified the forward direction. However, here is a counterexample for reverse direction: $$\mathcal{P} = \{ P_1, P_2,P_3\}$$, where $$P_{1} = \{(-1,0)\}$$, $$P_{2} = \{(1,0)\}$$, and $$P_{3} = \{(0,1),(0,-1)\}$$. Here $$c^{*} = (0,0)$$. However, $$p_{1}^{*} = (-1,0)$$, $$p_{2}^{*} = (1,0)$$, and $$p_{3}^{*} = (0,1)$$ or $$(0,-1)$$ that have mean either $$(0,1/3)$$ or $$(0,-1/3)$$

• Why is origin is the optimal center? Commented Dec 2, 2021 at 15:17
• @SudiptaRoy Let $(a,b)$ be the center. Then, the cost is $(a-1)^2 + (a+1)^2 + 2b^2 + \max\{a^2+(b-1)^2, a^2+(b+1)^2\}$. Solve it. The function is minimized at the origin. Commented Dec 2, 2021 at 15:28
• After my reply, I was thinking about this approach. Thank you Commented Dec 2, 2021 at 15:31