4
$\begingroup$

I am doing research on problems of location of a public facility on a network which lead me to the following question.

  • Is there an interesting way to characterize the class of functions $f : \mathbb{R}^{n+1} \rightarrow \mathbb{R}$ such that for every $p_n \in \mathbb{R}^n$, the median of the coordinates of $p_n$, $m(p_n) \in {\arg\min}_{c\in \mathbb{R}} ~~f(|p^n - c|)$, where $|p_n -c| = (|p_1 - c|, \dots, |p_n - c|)$.

  • To avoid technical complications in the definition of the median, let's assume that $n$ is odd so that the median is naturally defined as the coordinate $p_i$ of $p_n$ ($i\in \{1,\dots,n\}$) such that $\#\{ p_j $ with $ j\in \{1,\dots,n\} : p_j \leq p_i\} = \frac{n +1 }{2}$ and $\#\{ p_j $ with $ j\in \{1,\dots,n\} : p_j \geq p_i\} = \frac{n +1 }{2}$, where $\#$ denotes the cardinality of the following set.

If a characterization is too hard to obtain, a list of salient properties such $f$'s must satisfy would also be of great interest to me.

What I have got so far

Some examples

  • As is known in the literature on public facility location (and not hard to obtain), the function $S(|p^n - c|) = \sum_{i=1}^{n} |p_i - c|$ satisfies the above property.
  • So does any affine transformation monotonic transformation of $S$.
  • Another class of functions trivially satisfy the property : those functions which are always equal to zero when $|p_i - c|=0$ for some $i$, hence when $c = m(p_n)$. Examples are $P(|p^n - c|) = \Pi_{i=1}^{n} |p_i - c|$ and $M(|p^n - c|) = \min_{p_i} |p_i - c|$.

Clarification follow the answer from user96614

The approach proposed in user96614's answer is the one I had been investigating. I prevented myself from thinking in differentiable terms, but I was also considering small variation around the median. I should have added it my original post, sorry. My actual question (maybe hard to guess from my post, I admit) revolved around finding an alternative characterization of such functions. So I was looking for a (ideally exhaustive) set of easy to check properties which would be necessary for the function to satisfy the property (e.g. convexity, subbaditivity,...)

An intermediary question

  • I have tried to determined whether it is possible for a function which is not an affine transformation monotonic transformation of $S$ or a "trivial" function which equals zero as soon as $|p_i - c|=0$ for some $i\in \{1,\dots,n\}$ to satisfy the above property. My intuition is that it is (close to be?) the case. But neither have I been able to find an example, nor to prove it was not possible to find such example.
$\endgroup$
  • $\begingroup$ What is an element of $p_n$? Do you mean coordinate? $\endgroup$ – dfeuer Oct 25 '13 at 23:27
  • $\begingroup$ @ dfeuer: yes, I mean a coordinate. I'll update the question to make it clearer. $\endgroup$ – Martin Van der Linden Oct 26 '13 at 16:53
4
+50
$\begingroup$

If $n$ is even, $f$ has to be the sum $\sum_{i=1}^{n}{|p_i-c|}$ or a monotonically increasing function of this sum.

Your requirement: $f(x_1,...,x_n)\le f(y_1,...,y_n)$ whenever $x_i=|p_i-c|$, $y_i=|p_i-d|$, and $c$ is median of $p$, written as $c=m(p)$. The vector $x$ represents distances from median location and vector $y$ represents distances from another location.

Note that $x_i$ and $y_i$ cannot be arbitrary vectors. Suppose $\delta=|c-d|$. If $\delta<\mathrm{min}_{i\neq j}{\{x_i-x_j\}}$, then $x_i=y_i+\delta$ for at least $\lceil n/2 \rceil$ coordinates and $x_i=y_i-\delta$ for remaining coordinates. If $\delta>\mathrm{min}_{i\neq j}{\{x_i-x_j\}}$, then $x_i=y_i+\delta$ for at least $\lceil n/2 \rceil$ coordinates and $x_i \ge y_i-\delta$ for remaining coordinates.

So $f$ has to be a function which increases when all its arguments are changed by a small number $\delta>0$ and the number of arguments increased exceeds the number of arguments decreased. In the following, I assume $f$ is differentiable in all arguments.

Consider $n$ even. At $x$, all first partial derivatives of $f$ must be equal: $\frac{\partial f}{\partial x_i} = \frac{\partial f}{\partial x_j} \forall i,j$ otherwise we could increase $n/2$ arguments with lowest partial derivatives and decrease the remaining arguments and this will lead to a lower value of $f.$ Moreover, $x$ can be any set of coordinates (median doesn't have to be one of the points). So all partial derivatives of $f$ are equal everywhere in domain of $f$. It is easy to show then that increasing $x_i$ and decreasing $x_j$ by the same amount leaves $f$ unchanged. So $f$ depends on $x_i+x_j$ rather than $x_i$ and $x_j$ separately. Since, $i$ and $j$ are arbitrary, $f$ is a weakly increasing function of $\sum_{i=1}^{n}x_i$. Note that $f$ doesn't have to be an affine function of the sum.

If $n$ is odd, $k \ge 1$ coordinates must be zero in $x$. Then, a small change from $x$ to $y$ increases these $k$ coordinates by $\delta$. Of the remaining coordinates, some (at least $l=\frac{n+1}{2}-k$ and at most $\frac{n-1}{2}$) will increase by $\delta$ while the remaining will decrease by $\delta$. Since more than half of the coordinates increase, function $f$ will increase if all partial derivatives are equal and positive. That is, $f$ can again be an increasing function of $\sum_{i=1}^{n}x_i$. However, this is not the only possibility. There may be other solutions which satisfy the following necessary condition:

If $k$ coordinates of $x$ are $0$, reorder the coordinates and accordingly the arguments of $f$ so that $x_i=0$ for $1 \le i \le k$, $x_i>0$ for $k < i \le n$ and $\frac{\partial f}{\partial x_i} \le \frac{\partial f}{\partial x_j} \forall k<i<j$. Then, $\sum_{i=1}^{k+l}{\frac{\partial f}{\partial x_i}} \ge \sum_{i=k+l+1}^{n}{\frac{\partial f}{\partial x_i}}$.

The above necessary condition ensures that $f$ has a local minimum at $x$ but need not guarantee a global minimum. The functions $\prod_{i=1}^{n}{(x_i)}$ and $\min_{1\le i \le n}{(x_i)}$ satisfy the necessary condition.

Finally, note that the minimum and product functions do not work for the case of even $n$. For example, try $p=(1,3,11,13,15,39)$.

The problem for odd $n$ can be characterized as follows. Define an ordered pair of vectors $(x,y)$ as comparable if $x$ represents distances from median in a network and $y$ represents distances from another point in the same network. Let $\Omega$ represent the set of comparable points. Then, $f$ satisfies

Condition A: $f(x) \le f(y) \quad \forall (x,y) \in \Omega$.

While there are no direct restrictions on relative values of $f$ for vectors $x$ and $y$ if $(x,y) \not\in \Omega$, repeated application of Condition A may yield such restrictions. For example, if $(x,z) \in \Omega$ and $(z,y) \in \Omega$ then $f(x) \le f(y)$. Characterizing desired functions requires understanding the structure of $\Omega$.

$(x,y) \in \Omega$ if and only if at least one coordinate of $x$ is zero and there exists $\delta \in \mathbb{R}$ such that there are $\lceil n \rceil$ values of coordinate $i$ such that $y_i=|x_i+\delta|$ and $\lceil n \rceil$ values of coordinate $i$ such that $y_i=|x_i-\delta|$. The trivial solutions you mentioned equate $f$ to its lowest value at all $x$ with a coordinate of $0$. But this means that if $(x,y) \in \Omega$ for some $y$, then $f(x) \le f(z) \forall z$ even when $(x,z) \not\in \Omega$. Increasing functions of sum of coordinates exploit the property that if $(x,y) \in \Omega$ then $\sum x_i < \sum y_i$. However, note that $\sum x_i < \sum y_i \not\Rightarrow (x,y) \in \Omega$.

One approach towards finding other functions meeting Condition A would be to characterize the set of all pairs $(x,y)$ of median-distance vectors (at least one component of each of $x$ and $y$ is zero) at which the realtive values of $f$ are restricted. That is, all pairs $(x,y)$ such that there exist $x=z_0,z_1,z_2,...,z_{m-1},z_m=y$ with $(z_{i-1},z_i) \in \Omega$. This step seems difficult. After this step, choose function values at all median-distance vectors satisfying these restrictions. Finally, fill in values at other vectors $y$ that are not distances from medians to exceed $f(x)$ for all $x$ such that $(x,y) \in \Omega$.

Since only relative function values are restricted only for $(x,y) \in \Omega$, it seems unlikely that $f$ can be characterized by properties which depend solely on how values of $f$ change in a neighborhood.

$\endgroup$
  • $\begingroup$ You may want to add "if the function is differentiable" of "if the first partial derivatives exist" (whichever is necessary), as that is not assumed in the question. $\endgroup$ – dfeuer Oct 29 '13 at 21:21
  • $\begingroup$ @dfeuer Thanks. You are right. I took differentiability for granted which need not be the case. I think it is possible to present these arguments without assuming differentiability allowing for finitely many points of nondifferentiability or discountinuity. But I can't yet think of how to rule out arbitrary nondifferentiable functions. $\endgroup$ – user96614 Oct 29 '13 at 22:04
  • $\begingroup$ @ user96614 : Thanks for your answer. I will review it as soon as I can. However, as suggested by dfeuer, I was aiming for more general results, not assuming differentiability. Any additional thoughts without the differentiability assumption would be much appreciated. $\endgroup$ – Martin Van der Linden Oct 29 '13 at 22:09
  • $\begingroup$ @MartinVanderLinden Thanks. I will think about that. It seems your interest in the problem is in economic application. Usually economic plausibility considerations can further limit the space of functions that are "interesting". $\endgroup$ – user96614 Oct 29 '13 at 22:22
  • 1
    $\begingroup$ @MartinVanderLinden Thanks for the clarification. I think you should further sharpen your question to get more helpful responses. The requirement of a minimum at the median location only imposes restriction on the ordering of the function's values, not on the values themselves. The set of such functions is closed with respect to monotonically increasing transformations but these transformations do not preserve properties like convexity, subadditivity, etc. So any property that cannot be deduced simply from ordering of function values may not be relevant in characterizing the functions. $\endgroup$ – user96614 Oct 30 '13 at 4:27
0
$\begingroup$

The conditions on $f$ are a collection of inequalities $f(a) \geq f(b)$ with $a,b \in R^n$ and $b$ of the form $(|x_1-m|,|x_2-m|,\dots,|x_n-m|)$ where $m$ is the median of the $x_i$. All such $b$ are contained in a closed ($n-1$)-dimensional subset $S$ in $R^n$ (take $S$ to be non-negative vectors with at least one component zero).

Therefore, any continuous function that is $0$ on $S$ and positive elsewhere, is a solution. This however is the 'trivial' form in the question.

Below is an earlier solution disregarding the absolute value signs, which is an easier but closely related problem that I thought was being asked.


The condition on $f$ is that it be minimized, with respect to variations that shift all coordinates equally, on a known (closed, proper) subset of $R^n$. There is a large and infinite-dimensional supply of such functions for any closed proper subset, such as monotone transformations of distance to the subset, but going well beyond that (the graph of the function does not have to look like a cone over the subset). Our subset happens to be the vectors with median $0$.

Since the median is a measure of location, it is natural to re-coordinatize $n$-tuples $(x_1, \dots, x_n) \in R^n$ by their median and differences to the median, $(m; x_1 - M, x_2 - m, \dots x_n - m)$. The differences are $n$ numbers but depend only on the $n-1$ dimensional set of differences $x_i - x_j$, so the dimensions of the two spaces are the same, $n$ and $1 + (n-1)$. The coordinate transformation can be inverted by adding the median to the last $n$ components, showing that this is an equivalent way of writing $n$-tuples. This is nothing more than the median analogue of recentering data around the mean.

In this median-centered coordinate system, the question is about

continuous functions $f$ such that $f(m,d_1,d_2,\dots,d_n) \geq f(0,d_1,\dots,d_n)$.

The function only has to be defined when the median of the $d_i$ is $0$, but examples based on a formula might also be defined for all values of $d_i$. For instance, $f = g(d_1,\dots,d_n) + H(m)$ with $g$ arbitrary and $H$ minimized at $m=0$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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