Vol. 28, No. 2, 1969

Download this article
Download this article. For screen
For printing
Recent Issues
Vol. 329: 1  2
Vol. 328: 1  2
Vol. 327: 1  2
Vol. 326: 1  2
Vol. 325: 1  2
Vol. 324: 1  2
Vol. 323: 1  2
Vol. 322: 1  2
Online Archive
The Journal
About the journal
Ethics and policies
Peer-review process
Submission guidelines
Submission form
Editorial board
ISSN: 1945-5844 (e-only)
ISSN: 0030-8730 (print)
Special Issues
Author index
To appear
Other MSP journals
Lifting projections of convex polyhedra

David William Walkup and Roger Jean-Baptiste Robert Wets

Vol. 28 (1969), No. 2, 465–475

If τ is a projection of a closed convex polyhedron P onto a convex polyhedron Q, then a lifting of Q into P is defined to be a single-valued inverse τ of τ such that τ(Q) is the union of closed faces of P. The main result of this paper, designated the Lifting Theorem, asserts that there always exists a lifting τ, provided only that there exists at least one face of P on which τ acts one-to-one. The lifting theorem represents a unifying generalization of a number of results in the theory of convex polyhedra and should prove useful as an investigative as well as a conceptual tool. In the course of the proof, a special case of the Lifting Theorem is translated into linear programming terms and stated as the Basis Decomposition Theorem, which summarizes the behavior of a linear program as a function of its right-hand sides. In particular, the fact that a lifting is necessarily a piecewise linear homeomorphism is reflected in the Basis Decomposition Theorem as the observation that the optimal solution of a linear program can always be chosen as a continuous function of the right-hand sides.

Mathematical Subject Classification
Primary: 52.10
Secondary: 90.00
Received: 12 June 1968
Published: 1 February 1969
David William Walkup
Roger Jean-Baptiste Robert Wets