The Minimum Euclidean-Norm Point in a Convex Polytope: Wolfe's Combinatorial Algorithm is Exponential
From MaRDI portal
Publication:5216797
DOI10.1137/18M1221072zbMath1453.90113OpenAlexW3008414709WikidataQ115525586 ScholiaQ115525586MaRDI QIDQ5216797
Jamie Haddock, Luis Rademacher, Jesús A. De Loera
Publication date: 20 February 2020
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/18m1221072
linear programminglower boundsconvex quadratic optimizationWolfe's methodstrongly polynomial-time algorithms
Convex programming (90C25) Abstract computational complexity for mathematical programming problems (90C60) Quadratic programming (90C20)
Related Items
An update-and-stabilize framework for the minimum-norm-point problem, The smoothed complexity of Frank-Wolfe methods via conditioning of random matrices and polytopes, Decreasing minimization on base-polyhedra: relation between discrete and continuous cases
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On the closest point to the origin in transportation polytopes
- A note on the complexity of \(L _{p }\) minimization
- Minimum norm problems over transportation polytopes
- The ellipsoid method and its consequences in combinatorial optimization
- Geometric algorithms and combinatorial optimization
- Pivot rules for linear programming: A survey on recent theoretical developments
- Mathematical problems for the next century
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- Analysis of backtrack algorithms for listing all vertices and all faces of a convex polyhedron.
- On the von Neumann and Frank--Wolfe Algorithms with Away Steps
- A Strongly Polynomial Algorithm for a Class of Minimum-Cost Flow Problems with Separable Convex Objectives
- Lexicographically Optimal Base of a Polymatroid with Respect to a Weight Vector
- The polynomial solvability of convex quadratic programming
- Finding the nearest point in A polytope
- Colourful Linear Programming and its Relatives
- The Matching Polytope has Exponential Extension Complexity
- The minimum Euclidean-norm point in a convex polytope: Wolfe's combinatorial algorithm is exponential
- Learning with Submodular Functions: A Convex Optimization Perspective
- The convolution of finite systems of linear inequalities
- An Iterative Procedure for Computing the Minimum of a Quadratic Form on a Convex Set
