In this paper we consider a parametric family of quadratically constrained
quadratic programs (QCQP) and their associated semidefinite programming (SDP)
relaxations. Given a value of the parameters at which the SDP relaxation is
exact, we study conditions (and quantitative bounds) under which the relaxation
will continue to be exact as the parameter moves in a neighborhood around it.
More generally, our results can be used to analyze SDP relaxations of
polynomial optimization problems. Our framework captures several estimation
problems such as low rank approximation, camera triangulation, rotation
synchronization and approximate matrix completion. The SDP relaxation correctly
solves these problems under noiseless observations, and our results guarantee
that the relaxation will continue to solve them in the low noise regime.
Consider the problem of minimizing a quadratic objective subject to quadratic
equations. We study the semialgebraic region of objective functions for which
this problem is solved by its semidefinite relaxation. For the Euclidean
distance problem, this is a bundle of spectrahedral shadows surrounding the
given variety. We characterize the algebraic boundary of this region and we
derive a formula for its degree.
We study sum of squares (SOS) relaxations to optimize polynomial functions
over a set $V\cap R^n$, where $V$ is a complex algebraic variety. We propose a
new methodology that, rather than relying on some algebraic description,
represents $V$ with a generic set of complex samples. This approach depends
only on the geometry of $V$, avoiding representation issues such as
multiplicity and choice of generators. It also takes advantage of the
coordinate ring structure to reduce the size of the corresponding semidefinite
program (SDP). In addition, the input can be given as a straight-line program.
Our methods are particularly appealing for varieties that are easy to sample
from but for which the defining equations are complicated, such as $SO(n)$,
Grassmannians or rank $k$ tensors. For arbitrary varieties we can obtain the
required samples by using the tools of numerical algebraic geometry. In this
way we connect the areas of SOS optimization and numerical algebraic geometry.
We introduce a novel representation of structured polynomial ideals, which we
refer to as chordal networks. The sparsity structure of a polynomial system is
often described by a graph that captures the interactions among the variables.
Chordal networks provide a computationally convenient decomposition into
simpler (triangular) polynomial sets, while preserving the underlying graphical
structure. We show that many interesting families of polynomial ideals admit
compact chordal network representations (of size linear in the number of
variables), even though the number of components is exponentially large.
Chordal networks can be computed for arbitrary polynomial systems using a
refinement of the chordal elimination algorithm from [Cifuentes-Parrilo-2016].
Furthermore, they can be effectively used to obtain several properties of the
variety, such as its dimension, cardinality, and equidimensional components, as
well as an efficient probabilistic test for radical ideal membership. We apply
our methods to examples from algebraic statistics and vector addition systems;
for these instances, algorithms based on chordal networks outperform existing
techniques by orders of magnitude.
Chordal structure and bounded treewidth allow for efficient computation in
numerical linear algebra, graphical models, constraint satisfaction and many
other areas. In this paper, we begin the study of how to exploit chordal
structure in computational algebraic geometry, and in particular, for solving
polynomial systems. The structure of a system of polynomial equations can be
described in terms of a graph. By carefully exploiting the properties of this
graph (in particular, its chordal completions), more efficient algorithms can
be developed. To this end, we develop a new technique, which we refer to as
chordal elimination, that relies on elimination theory and Gr\"obner bases. By
maintaining graph structure throughout the process, chordal elimination can
outperform standard Gr\"obner basis algorithms in many cases. The reason is
that all computations are done on "smaller" rings, of size equal to the
treewidth of the graph. In particular, for a restricted class of ideals, the
computational complexity is linear in the number of variables. Chordal
structure arises in many relevant applications. We demonstrate the suitability
of our methods in examples from graph colorings, cryptography, sensor
localization and differential equations.
We present an efficient algorithm to compute permanents, mixed discriminants
and hyperdeterminants of structured matrices and multidimensional arrays
(tensors). We describe the sparsity structure of an array in terms of a graph,
and we assume that its treewidth, denoted as $\omega$, is small. Our algorithm
requires $O(n 2^\omega)$ arithmetic operations to compute permanents, and
$O(n^2 + n 3^\omega)$ for mixed discriminants and hyperdeterminants. We finally
show that mixed volume computation continues to be hard under bounded treewidth
The degree chromatic polynomial $Pm(G,k)$ of a graph $G$ counts the number of
$k$-colorings in which no vertex has $m$ adjacent vertices of its same color.
We prove Humpert and Martin's conjecture on the leading terms of the degree
chromatic polynomial of a tree.