Polyhedral Basis, Probability Spaces, and Links to Disjunctive Programming
AbstractMotivated by our earlier study of convex extensions , we define a polyhedral basis over a convex set. We explore properties of polyhedral functions that lead us into studying their relations to convexification and disjunctive programming. In particular, we show that a polyhedral basis is easy to identify for Cartesian products of simplices. A special case, that of an n-dimensional hypercube, is of particular interest in this study. In this case, we show that convex and concave envelopes of multilinear sets are derived as a consequence of disjunctive programming and Reformulation Linearization Techniques. We answer in negative an open question whether there exist polynomial functions that will provide convexification processes for general integer programs just as multilinear functions are used to convexify 0-1 programs in the reformulation linearization technique and the lift and project algorithm. The polyhedral functions also correspond to nonlinear rounding ideas and we will explore these in the article. This interpretation allows us to study probabilistic mathematical programs and explore their relation to multilinear programs. More concretely, we demonstrate that a probabilistic mathematical program is equivalent to the lagrangian relaxation of a multilinear program. Consequently, we study approximation schemes and demonstrate that rounding schemes often hint at polyhedral basis functions. Some negative results about Lagrangian relaxation are presented. This is a preliminary set of proofs and provides many directions for further work in convexification techniques. Some of the results that follow easily are stated without proofs.
Download InfoTo our knowledge, this item is not available for download. To find whether it is available, there are three options:
1. Check below under "Related research" whether another version of this item is available online.
2. Check on the provider's web page whether it is in fact available.
3. Perform a search for a similarly titled item that would be available.
Bibliographic InfoPaper provided by Purdue University, Department of Economics in its series Purdue University Economics Working Papers with number 1157.
Length: 29 pages
Date of creation: 2002
Date of revision:
You can help add them by filling out this form.
For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: (Krannert PHD).
If references are entirely missing, you can add them using this form.