On the distance between polytopes
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
W. Cheney and A. A. Goldstein, Proximity maps for convex sets, Proc. Amer. Math. Soc. 10, 448-450 (1959)
M. Frank and P. Wolfe, An algorithm for quadratic programming, NRLQ 3, 95-110 (1956)
P. Wolfe, The simplex method for quadratic programming, Econometriea 27, 382-398 (1959)
G. Dantzig, Linear programming and extensions, Princeton University Press, Princeton, New Jersey, 1963.
A. A. Goldstein and W. Cheney, A finite algorithm for the solution of consistent linear equations and inequalities and for the Tchebycheff approximation of consistent linear equations, Pacific J. Math. 3, 415–427 (1958)
A. Ben-Israel, Generalized inverses and the Bott-Duffin network analysis, J. Math Anal. Appl. 7 (1963)
R. Penrose, A generalized inverse for matrices, Proc. Cambridge Philos. Soc. 51, 406–413 (1955)
G. Zoutendijk, Methods of feasible directions, Elsevier Publishing Co., New York, 1960.
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)
G. Dantzig, A. Orden and P. Wolfe, Notes on linear programming: Part I. The generalized simplex method for minimizing a linear form under linear inequality restraints, Pacific J. Math. 5, 183–195 (1955)
S. Agmon, The relaxation method for linear inequalities, Canada J. Math. 6, 382–392 (1954)
T. S. Motzkin and I. J. Shoenberg, The relaxation method for linear inequalities, Canada J. Math. 6, 393–404 (1954)
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, Numerische Mathematik 2, 1–17 (1960)
I. Barrodale and A. Young, Algorithms for best ${L_1}$ and ${L_\infty }$ linear approximations on a discrete set, Numerische Mathematik 8, 295–306 (1966)
A. Charnes, W. W. Cooper and R. O. Ferguson, Optimal estimation of executive compensation by linear programming, Management Science 1, 138–151 (1955)
Similar Articles
Retrieve articles in Quarterly of Applied Mathematics
with MSC:
41.60
Retrieve articles in all journals
with MSC:
41.60
Additional Information
Article copyright:
© Copyright 1968
American Mathematical Society