3
$\begingroup$

Problem: Let $S$ be a finite set of vectors. Let $C$ be their convex hull. Compute $\operatorname{argmin}_{x \in C} \|x\|$.

Reference 1 gives an algorithm for this problem that is finite-time (Section 2). However, its worst-case time complexity is not given.

Reference 2 gives another algorithm for this problem, but it is not finite-time (Theorem 2).

Is there a strongly polynomial time algorithm for this problem?

References:

  1. Algorithm for a least-distance programming problem. Philip Wolfe. Mathematical Programming Studies. Volume 1, March 1974, Pages 190-205.

  2. An algorithm for finding the shortest element of a polyhedral set with application to Lagrangian duality. Mokhtar S Bazaraa, Jamie J Goode, Ronald L Rardin. Journal of Mathematical Analysis and Applications. Volume 65, Issue 2, September 1978, Pages 278-288.

$\endgroup$
2
  • 1
    $\begingroup$ Is there a strongly poly-time reduction from general LP to this problem? (This would mean a strongly poly-time algorithm is not known, right?) Given an arbitrary feasibility LP $Ax=b; x \ge 0$, reduce it to $Ax = b; x \ge 0, \sum_i x_i \le N$ for some very large $N$, then (by adding a slack variable and scaling) put in form $Ax = b; x \ge 0; \sum_i x_i = 1$, then reduce this to $A' x = 0; x \ge 0; \sum_i x_i = 1$ for appropriate $A$. The latter feasibility question is just whether the convex hull of the columns of $A'$ contains the origin, i.e., whether the answer to your question is zero. $\endgroup$
    – Neal Young
    Oct 21, 2022 at 1:49
  • $\begingroup$ dl.acm.org/doi/10.1145/3188745.3188820 shows that general LP reduces in strongly poly time to minimum norm point in a simplex. Also has other related results. You can also see slides of a talk simons.berkeley.edu/sites/default/files/docs/9999/… $\endgroup$ Oct 21, 2022 at 19:00

1 Answer 1

6
$\begingroup$

It is known via a paper of De Loera, Haddock and Rademacher that a strongly polynomial time algorithm for finding a minimum norm point in a simplex implies a strongly polynomial time algorithm for general LP. We do not know whether LP has a strongly poly time algorithm - this is a fundamental open problem in optimization.

$\endgroup$
2

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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