A recursive algorithm for finding the minimum norm point in a polytope and a pair of closest points in two polytopes

DOI10.1007/BF01582149zbMath0791.90046OpenAlexW2094911742MaRDI QIDQ1315417

Yoshitsugu Yamamoto, Kazuyuki Sekitani

Publication date: 27 March 1994

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01582149

zbMATH Keywords

recursive algorithmsimplicial decompositionconvex quadratic programminimum Euclidean distance pair of pointsminimum Euclidean norm point

Mathematics Subject Classification ID

Convex programming (90C25) (n)-dimensional polytopes (52B11) Quadratic programming (90C20) Computational methods for problems pertaining to operations research and mathematical programming (90-08)

Related Items (13)

An algorithm for finding the minimum-norm point in the intersection of a convex polyhedron and a hyperplane ⋮ Zonotopes and the LP-Newton method ⋮ An efficient algorithm for finding the minimum norm point in the convex hull of a finite point set in the plane ⋮ Finding the projection on a polytope: An iterative method ⋮ Error bounds for solutions of linear equations and inequalities ⋮ Hausdorff matching and Lipschitz optimization ⋮ Unnamed Item ⋮ A simple projection algorithm for linear programming problems ⋮ A recursive algorithm for finding the minimum covering sphere of a polytope and the minimum covering concentric spheres of several polytopes ⋮ Efficient computation of the Hausdorff distance between polytopes by exterior random covering ⋮ The distance between convex sets with Minkowski sum structure: application to collision detection ⋮ A vertex algorithm for collision detection ⋮ An iterative algorithm for finding a nearest pair of points in two convex subsets of \(\mathbb{R}^n\)

Cites Work

• Error bounds for strongly convex programs and (super)linearly convergent iterative schemes for the least 2-norm solution of linear programs
• A DUAL ALGORITHM FOR FINDING THE MINIMUM-NORM POINT IN A POLYTOPE
• Dual gauge programs, with applications to quadratic programming and the minimum-norm problem
• Finding the nearest point in A polytope
• Error bounds for monotone linear complementarity problems
• A DUAL ALGORITHM FOR FINDING A NEAREST PAIR OF POINTS IN TWO POLYTOPES
• A Tight Upper Bound on the Rate of Convergence of Frank-Wolfe Algorithm

This page was built for publication: A recursive algorithm for finding the minimum norm point in a polytope and a pair of closest points in two polytopes