A Probabilistic Algorithm for the Solution of Homogeneous Linear Inequalities

This thesis presents a probabilistic algorithm for the solution of system of homogeneous linear inequality constraints. In fact, the proposed method simultaneously provides information required for constraint analysis and, if the feasible region is not empty, with probability one, will find a feasible solution. In [1] Caron and Traynor explored the relationship between the constraint analysis problem and a certain set covering problem proposed by Boneh [2]. They provided the framework that showed the connection between minimal representations, irreducible infeasible systems, minimal infeasibility sets, as well as other attributes of preprocessing of mathematical programs. In [3] 2010 Caron et. al. showed the application of the constraint analysis methodology to linear matrix inequality constraints. This thesis builds on those results to develop a method specific to a system of homogeneous linear inequalities. Much of this thesis is devoted to the development of a hit and run sampling methodology