Infeasibility certificates for linear matrix inequalities

Details Infeasibility certificates for linear matrix inequalities Infeasibility certificates for linear matrix inequalities

2011-08-30

arxiv.org/abs/1108.5930v1

Mathematics

Optimization and Control

30 pages

Scientific paper

Farkas' lemma is a fundamental result from linear programming providing linear certificates for infeasibility of systems of linear inequalities. In semidefinite programming, such linear certificates only exist for strongly infeasible linear matrix inequalities. We provide nonlinear algebraic certificates for all infeasible linear matrix inequalities in the spirit of real algebraic geometry. More precisely, we show that a linear matrix inequality is infeasible if and only if -1 lies in the quadratic module associated to it. We prove exponential degree bounds for the corresponding algebraic certificate. In order to get a polynomial size certificate, we use a more involved algebraic certificate motivated by the real radical and Prestel's theory of semiorderings. Completely different methods, namely complete positivity from operator algebras, are employed to consider linear matrix inequality domination.

Affiliated with

Also associated with

No associations

Rating

Infeasibility certificates for linear matrix inequalities does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Infeasibility certificates for linear matrix inequalities, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Infeasibility certificates for linear matrix inequalities will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-729023