Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss

linear algebraic variety generated by a semialgebraic closed convex set (semidefinite programming)

0 views
Skip to first unread message

David Monniaux

unread,
Jul 16, 2008, 9:05:41 AM7/16/08
to
I'm studying the semidefinite programming problem:
Given real symmetric m x m matrices (well, rational matrices in
practice) F_0, F_1, ..., F_n, obtain x_1, ..., x_n real coefficients
such that
F = F_0 + \sum_i x_i F_i >= 0 (I mean, is semidefinite positive).

We suppose the F_i to be linearly independent.

The set S of acceptable (x_1, ...., x_n) vectors is:
* closed and convex (it is the intersection of the halfspaces defined by
x^t F_0 x + \sum_i (x^t F_i x) x_i >= 0 for all vector x)
* semialgebraic: F is semidefinite positive if and only if the
coefficients of its characteristic polynomial are alternatively
nonpositive and nonnegative (the determinant is nonnegative, the next
one is nonpositive, etc.), so it is defined by m polynomial inequalities.

I would be tremendously helped if I could compute the linear algebraic
variety generated by S (I mean, the least set of the form v_0 +
Vect(v_1, ..., v_d) such that S is included in it.)

By "computing" I mean actually obtaining v_0, v_1, ..., v_d. My
intuition is that if the F_i are rational, then these should also be
rational if there is at least one rational point inside S.

Would somebody have any idea about this that does not involve using
quantifier elimination over real closed fields?

I realize that this is like a shot in the dark...

Thanks in advance

0 new messages