This Article Full Text (PDF) Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Google Scholar Articles by Caron, R. J. Articles by Jibrin, S.

Feasibility and Constraint Analysis of Sets of Linear Matrix Inequalities

University of Windsor, Windsor, Ontario N9B 3P4, Canada
University of Windsor, Windsor, Ontario N9B 3P4, Canada
Northern Arizona University, Flagstaff, Arizona 86011
rcaron{at}uwindsor.ca
tt{at}uwindsor.ca
shafiu.jibrin{at}nau.edu

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.

Key words: linear matrix inequalities; positive semidefinite programming; feasibility; redundancy; irreducible infeasible sets
History: received February 2008; revised November 2008; accepted March 2009.