Polyhedral Basis, Probability Spaces, and Links to Disjunctive Programming

Motivated by our earlier study of convex extensions [25], 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.