In this paper we propose a general hierarchy of conic linear programming relaxations for homogeneous polynomials being positive over a basic semialgebraic cone contained in the nonnegative orthant. Under some classical assumptions these relaxations converge monotonically to the optimal value of the original problem. The members of this hierarchy provide strong bounds for the optimum value and are in the special cases from the previous paragraph much easier to compute then classical SOS and moment approximations.
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 modication 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 it is also explained how the main results pertain to commutative and tracial optimization.
A vertex signature $\pi$ of a finite graph $G$ is any mapping $\pi \, : \, V(G)\to \{0,1\}$. An edge-coloring of $G$ is said to be \textit{vertex-parity} for the pair $(G,\pi)$ if for every vertex $v$ each color used on the edges incident to $v$ appears in parity accordance with $\pi$, i.e. an even or odd number of times depending on whether $\pi(v)$ equals $0$ or $1$, respectively. The minimum number of colors for which $(G,\pi)$ admits such an edge-coloring is denoted by $\chi'_p(G,\pi)$. We characterize the existence and prove that $\chi'_p(G,\pi)$ is at most $6$. Furthermore, we give a structural characterization of the pairs $(G,\pi)$ for which $\chi'_p(G,\pi)=5$ and $\chi'_p(G,\pi)=6$. In the last part of the paper, we consider a weaker version of the coloring, where it suffices that at every vertex, at least one color appears in parity accordance with $\pi$. We show that the corresponding chromatic index is at most $3$ and give a complete characterization for it.
COBISS.SI-ID: 2048470291
In this paper we propose a general hierarchy of conic linear programming relaxations for homogeneous polynomials being positive over a basic semialgebraic cone contained in the nonnegative orthant. Under some classical assumptions these relaxations converge monotonically to the optimal value of the original problem. The members of this hierarchy provide strong bounds for the optimum value and are in the special cases from the previous paragraph much easier to compute then classical SOS and moment approximations.
COBISS.SI-ID: 123456
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 modication 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 it is also explained how the main results pertain to commutative and tracial optimization.
COBISS.SI-ID: 111111111