<p>It is known via a <a href="https://dl.acm.org/doi/10.1145/3188745.3188820" rel="noreferrer">paper</a> 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.</p>

CC BY-SA 4.0
2022-10-22T17:37:51.833Z
Some of Vavasis's papers may also be relevant. First is showing that quadratic programming is in NP. https://www.sciencedirect.com/science/article/abs/pii/002001909090100C Second is on weakly polynomial time algorithms for finding some local optima. https://www.worldscientific.com/doi/epdf/10.1142/9789814354363_0022
Chandra Chekuri
CC BY-SA 4.0
2022-10-22T23:03:57.057Z
In the other direction, does this also reduce to LP?
user76284
CC BY-SA 4.0
2022-10-21T23:49:05.213Z
2022-10-21T23:49:05.213Z
Chandra Chekuri
<p>Problem: Let <span class="math-container">$S$</span> be a finite set of vectors. Let <span class="math-container">$C$</span> be their <a href="https://en.wikipedia.org/wiki/Convex_hull" rel="nofollow noreferrer">convex hull</a>. Compute <span class="math-container">$\operatorname{argmin}_{x \in C} \|x\|$</span>.</p>
<p>Reference 1 gives an algorithm for this problem that is finite-time (Section 2). However, its worst-case time complexity is not given.</p>
<p>Reference 2 gives another algorithm for this problem, but it is not finite-time (Theorem 2).</p>
<p>Is there a <a href="https://en.wikipedia.org/wiki/Time_complexity#Strongly_and_weakly_polynomial_time" rel="nofollow noreferrer">strongly polynomial time</a> algorithm for this problem?</p>
<p>References:</p>
<ol>
<li><p><em><a href="https://link.springer.com/chapter/10.1007/BFb0121249" rel="nofollow noreferrer">Algorithm for a least-distance programming problem</a></em>. Philip Wolfe. Mathematical Programming Studies. Volume 1, March 1974, Pages 190-205.</p>
</li>
<li><p><em><a href="https://www.sciencedirect.com/science/article/pii/0022247X78901804" rel="nofollow noreferrer">An algorithm for finding the shortest element of a polyhedral set with application to Lagrangian duality</a></em>. Mokhtar S Bazaraa, Jamie J Goode, Ronald L Rardin. Journal of Mathematical Analysis and Applications. Volume 65, Issue 2, September 1978, Pages 278-288.</p>
</li>
</ol>

CC BY-SA 4.0
2022-10-21T01:49:52.193Z
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.
Neal Young
CC BY-SA 4.0
2022-10-21T19:00:49.963Z
https://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 https://simons.berkeley.edu/sites/default/files/docs/9999/presentation-3.pdf
Chandra Chekuri
<time-complexity><linear-algebra><convex-optimization><convex-geometry><convex-hull>
Strongly polynomial time algorithm for shortest convex combination
user76284
# Strongly polynomial time algorithm for shortest convex combination

(Asked by: username_0 on 2022-10-20)

Problem: Let $S$ be a finite set of vectors. Let $C$ be their [convex hull](https://en.wikipedia.org/wiki/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](https://en.wikipedia.org/wiki/Time_complexity#Strongly_and_weakly_polynomial_time) algorithm for this problem?

References:

1. *[Algorithm for a least-distance programming problem](https://link.springer.com/chapter/10.1007/BFb0121249)*. 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](https://www.sciencedirect.com/science/article/pii/0022247X78901804)*. Mokhtar S Bazaraa, Jamie J Goode, Ronald L Rardin. Journal of Mathematical Analysis and Applications. Volume 65, Issue 2, September 1978, Pages 278-288.

**Tags:** time-complexity, linear-algebra, convex-optimization, convex-geometry, convex-hull
> **Comments:**
> **username_1**: 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.  
> **username_2**: https://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 https://simons.berkeley.edu/sites/default/files/docs/9999/presentation-3.pdf  

---

## 1 answers

### Answer by username_2 on 2022-10-21. Score: 6 | Accepted answer

It is known via a [paper](https://dl.acm.org/doi/10.1145/3188745.3188820) 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.

> **Comments:**
> **username_2**: Some of Vavasis's papers may also be relevant. First is showing that quadratic programming is in NP. https://www.sciencedirect.com/science/article/abs/pii/002001909090100C Second is on weakly polynomial time algorithms for finding some local optima. https://www.worldscientific.com/doi/epdf/10.1142/9789814354363_0022  
> **username_0**: In the other direction, does this also reduce to LP?  

---

