Efficiency Measures of Vertex Following Algorithms on Polyhedral Sets.
CALIFORNIA UNIV BERKELEY OPERATIONS RESEARCH CENTER
Pagination or Media Count:
Given a polyhedral set p x an element of R sup K such that Ax or b, let V denote the set of all vertices of p satisfying a prescribed condition. Consider the problem of determining whether or not V is empty, and if not, finding a point in V. An algorithm to solve this problem is called a Vertex Following Algorithm VFA if it follows a path of neighboring vertices before it terminates. In this dissertation, certain concepts of efficiency measures of VFAs are investigated classifications of VFAs are presented with regard to the number of iterations required before termination and the average computational effort for each iteration. The properties of polyhedral sets as related to VFAs are presented in a unified way an example is given to show how one can use these properties in establishing bounds on efficiencies of VFAs. Then a practical algorithm for finding all vertices of a polytope expressed by a set of linear inequalities is constructed. Some previous results on random polyhedra, related to VFAs, are briefly restated. Several probability measures that can be used in studies of VFAs are presented. A procedure for probabilistic studies of VFAs is then proposed.
- Operations Research