Janez Povh In this article we present a robustness analysis of the extraction of optimizers in polynomial optimization. Optimizers can be extracted by solving moment problems using flatness and the Gelfand-Naimark-Segal (GNS) construction. Here a modification of the GNS construction is presented that applies even to non-flat data, and then its sensitivity under perturbations is studied. The … Read more
The study of matrix inequalities in a dimension-free setting is in the realm of free real algebraic geometry (RAG). In this paper we investigate constrained trace and eigenvalue optimization of noncommutative polynomials. We present Lasserre’s relaxation scheme for trace optimization based on semidefinite programming (SDP) and demonstrate its convergence properties. Finite convergence of this relaxation … Read more
In this paper we consider polynomials in noncommuting variables that admit sum of hermitian squares and commutators decompositions. We recall algorithms for finding decompositions of this type that are based on semidefinite programming. The main part of the article investigates how to find such decomposition with rational coefficients if the original polynomial has rational coefficients. … Read more
In this paper we consider polynomial conic optimization problems, where the feasible set is defined by constraints in the form of given polynomial vectors belonging to given nonempty closed convex cones, and we assume that all the feasible solutions are nonnegative. This family of problems captures in particular polynomial optimization problems, polynomial semidefinite polynomial optimization … Read more
In this paper we provide a generalization of two well-known positivstellensätze, namely the positivstellensatz from Pólya [Georg Pólya. Über positive darstellung von polynomen vierteljschr. In Naturforsch. Ges. Zürich, 73: 141-145, 1928] and the positivestellensatz from Putinar and Vasilescu [Mihai Putinar and Florian-Horia Vasilescu. Positive polynomials on semialgebraic sets. Comptes Rendus de l’Académie des Sciences – … Read more
In this paper, an erratum is provided to the article “\emph{On the set-semidefinite representation of nonconvex quadratic programs over arbitrary feasible sets}”, published in Optim.\ Letters, 2012. Due to precise observation of the first author, it has been found that the proof of Lemma 9 has a nontrivial gap, and consequently the main result (Theorem … Read more
The set of polynomials which are nonnegative over a subset of the nonnegative orthant (we call them set semidefinite) have many uses in optimization. A common example of this type of set is the set of copositive matrices, where effectively we are considering nonnegativity over the entire nonnegative orthant and we limit the polynomials to … Read more
This paper presents an algorithm and its implementation in the software package NCSOStools for finding sums of hermitian squares and commutators decompositions for polynomials in noncommuting variables. The algorithm is based on noncommutative analogs of the classical Gram matrix method and the Newton polytope method, which allows us to use semidefinite programming. Throughout the paper … Read more
In the paper we prove that any nonconvex quadratic problem over some set $K\subset \mathbb{R}^n$ with additional linear and binary constraints can be rewritten as linear problem over the cone, dual to the cone of K-semidefinite matrices. We show that when K is defined by one quadratic constraint or by one concave quadratic constraint and … Read more
In this paper we study constrained eigenvalue optimization of noncommutative (nc) polynomials, focusing on the polydisc and the ball. Our three main results are as follows: (1) an nc polynomial is nonnegative if and only if it admits a weighted sum of hermitian squares decomposition; (2) (eigenvalue) optima for nc polynomials can be computed using … Read more