Computing monotone disjoint paths on polytopes

The Holt-Klee Condition states that there exist at least d vertex-disjoint strictly monotone paths from the source to the sink of a polytopal digraph consisting of the set of vertices and arcs of a polytope P directed by a linear objective function in general position. The study of paths on polytopal digraphs stems from a long standing problem, that of designing a polynomial-time pivot method, or proving none exists. To study disjoint paths it would be useful to have a tool to compute them. Without explicitly computing the digraph we develop an algorithm to compute a maximum cardinality set of source to sink paths in a polytope, even in the presence of degeneracy. The algorithm uses a combination of networks flows, the simplex method, and reverse search. An implementation is available.     

Shrinkage and variable selection by polytopes

Constrained estimators that enforce variable selection and grouping of highly correlated data have been shown to be successful in finding sparse representations and obtaining good performance in prediction. We consider polytopes as a general class of compact and convex constraint regions. Well-established procedures like LASSO (Tibshirani, 1996) or OSCAR (Bondell and Reich, 2008) are shown to be based on specific subclasses of polytopes. The general framework of polytopes can be used to investigate the geometric structure that underlies these procedures. Moreover, we propose a specifically designed class of polytopes that enforces variable selection and grouping. Simulation studies and an application illustrate the usefulness of the proposed method.     

The use of edge-directions and linear programming to enumerate vertices

Given a list of vectors that contains directions of the edges of a given polytope ℘ and the availability of an algorithm that solves linear programs over ℘, we describe a method for enumerating the vertices of ℘; in particular, the method is adaptable to polytopes which are presented as (linear) projections of polytopes having linear inequality representation. Polynomial complexity bounds under both the real and the binary computation models are derived when the dimension of the polytope is fixed and the given LP algorithm is polynomial. Dedicated to Professor Frank K. Hwang on the occasion of his sixty fifth birthday. Supported in part by a grant from ISF—the Israel Science Foundation, by a VPR grant at the Technion and by the Fund for the Promotion of Research at the Technion.