
We propose a new method for simplifying semidefinite programs (SDP) inspired
by symmetry reduction. Specifically, we show if an orthogonal projection map
satisfies certain invariance conditions, restricting to its range yields an
equivalent primaldual pair over a lowerdimensional symmetric conenamely,
the coneofsquares of a Jordan subalgebra of symmetric matrices. We present a
simple algorithm for minimizing the rank of this projection and hence the
dimension of this subalgebra. We also show that minimizing rank optimizes the
directsum decomposition of the algebra into simple ideals, yielding an optimal
"blockdiagonalization" of the SDP. Finally, we give combinatorial versions of
our algorithm that execute at reduced computational cost and illustrate
effectiveness of an implementation on examples. Through the theory of Jordan
algebras, the proposed method easily extends to linear and secondordercone
programming and, more generally, symmetric cone optimization.

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.

The matrix logarithm, when applied to Hermitian positive definite matrices,
is concave with respect to the positive semidefinite order. This operator
concavity property leads to numerous concavity and convexity results for other
matrix functions, many of which are of importance in quantum information
theory. In this paper we show how to approximate the matrix logarithm with
functions that preserve operator concavity and can be described using the
feasible regions of semidefinite optimization problems of fairly small size.
Such approximations allow us to use offtheshelf semidefinite optimization
solvers for convex optimization problems involving the matrix logarithm and
related functions, such as the quantum relative entropy. The basic ingredients
of our approach apply, beyond the matrix logarithm, to functions that are
operator concave and operator monotone. As such, we introduce strategies for
constructing semidefinite approximations that we expect will be useful, more
generally, for studying the approximation power of functions with small
semidefinite representations.

We show that existence of a global polynomial Lyapunov function for a
homogeneous polynomial vector field or a planar polynomial vector field (under
a mild condition) implies existence of a polynomial Lyapunov function that is a
sum of squares (sos) and that the negative of its derivative is also a sum of
squares. This result is extended to show that such sosbased certificates of
stability are guaranteed to exist for all stable switched linear systems. For
this class of systems, we further show that if the derivative inequality of the
Lyapunov function has an sos certificate, then the Lyapunov function itself is
automatically a sum of squares. These converse results establish cases where
semidefinite programming is guaranteed to succeed in finding proofs of Lyapunov
inequalities. Finally, we demonstrate some merits of replacing the sos
requirement on a polynomial Lyapunov function with an sos requirement on its
top homogeneous component. In particular, we show that this is a weaker
algebraic requirement in addition to being cheaper to impose computationally.

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 straightline 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.

This is an experimental case study in real algebraic geometry, aimed at
computing the image of a semialgebraic subset of 3space under a polynomial map
into the plane. For general instances, the boundary of the image is given by
two highly singular curves. We determine these curves and show how they
demarcate the "flattened soccer ball". We explore cylindrical algebraic
decompositions, by working through concrete examples. Maps onto convex polygons
and connections to convex optimization are also discussed.

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 [CifuentesParrilo2016].
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.

Sequential ratedistortion (SRD) theory provides a framework for studying the
fundamental tradeoff between datarate and dataquality in realtime
communication systems. In this paper, we consider the SRD problem for
multidimensional timevarying GaussMarkov processes under meansquare
distortion criteria. We first revisit the sensorestimator separation
principle, which asserts that considered SRD problem is equivalent to a joint
sensor and estimator design problem in which datarate of the sensor output is
minimized while the estimator's performance satisfies the distortion criteria.
We then show that the optimal joint design can be performed by semidefinite
programming. A semidefinite representation of the corresponding SRD function is
obtained. Implications of the obtained result in the context of zerodelay
source coding theory and applications to networked control theory are also
discussed.

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
assumptions.

A central question in optimization is to maximize (or minimize) a linear
function over a given polytope P. To solve such a problem in practice one needs
a concise description of the polytope P. In this paper we are interested in
representations of P using the positive semidefinite cone: a positive
semidefinite lift (psd lift) of a polytope P is a representation of P as the
projection of an affine slice of the positive semidefinite cone
$\mathbf{S}^d_+$. Such a representation allows linear optimization problems
over P to be written as semidefinite programs of size d. Such representations
can be beneficial in practice when d is much smaller than the number of facets
of the polytope P. In this paper we are concerned with socalled equivariant
psd lifts (also known as symmetric psd lifts) which respect the symmetries of
the polytope P. We present a representationtheoretic framework to study
equivariant psd lifts of a certain class of symmetric polytopes known as
orbitopes. Our main result is a structure theorem where we show that any
equivariant psd lift of size d of an orbitope is of sumofsquares type where
the functions in the sumofsquares decomposition come from an invariant
subspace of dimension smaller than d^3. We use this framework to study two
wellknown families of polytopes, namely the parity polytope and the cut
polytope, and we prove exponential lower bounds for equivariant psd lifts of
these polytopes.

Let G be a finite abelian group. This paper is concerned with nonnegative
functions on G that are sparse with respect to the Fourier basis. We establish
combinatorial conditions on subsets S and T of Fourier basis elements under
which nonnegative functions with Fourier support S are sums of squares of
functions with Fourier support T. Our combinatorial condition involves
constructing a chordal cover of a graph related to G and S (the Cayley graph
Cay($\hat{G}$,S)) with maximal cliques related to T. Our result relies on two
main ingredients: the decomposition of sparse positive semidefinite matrices
with a chordal sparsity pattern, as well as a simple but key observation
exploiting the structure of the Fourier basis elements of G.
We apply our general result to two examples. First, in the case where $G =
\mathbb{Z}_2^n$, by constructing a particular chordal cover of the halfcube
graph, we prove that any nonnegative quadratic form in n binary variables is a
sum of squares of functions of degree at most $\lceil n/2 \rceil$, establishing
a conjecture of Laurent. Second, we consider nonnegative functions of degree d
on $\mathbb{Z}_N$ (when d divides N). By constructing a particular chordal
cover of the d'th power of the Ncycle, we prove that any such function is a
sum of squares of functions with at most $3d\log(N/d)$ nonzero Fourier
coefficients. Dually this shows that a certain cyclic polytope in
$\mathbb{R}^{2d}$ with N vertices can be expressed as a projection of a section
of the cone of psd matrices of size $3d\log(N/d)$. Putting $N=d^2$ gives a
family of polytopes $P_d \subset \mathbb{R}^{2d}$ with LP extension complexity
$\text{xc}_{LP}(P_d) = \Omega(d^2)$ and SDP extension complexity
$\text{xc}_{PSD}(P_d) = O(d\log(d))$. To the best of our knowledge, this is the
first explicit family of polytopes in increasing dimensions where
$\text{xc}_{PSD}(P_d) = o(\text{xc}_{LP}(P_d))$.

The nonnegative rank of an entrywise nonnegative matrix A of size mxn is the
smallest integer r such that A can be written as A=UV where U is mxr and V is
rxn and U and V are both nonnegative. The nonnegative rank arises in different
areas such as combinatorial optimization and communication complexity.
Computing this quantity is NPhard in general and it is thus important to find
efficient bounding techniques especially in the context of the aforementioned
applications. In this paper we propose a new lower bound on the nonnegative
rank which, unlike most existing lower bounds, does not explicitly rely on the
matrix sparsity pattern and applies to nonnegative matrices with arbitrary
support. The idea involves computing a certain nuclear norm with nonnegativity
constraints which allows to lower bound the nonnegative rank, in the same way
the standard nuclear norm gives lower bounds on the standard rank. Our lower
bound is expressed as the solution of a copositive programming problem and can
be relaxed to obtain polynomialtime computable lower bounds using semidefinite
programming. We compare our lower bound with existing ones, and we show
examples of matrices where our lower bound performs better than currently known
ones.

In this paper we show how to construct inner and outer convex approximations
of a polytope from an approximate cone factorization of its slack matrix. This
provides a robust generalization of the famous result of Yannakakis that
polyhedral lifts of a polytope are controlled by (exact) nonnegative
factorizations of its slack matrix. Our approximations behave well under
polarity and have efficient representations using second order cones. We
establish a direct relationship between the quality of the factorization and
the quality of the approximations, and our results extend to generalized slack
matrices that arise from a polytope contained in a polyhedron.

We consider the problem of jointly estimating the attitude and spinrate of a
spinning spacecraft. Psiaki (J. Astronautical Sci., 57(12):7392, 2009) has
formulated a family of optimization problems that generalize the classical
leastsquares attitude estimation problem, known as Wahba's problem, to the
case of a spinning spacecraft. If the rotation axis is fixed and known, but the
spinrate is unknown (such as for nutationdamped spinstabilized spacecraft)
we show that Psiaki's problem can be reformulated exactly as a type of
tractable convex optimization problem called a semidefinite optimization
problem. This reformulation allows us to globally solve the problem using
standard numerical routines for semidefinite optimization. It also provides a
natural semidefinite relaxationbased approach to more complicated variations
on the problem.

Modelbased compressed sensing refers to compressed sensing with extra
structure about the underlying sparse signal known a priori. Recent work has
demonstrated that both for deterministic and probabilistic models imposed on
the signal, this extra information can be successfully exploited to enhance
recovery performance. In particular, weighted $\ell_1$minimization with
suitable choice of weights has been shown to improve performance in the so
called nonuniform sparse model of signals. In this paper, we consider a full
generalization of the nonuniform sparse model with very mild assumptions. We
prove that when the measurements are obtained using a matrix with i.i.d
Gaussian entries, weighted $\ell_1$minimization successfully recovers the
sparse signal from its measurements with overwhelming probability. We also
provide a method to choose these weights for any general signal model from the
nonuniform sparse class of signal models.

Given a polytope P in $\mathbb{R}^n$, we say that P has a positive
semidefinite lift (psd lift) of size d if one can express P as the linear
projection of an affine slice of the positive semidefinite cone
$\mathbf{S}^d_+$. If a polytope P has symmetry, we can consider equivariant psd
lifts, i.e. those psd lifts that respect the symmetry of P. One of the simplest
families of polytopes with interesting symmetries are regular polygons in the
plane, which have played an important role in the study of linear programming
lifts (or extended formulations). In this paper we study equivariant psd lifts
of regular polygons. We first show that the standard Lasserre/sumofsquares
hierarchy for the regular Ngon requires exactly ceil(N/4) iterations and thus
yields an equivariant psd lift of size linear in N. In contrast we show that
one can construct an equivariant psd lift of the regular 2^ngon of size 2n1,
which is exponentially smaller than the psd lift of the sumofsquares
hierarchy. Our construction relies on finding a sparse sumofsquares
certificate for the facetdefining inequalities of the regular 2^ngon, i.e.,
one that only uses a small (logarithmic) number of monomials. Since any
equivariant LP lift of the regular 2^ngon must have size 2^n, this gives the
first example of a polytope with an exponential gap between sizes of
equivariant LP lifts and equivariant psd lifts. Finally we prove that our
construction is essentially optimal by showing that any equivariant psd lift of
the regular Ngon must have size at least logarithmic in N.

We give explicit polynomialsized (in $n$ and $k$) semidefinite
representations of the hyperbolicity cones associated with the elementary
symmetric polynomials of degree $k$ in $n$ variables. These convex cones form a
family of nonpolyhedral outer approximations of the nonnegative orthant that
preserve lowdimensional faces while successively discarding highdimensional
faces. More generally we construct explicit semidefinite representations
(polynomialsized in $k,m$, and $n$) of the hyperbolicity cones associated with
$k$th directional derivatives of polynomials of the form $p(x) =
\det(\sum_{i=1}^{n}A_i x_i)$ where the $A_i$ are $m\times m$ symmetric
matrices. These convex cones form an analogous family of outer approximations
to any spectrahedral cone. Our representations allow us to use semidefinite
programming to solve the linear cone programs associated with these convex
cones as well as their (less well understood) dual cones.

Let M be a pbyq matrix with nonnegative entries. The positive semidefinite
rank (psd rank) of M is the smallest integer k for which there exist positive
semidefinite matrices $A_i, B_j$ of size $k \times k$ such that $M_{ij} =
\text{trace}(A_i B_j)$. The psd rank has many appealing geometric
interpretations, including semidefinite representations of polyhedra and
informationtheoretic applications. In this paper we develop and survey the
main mathematical properties of psd rank, including its geometry, relationships
with other rank notions, and computational and algorithmic aspects.

The nonnegative rank of a matrix A is the smallest integer r such that A can
be written as the sum of r rankone nonnegative matrices. The nonnegative rank
has received a lot of attention recently due to its application in
optimization, probability and communication complexity. In this paper we study
a class of atomic rank functions defined on a convex cone which generalize
several notions of "positive" ranks such as nonnegative rank or cprank (for
completely positive matrices). The main contribution of the paper is a new
method to obtain lower bounds for such ranks which improve on previously known
bounds. Additionally the bounds we propose can be computed by semidefinite
programming. The idea of the lower bound relies on an atomic norm approach
where the atoms are selfscaled according to the vector (or matrix, in the case
of nonnegative rank) of interest. This results in a lower bound that is
invariant under scaling and that is at least as good as other existing
normbased bounds.
We mainly focus our attention on the two important cases of nonnegative rank
and cprank where our bounds satisfying interesting properties: For the
nonnegative rank we show that our lower bound can be interpreted as a
noncombinatorial version of the fractional rectangle cover number, while the
sumofsquares relaxation is closely related to the Lov\'asz theta number of
the rectangle graph of the matrix. We also prove that the lower bound inherits
many of the structural properties satisfied by the nonnegative rank such as
invariance under diagonal scaling, subadditivity, etc. We also apply our method
to obtain lower bounds on the cprank for completely positive matrices. In this
case we prove that our lower bound is always greater than or equal the plain
rank lower bound, and we show that it has interesting connections with
combinatorial lower bounds based on edgeclique cover number.

We study the convex hull of $SO(n)$, thought of as the set of $n\times n$
orthogonal matrices with unit determinant, from the point of view of
semidefinite programming. We show that the convex hull of $SO(n)$ is doubly
spectrahedral, i.e. both it and its polar have a description as the
intersection of a cone of positive semidefinite matrices with an affine
subspace. Our spectrahedral representations are explicit, and are of minimum
size, in the sense that there are no smaller spectrahedral representations of
these convex bodies.

Distributed control problems under some specific information constraints can
be formulated as (possibly infinite dimensional) convex optimization problems.
The underlying motivation of this work is to develop an understanding of the
optimal decision making architecture for such problems. In this paper, we
particularly focus on the Nplayer triangular LQG problems and show that the
optimal output feedback controllers have attractive state space realizations.
The optimal controller can be synthesized using a set of stabilizing solutions
to 2N linearly coupled algebraic Riccati equations, which turn out to be easily
solvable under reasonable assumptions.

We introduce the framework of pathcomplete graph Lyapunov functions for
approximation of the joint spectral radius. The approach is based on the
analysis of the underlying switched system via inequalities imposed among
multiple Lyapunov functions associated to a labeled directed graph. Inspired by
concepts in automata theory and symbolic dynamics, we define a class of graphs
called pathcomplete graphs, and show that any such graph gives rise to a
method for proving stability of the switched system. This enables us to derive
several asymptotically tight hierarchies of semidefinite programming
relaxations that unify and generalize many existing techniques such as common
quadratic, common sum of squares, and maximum/minimumofquadratics Lyapunov
functions. We compare the quality of approximation obtained by certain classes
of pathcomplete graphs including a family of dual graphs and all pathcomplete
graphs with two nodes on an alphabet of two matrices. We provide approximation
guarantees for several families of pathcomplete graphs, such as the De Bruijn
graphs, establishing as a byproduct a constructive converse Lyapunov theorem
for maximum/minimumofquadratics Lyapunov functions.

We introduce the notion of exchangeable equilibria of a symmetric bimatrix
game, defined as those correlated equilibria in which players' strategy choices
are conditionally independently and identically distributed given some hidden
variable. We give several gametheoretic interpretations and a version of the
"revelation principle". Geometrically, the set of exchangeable equilibria is
convex and lies between the symmetric Nash equilibria and the symmetric
correlated equilibria. Exchangeable equilibria can achieve higher expected
utility than symmetric Nash equilibria.

There has been a lot of interest recently in proving lower bounds on the size
of linear programs needed to represent a given polytope P. In a breakthrough
paper Fiorini et al. [Proceedings of 44th ACM Symposium on Theory of Computing
2012, pages 95106] showed that any linear programming formulation of
maximumcut must have exponential size. A natural question to ask is whether
one can prove such strong lower bounds for semidefinite programming
formulations. In this paper we take a step towards this goal and we prove
strong lower bounds for a certain class of SDP formulations, namely SDPs over
the Cartesian product of fixedsize positive semidefinite cones. In practice
this corresponds to semidefinite programs with a blockdiagonal structure and
where blocks have constant size d. We show that any such extended formulation
of the cut polytope must have exponential size (when d is fixed). The result of
Fiorini et al. for LP formulations is obtained as a special case when d=1. For
blocks of size d=2 the result rules out any small formulations using
secondorder cone programming. Our study of SDP lifts over Cartesian product of
fixedsize positive semidefinite cones is motivated mainly from practical
considerations where it is well known that such SDPs can be solved more
efficiently than general SDPs. The proof of our lower bound relies on new
results about the sparsity pattern of certain matrices with small psd rank,
combined with an induction argument inspired from the recent paper by Kaibel
and Weltge [arXiv:1307.3543] on the LP extension complexity of the correlation
polytope.

We consider polynomial differential equations and make a number of
contributions to the questions of (i) complexity of deciding stability, (ii)
existence of polynomial Lyapunov functions, and (iii) existence of sum of
squares (sos) Lyapunov functions.
(i) We show that deciding local or global asymptotic stability of cubic
vector fields is strongly NPhard. Simple variations of our proof are shown to
imply strong NPhardness of several other decision problems: testing local
attractivity of an equilibrium point, stability of an equilibrium point in the
sense of Lyapunov, invariance of the unit ball, boundedness of trajectories,
convergence of all trajectories in a ball to a given equilibrium point,
existence of a quadratic Lyapunov function, local collision avoidance, and
existence of a stabilizing control law.
(ii) We present a simple, explicit example of a globally asymptotically
stable quadratic vector field on the plane which does not admit a polynomial
Lyapunov function (joint work with M. Krstic). For the subclass of homogeneous
vector fields, we conjecture that asymptotic stability implies existence of a
polynomial Lyapunov function, but show that the minimum degree of such a
Lyapunov function can be arbitrarily large even for vector fields in fixed
dimension and degree. For the same class of vector fields, we further establish
that there is no monotonicity in the degree of polynomial Lyapunov functions.
(iii) We show via an explicit counterexample that if the degree of the
polynomial Lyapunov function is fixed, then sos programming may fail to find a
valid Lyapunov function even though one exists. On the other hand, if the
degree is allowed to increase, we prove that existence of a polynomial Lyapunov
function for a planar or a homogeneous vector field implies existence of a
polynomial Lyapunov function that is sos and that the negative of its
derivative is also sos.