The minimum Euclidean-norm point in a convex polytope: Wolfe's combinatorial algorithm is exponential
The minimum Euclidean-norm point in a convex polytope: Wolfe's combinatorial algorithm is exponential
The complexity of Philip Wolfe's method for the minimum Euclidean-norm point problem over a convex polytope has remained unknown since he proposed the method in 1974. The method is important because it is used as a subroutine for one of the most practical algorithms for submodular function minimization. We present the first example that Wolfe's method takes exponential time. Additionally, we improve previous results to show that linear programming reduces in strongly-polynomial time to the minimum norm point problem over a simplex.
- University of California System United States
- University of California, Davis United States
- University of California, San Francisco United States
- Mathematical Sciences Research Institute United States
- THE OHIO STATE UNIVERSITY United States
FOS: Computer and information sciences, Convex programming, Numerical and computational mathematics, Quadratic programming, Mathematical Sciences, Computation Theory & Mathematics, strongly polynomial-time algorithms, lower bounds, Mathematics - Metric Geometry, Computer Science - Data Structures and Algorithms, FOS: Mathematics, Data Structures and Algorithms (cs.DS), Abstract computational complexity for mathematical programming problems, Mathematics - Optimization and Control, Theory of computation, Numerical and Computational Mathematics, Applied Mathematics, convex quadratic optimization, Wolfe's method, strongly polynomial time algorithms, Computation Theory and Mathematics, linear programming, Metric Geometry (math.MG), Applied mathematics, Pure Mathematics, Optimization and Control (math.OC), 90C20, 90C27, 90C60
FOS: Computer and information sciences, Convex programming, Numerical and computational mathematics, Quadratic programming, Mathematical Sciences, Computation Theory & Mathematics, strongly polynomial-time algorithms, lower bounds, Mathematics - Metric Geometry, Computer Science - Data Structures and Algorithms, FOS: Mathematics, Data Structures and Algorithms (cs.DS), Abstract computational complexity for mathematical programming problems, Mathematics - Optimization and Control, Theory of computation, Numerical and Computational Mathematics, Applied Mathematics, convex quadratic optimization, Wolfe's method, strongly polynomial time algorithms, Computation Theory and Mathematics, linear programming, Metric Geometry (math.MG), Applied mathematics, Pure Mathematics, Optimization and Control (math.OC), 90C20, 90C27, 90C60
selected citations These citations are derived from selected sources.This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).4 popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.Top 10% influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).Average impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.Average
Citations provided by BIP!Popularity provided by BIP!