<p>Given $n$ <em>fixed</em> points $\{p_i\}_{i=1}^n$ in $D$-dimensional Euclidean space $\mathbb{R}^D$, consider the following optimization problem:</p>

<p>$$
\begin{align}
  \text{mininize} \ \ \ &amp;\prod_{i=1}^n \lVert p-p_i\rVert\\
  \text{subject to: } &amp; \lVert p-p_i\rVert \ge 1, \text{for } i=1,\cdots,n
\end{align}
$$</p>

<p>The constraint is to make sure that trivial solution $p=p_i$ won't occur.  </p>

<p><strong>Q.</strong> Has there been any literature discussing such problem already?</p>

<p>Thanks in advance.</p>

CC BY-SA 3.0
2016-09-06T17:42:18.053Z
Yes, $D$ is fixed. And mathematically speaking it does solve the problem. But when $D$ is large, finding all stationary points in the auxiliary function of Lagrange multipliers involves  solving $D$ homogeneous polynomials in $(D+1)$ variables, of degrees $(2n-1)$, which is a hard question itself.
Minwei Ye
CC BY-SA 3.0
2016-09-06T01:37:13.917Z
Have you tried using Lagrange multipliers? It seems that it should work if $D$ is constant and the points are in general position.
Yuval Filmus
<reference-request><optimization><cg.comp-geom>
Minimize the product of distances from n fixed points
Minwei Ye
# Minimize the product of distances from n fixed points

(Asked by: username_0 on 2016-09-05)

Given $n$ *fixed* points $\{p\_i\}\_{i=1}^n$ in $D$-dimensional Euclidean space $\mathbb{R}^D$, consider the following optimization problem:

$$
\begin{align}
\text{mininize} \ \ \ &\prod\_{i=1}^n \lVert p-p\_i\rVert\\
\text{subject to: } & \lVert p-p\_i\rVert \ge 1, \text{for } i=1,\cdots,n
\end{align}
$$

The constraint is to make sure that trivial solution $p=p\_i$ won't occur.

**Q.** Has there been any literature discussing such problem already?

Thanks in advance.

**Tags:** reference-request, optimization, cg.comp-geom

> **Comments:**
> **username_1**: Have you tried using Lagrange multipliers? It seems that it should work if $D$ is constant and the points are in general position.  
> **username_0**: Yes, $D$ is fixed. And mathematically speaking it does solve the problem. But when $D$ is large, finding all stationary points in the auxiliary function of Lagrange multipliers involves  solving $D$ homogeneous polynomials in $(D+1)$ variables, of degrees $(2n-1)$, which is a hard question itself.  

---

## 0 answers

