On the distance between polytopes

Willner, Leopold B.

doi:10.1090/qam/231106

Author: Leopold B. Willner
Journal: Quart. Appl. Math. 26 (1968), 207-212
MSC: Primary 41.60
DOI: https://doi.org/10.1090/qam/231106
MathSciNet review: 231106
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: This paper is written to fill an apparent gap in the literature in connection with some elementary problems of distance in finite dimensional normed linear spaces. In particular the problem of determining the distance between two polytopes in a normed $n$-dimensional real vector space is considered. Special consideration is given to the case in which the norm is a twice differentiable function of its arguments and for this case a convex programming algorithm is presented. In addition several other cases are considered including the well known discrete Tchebycheff approximation. The results should find application in approximation theory.

Ward Cheney and Allen A. Goldstein, Proximity maps for convex sets, Proc. Amer. Math. Soc. 10 (1959), 448–450. MR 105008, DOI https://doi.org/10.1090/S0002-9939-1959-0105008-8
Marguerite Frank and Philip Wolfe, An algorithm for quadratic programming, Naval Res. Logist. Quart. 3 (1956), 95–110. MR 89102, DOI https://doi.org/10.1002/nav.3800030109
Philip Wolfe, The simplex method for quadratic programming, Econometrica 27 (1959), 382–398. MR 106783, DOI https://doi.org/10.2307/1909468
George B. Dantzig, Linear programming and extensions, Princeton University Press, Princeton, N.J., 1963. MR 0201189
Allen A. Goldstein and Ward Cheney, A finite algorithm for the solution of consistent linear equations and inequalities and for the Tchebycheff approximation of inconsistent linear equations, Pacific J. Math. 8 (1958), 415–427. MR 101505
A. Ben-Israel and A. Charnes, Generalized inverses and the Bott-Duffin network analysis, J. Math. Anal. Appl. 7 (1963), 428–435. MR 156864, DOI https://doi.org/10.1016/0022-247X%2863%2990064-7
R. Penrose, A generalized inverse for matrices, Proc. Cambridge Philos. Soc. 51 (1955), 406–413. MR 69793
G. Zoutendijk, Methods of feasible directions: A study in linear and non-linear programming, Elsevier Publishing Co., Amsterdam-London-New York-Princeton, N.J., 1960. MR 0129119

P. Wolfe, Computational techniques for non linear programs, Princeton University Conference, 1957

G. Dantzig and P. Wolfe, Decomposition principle for linear programs, Operations Research 8, 101–111 (1960)

George B. Dantzig, Alex Orden, and Philip Wolfe, The generalized simplex method for minimizing a linear form under linear inequality restraints, Pacific J. Math. 5 (1955), 183–195. MR 69584
Shmuel Agmon, The relaxation method for linear inequalities, Canad. J. Math. 6 (1954), 382–392. MR 62786, DOI https://doi.org/10.4153/cjm-1954-037-2
T. S. Motzkin and I. J. Schoenberg, The relaxation method for linear inequalities, Canad. J. Math. 6 (1954), 393–404. MR 62787, DOI https://doi.org/10.4153/cjm-1954-038-x

J. E. Kelley, Jr., An application of linear programming to carve fitting, J. SIAM 15–22 (1958)

E. Stiefel, Note on Jordan elimination, linear programming and Tchebycheff approximation, Numer. Math. 2 (1960), 1–17. MR 111124, DOI https://doi.org/10.1007/BF01386203
Ian Barrodale and Andrew Young, Algorithms for best $L_{1}$ and $L_{\infty }$ linear approximations on a discrete set, Numer. Math. 8 (1966), 295–306. MR 196912, DOI https://doi.org/10.1007/BF02162565
A. Charnes and W. W. Cooper, Optimal estimation of executive compensation by linear programming, Management Sci. 1 (1955), 138–151. MR 73914, DOI https://doi.org/10.1287/mnsc.1.2.138