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.

  • 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 Sep 6 '16 at 1:37
  • 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 Sep 6 '16 at 17:42

Your Answer

 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.