Details:
Title | Semidefinite representations for finite varieties | Author(s) | Monique Laurent | Type | Technical Report, Misc | Abstract | We consider the problem of minimizing a polynomial over a set defined by polynomial equations and inequalities. When the polynomial equations have a finite set of complex solutions, we can reformulate this problem as a semidefinite programming problem. Our semidefinite representation involves combinatorial moment matrices, which are matrices indexed by a basis of the quotient vector space R[x_1, ..., x_n]/I, where I is the ideal generated by the polynomial equations in the problem. Moreover, we prove the finite convergence of a hierarchy of semidefinite relaxations introduced by Lasserre. Semidefinite approximations can be constructed by considering truncated combinatorial moment matrices; rank conditions are given (in a grid case) that ensure that the approximation solves the original problem to optimality. |
URL |
http://homepages.cwi.nl/~monique/ |
Language | English | Year | 2004 | Month | June | Edition | 0 | Translation |
No | Refereed |
No |
|