Abstract
For a given pair of finite point setsP andQ in some Euclidean space we consider two problems: Problem 1 of finding the minimum Euclidean norm point in the convex hull ofP and Problem 2 of finding a minimum Euclidean distance pair of points in the convex hulls ofP andQ. We propose a finite recursive algorithm for these problems. The algorithm is not based on the simplicial decomposition of convex sets and does not require to solve systems of linear equations.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
M.D. Canon and C.D. Cullum, “The determination of optimum separating hyperplanes I. A finite step procedure,” RC 2023, IBM Watson Research Center (Yorktown Heights, NY, 1968).
M.D. Canon and C.D. Cullum, “A tight upper bound on the rate of convergence of the Frank—Wolfe algorithm,”SIAM Journal on Control 6 (1968) 509–516.
M. Frank and P. Wolfe, “An algorithm for quadratic programming,”Naval Research Logistics Quarterly 3 (1956) 95–110.
R.M. Freund, “Dual gauge programs, with applications to quadratic programming and the minimumnorm problem,”Mathematical Programming 38 (1987) 47–67.
S. Fujishige and P. Zhan, “A dual algorithm for finding the minimum-norm point in a polytope,”Journal of the Operations Research Society of Japan 33 (1990) 188–195.
S. Fujishige and P. Zhan, “A dual algorithm for finding a nearest pair of points in two polytopes,” DP No. 470, Institute of Socio-Economic Planning, University of Tsukuba (Tsukuba, 1991).
O.L. Mangasarian and R. De Leone, “Error bounds for strongly convex program and (super)linearly convergent iterative schemes for the least 2-norm solution of linear programs,”Applied Mathematics and Optimization 17 (1988) 1–14.
O.L. Mangasarian and T.-H. Shiau, “Error bounds for monotone linear complementarity problems,”Mathematical Programming 36 (1986) 81–89.
P. Wolfe, “Finding the nearest point in a polytope,”Mathematical Programming 11 (1976) 128–149.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Sekitani, K., Yamamoto, Y. A recursive algorithm for finding the minimum norm point in a polytope and a pair of closest points in two polytopes. Mathematical Programming 61, 233–249 (1993). https://doi.org/10.1007/BF01582149
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01582149