Let @math be a linear matrix, or pencil, generated by given symmetric matrices @math of size @math with rational entries. The set of real vectors x such that the pencil is positive semidefinite is a convex semi-algebraic set called spectrahedron, described by a linear matrix inequality (LMI). We design an exact algorithm that, up to genericity assumptions on the input matrices, computes an exact algebraic representation of at least one point in the spectrahedron, or decides that it is empty. The algorithm does not assume the existence of an interior point, and the computed point minimizes the rank of the pencil on the spectrahedron. The degree @math of the algebraic representation of the point coincides experimentally with the algebraic degree of a generic semidefinite program associated to the pencil. We provide explicit bounds for the complexity of our algorithm, proving that the maximum number of arithmetic operations that are performed is essentially quadratic in a multilinear B 'ezout bound of @math . When @math (resp. @math ) is fixed, such a bound, and hence the complexity, is polynomial in @math (resp. @math ). We conclude by providing results of experiments showing practical improvements with respect to state-of-the-art computer algebra algorithms.
To get a purely algebraic certificate of emptiness for @math , one could use the classical approach by Positivstellensatz @cite_14 @cite_1 @cite_8 . As a snake biting its tail, this would lead to a family, or hierarchy , of semidefinite programs @cite_11 . Bounds for the degree of Positivstellensatz certificates are exponential in the number of variables and have been computed in @cite_7 for Schmudgen's, and in @cite_2 for Putinar's formulation. In the recent remarkable result @cite_0 , a uniform @math fold exponential bound for the degree of the Hilbert 17th problem is provided. In @cite_6 , an emptiness certificate dedicated to the spectrahedral case, by means of special quadratic modules associated to these sets, is obtained.
@cite_14 @cite_7 @cite_8 @cite_1 @cite_6 @cite_0 @cite_2 @cite_11
2165281529 2077998936 2062162367 1964100506 2268784238 2083449425 1967344706
We consider the problem of minimizing a polynomial over a semialgebraic set defined by polynomial equations and inequalities, which is NP-hard in general. Hierarchies of semidefinite relaxations have been proposed in the literature, involving positive semidefinite moment matrices and the dual theory of sums of squares of polynomials. We present these hierarchies of approximations and their main properties: asymptotic finite convergence, optimality certificate, and extraction of global optimum solutions. We review the mathematical tools underlying these properties, in particular, some sums of squares representation results for positive polynomials, some results about moment matrices (in particular, of Curto and Fialkow), and the algebraic eigenvalue method for solving zero-dimensional systems of polynomial equations. We try whenever possible to provide detailed proofs and background. The aim of this note is to give short algebraic proofs of theorems of Handelman, Polya and Schmudgen concerning the algebraic structure of polynomials being positive on certain subsets of ℝ n . The main ingredient of the proofs is the representation theorem of Kadison–Dubois. The proof of the latter is elementary and algebraic but tricky. 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: A linear matrix inequality @math is infeasible if and only if -1 lies in the quadratic module associated to A. We also present a new exact duality theory for semidefinite programming, motivated by the real radical and sums of squares certificates from real algebraic geometry. We prove elementary recursive bounds in the degrees for Positivstellensatz and Hilbert 17-th problem, which is the expression of a nonnegative polynomial as a sum of squares of rational functions. We obtain a tower of five exponentials. A precise bound in terms of the number and degree of the polynomials and their number of variables is provided in the paper. Let S= [email protected]?R^n|g"1(x)>=0,...,g"m(x)>=0 be a basic closed semialgebraic set defined by real polynomials g"i. Putinar's Positivstellensatz says that, under a certain condition stronger than compactness of S, every real polynomial f positive on S possesses a representation [email protected]?"i"="0^[email protected]"ig"i where g"[email protected]?1 and each @s"i is a sum of squares of polynomials. Such a representation is a certificate for the nonnegativity of f on S. We give a bound on the degrees of the terms @s"ig"i in this representation which depends on the description of S, the degree of f and a measure of how close f is to having a zero on S. As a consequence, we get information about the convergence rate of Lasserre's procedure for optimization of a polynomial subject to polynomial constraints. We consider the problem of finding the unconstrained global minimum of a real-valued polynomial p(x): R ^n R $, as well as the global minimum of p(x), in a compact set K defined by polynomial inequalities. It is shown that this problem reduces to solving an (often finite) sequence of convex linear matrix inequality (LMI) problems. A notion of Karush--Kuhn--Tucker polynomials is introduced in a global optimality condition. Some illustrative examples are provided.