2
$\begingroup$

I'm trying to solve the following minimization problem, and I'm sure there must be a standard methodology that I could use, but so far I couldn't find any good references. Please let me know if you have anything in mind that could help or any references that you think would be useful for tackling this problem.

Suppose you are given $K$ points, $p_i \in R^n$, for $i \in \{1,\ldots,K\}$. Assume also that we are given $K$ constants $\delta_i$, for $i \in \{1,\ldots,K\}$. We want to find the vector $x$ that minimizes:

$\min_{x \in R^n} \sum_{i=1,\ldots,K} || x - p_i ||^2$

subject the following $K$ constraints:

$\frac{ || x - p_i ||^2 } { \sum_{j=1,\ldots,K} ||x - p_j||^2} = \delta_i$

for all $i \in {1,\ldots,K}$.

Any help is extremely welcome!

Bruno

edit: also, we know that $\sum_{i=1,\ldots,K} \delta_i = 1$.

  • 0
    @Christian: suppose K=4 points in a 2D space; the points A, B, C and D are located at the vertices of a square whose side's length is 2, centered at the origin. A=(-1,-1), B=(-1,+1), C=(+1, -1), D=(+1,+1). Suppose all $delta$'s are equal to $\frac{\sqrt(2)}{4}$. In this case, there exists only one solution, which is X=(0,0).2011-05-23

2 Answers 2

1

You can try using Lagrange multiplier method - see wikipedia.

1

Yes, this works. If $n \leq K-2,$ you have no guarantee of any legal solution, even when the $\delta_i$ sum to 1, as required. It may be that the sample points, your $v_j$ and $Y,$ were in a Euclidean space of much lower dimension, however, that does not guarantee you can repeat that piece of luck if the new $n$ in $\mathbf R^n$ is too small.

If $n = K -1,$ there should be a single feasible point, "near" the simplex with the $K$ points as vertices. No need (or ability) to minimize anything. Actually, unless the $\delta$'s are all equal, it appears there is a second feasible point far away. If all angles in the simplex are acute, there is a feasible point in its interior.

So, my advice is, figure out how to find a feasible point when $n=K-1.$ If circumstance forces $n \geq K,$ rotate so the hyperplane containing all the $p_i$ becomes the hyperplane $x_1, x_2, \ldots, x_{K-1}, 0,0,\ldots,0,$ solve the problem there, then rotate back.

Meanwhile, I see nothing wrong with a numerical method for finding the single feasible point near the simplex when $n=K-1.$ Easier than finding the intersection of a large number of spheres and planes. Note that, when $n=K,$ the full set of all feasible points is either a straight line (if all $\delta_i$ are equal) or, in fact, an actual circle. Go figure. In either case, meeting the hyperplane that contains the $p_i$'s orthogonally.

For that matter, your easiest program is just to solve the problem in the original $v_i, Y$ location, that is, a numerical method that finds the point $Z$ near the $v_i$ simplex with the correct $\delta$'s. Then you can just map $Z$ along with the $v_i.$

  • 0
    My email can be found by searching with my last name at $ $ http://www.ams.org/cml/ $ $ You seem to have a way to go in finding the right mathematical description of this.2011-05-22