# Strongly polynomial time algorithm for shortest convex combination

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.

• 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. Oct 21, 2022 at 1:49
• 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/… Oct 21, 2022 at 19:00