Feasibility and constraint analysis of sets of linear matrix inequalities

Richard J. Caron, Tim Traynor, Shafiu Jibrin

Research output: Contribution to journalArticlepeer-review

3 Scopus citations


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.

Original languageEnglish (US)
Pages (from-to)144-153
Number of pages10
JournalINFORMS Journal on Computing
Issue number1
StatePublished - Dec 2010


  • Feasibility
  • Irreducible infeasible sets
  • Linear matrix inequalities
  • Positive semidefinite programming
  • Redundancy

ASJC Scopus subject areas

  • Software
  • Information Systems
  • Computer Science Applications
  • Management Science and Operations Research


Dive into the research topics of 'Feasibility and constraint analysis of sets of linear matrix inequalities'. Together they form a unique fingerprint.

Cite this