Article ID: | iaor1994702 |
Country: | United Kingdom |
Volume: | 20 |
Issue: | 4 |
Start Page Number: | 363 |
End Page Number: | 370 |
Publication Date: | May 1993 |
Journal: | Computers and Operations Research |
Authors: | Sherali Hanif D., Choi Gyunghyun |
Keywords: | computational analysis |
This paper presents a specialized algorithm for finding a point in the convex hull of a given finite collection of discrete points that is closest to the origin. Such problems find applications in nondifferentiable optimization, statistics, approximation theory, and linear programming. The algorithm presented is easy to implement, has minimal storage requirements, and effectively controls the size and complexity of the subproblems solved. The authors prove convergence of the algorithm, and show how to solve the subproblems in closed-form. A computational comparison with a popular competing method exhibits an increased advantage for the proposed algorithm with an increase in problem size, except for highly ill-conditioned problems.