Feasibility and Constraint Analysis of Sets of Linear Matrix Inequalities

We present a constraint analysis methodology for linear matrix inequality constraints. If the constraint set is found to be feasible, we search for a minimal representation; otherwise, we search for an irreducible infeasible system. The work is based on the solution of a set-covering problem where each row corresponds to a sample point and is determined by constraint satisfaction at the sampled point. Thus, an implementation requires a method to collect points in the ambient space and a constraint oracle. Much of this paper will be devoted to the development of a hit-and-run sampling methodology. Test results confirm that our approach not only provides information required for constraint analysis but will also, if the feasible region has a nonvoid interior, with probability one, find a feasible point.