Efficiency Measures of Vertex Following Algorithms on Polyhedral Sets.
Abstract
Given a polyhedral set p = (x an element of (R sup K) such that A(x) < 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 VFA's are investigated; classifications of VFA's 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 VFA's are presented in a unified way; an example is given to show how one can use these properties in establishing bounds on efficiencies of VFA's. 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 VFA's, are briefly restated. Several probability measures that can be used in studies of VFA's are presented. A procedure for probabilistic studies of VFA's is then proposed.
Document Details
- Document Type
- Technical Report
- Publication Date
- Jun 01, 1975
- Accession Number
- ADA012484
Entities
People
- Aydin Ulkucu
Organizations
- University of California, Berkeley