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 non-negative. This family of problems captures in particular polynomial optimization problems (POPs), polynomial semi-definite polynomial optimization problems (PSDPs) and polynomial second-order cone-optimization problems (PSOCPs). We propose a new general hierarchy of linear conic optimization relaxations inspired by an extension of Pólya's Positivstellensatz for homogeneous polynomials being positive over a basic semi-algebraic cone contained in the non-negative orthant, introduced in Dickinson and Povh (J Glob Optim 61(4):615-625, 2015). We prove that based on some classic assumptions, these relaxations converge monotonically to the optimal value of the original problem. Adding a redundant polynomial positive semi-definite constraint to the original problem drastically improves the bounds produced by our method. We provide an extensive list of numerical examples that clearly indicate the advantages and disadvantages of our hierarchy. In particular, in comparison to the classic approach of sum-of-squares, our new method provides reasonable bounds on the optimal value for POPs, and strong bounds for PSDPs and PSOCPs, even outperforming the sum-of-squares approach in these latter two cases.
COBISS.SI-ID: 16466459
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 nonflat data, and then its sensitivity under perturbations is studied. The focus is on eigenvalue optimization for noncommutative polynomials, but we also explain how the main results pertain to commutative and tracial optimization.
COBISS.SI-ID: 16398875
Linear matrix inequalities (LMIs) $I_d + \sum _{j=1}^g A_jx_j + \sum_{j=1}^g A_j^*x_j^* \succeq 0$ play a role in many areas of applications. The set of solutions of an LMI is a spectrahedron. LMIs in (dimension-free) matrix variables model most problems in linear systems engineering, and their solution sets are called free spectrahedra. Free spectrahedra are exactly the free semialgebraic convex sets. This paper studies free analytic maps between free spectrahedra and, under certain (generically valid) irreducibility assumptions, classifies all those that are bianalytic. The foundation of such maps turns out to be a very small class of birational maps we call convexotonic. The convexotonic maps in $g$ variables sit in correspondence with $g$-dimensional algebras. If two bounded free spectrahedra ${\mathcal {D}}_A$ and ${\mathcal {D}}_B$ meeting our irreducibility assumptions are free bianalytic with map denoted $p$, then $p$ must (after possibly an affine linear transform) extend to a convexotonic map corresponding to a $g$-dimensional algebra spanned by $(U-I)A_1,\ldots ,(U-I)A_g$ for some unitary $U$. Furthermore, $B$ and $UA$ are unitarily equivalent. The article also establishes a Positivstellensatz for free analytic functions whose real part is positive semidefinite on a free spectrahedron and proves a representation for a free analytic map from ${\mathcal {D}}_A$ to ${\mathcal {D}}_B$ (not necessarily bianalytic). Another result shows that a function analytic on any...
COBISS.SI-ID: 18554201
In this paper we present a parallel Branch and Bound (B&B) algorithm to solve the Stable Set Problem, which is a well-known combinatorial optimization problem. The algorithm is based on tight semidefinite programming bounds. Numerical results, based on using up to 192 CPU cores, show that this algorithm scales very well.
COBISS.SI-ID: 111111
In this article, we describe how we parallelized the famous BiqMac rescuer.
COBISS.SI-ID: 18745177