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.

  • $\begingroup$ Have you tried using Lagrange multipliers? It seems that it should work if $D$ is constant and the points are in general position. $\endgroup$ – Yuval Filmus Sep 6 '16 at 1:37
  • $\begingroup$ 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. $\endgroup$ – Minwei Ye Sep 6 '16 at 17:42

Your Answer

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

Browse other questions tagged or ask your own question.