Every convex homogeneous polynomial (or form) is nonnegative. Blekherman has shown that there exist convex forms that are not sums of squares via a nonconstructive argument. We provide an explicit example of a convex form of degree four in 272 variab
les that is not a sum of squares. The form is related to the Cauchy-Schwarz inequality over the octonions. The proof uses symmetry reduction together with the fact (due to Blekherman) that forms of even degree, that are near-constant on the unit sphere, are convex. Using this same connection, we obtain improved bounds on the approximation quality achieved by the basic sum-of-squares relaxation for optimizing quaternary quartic forms on the sphere.
Amenability is a notion of facial exposedness for convex cones that is stronger than being facially dual complete (or nice) which is, in turn, stronger than merely being facially exposed. Hyperbolicity cones are a family of algebraically structured c
losed convex cones that contain all spectrahedra (linear sections of positive semidefinite cones) as special cases. It is known that all spectrahedra are amenable. We establish that all hyperbolicity cones are amenable. As part of the argument, we show that any face of a hyperbolicity cone is a hyperbolicity cone. As a corollary, we show that the intersection of two hyperbolicity cones, not necessarily sharing a common relative interior point, is a hyperbolicity cone.
We present a generalization of the notion of neighborliness to non-polyhedral convex cones. Although a definition of neighborliness is available in the non-polyhedral case in the literature, it is fairly restrictive as it requires all the low-dimensi
onal faces to be polyhedral. Our approach is more flexible and includes, for example, the cone of positive-semidefinite matrices as a special case (this cone is not neighborly in general). We term our generalization Terracini convexity due to its conceptual similarity with the conclusion of Terracinis lemma from algebraic geometry. Polyhedral cones are Terracini convex if and only if they are neighborly. More broadly, we derive many families of non-polyhedral Terracini convex cones based on neighborly cones, linear images of cones of positive semidefinite matrices, and derivative relaxations of Terracini convex hyperbolicity cones. As a demonstration of the utility of our framework in the non-polyhedral case, we give a characterization based on Terracini convexity of the tightness of semidefinite relaxations for certain inverse problems.
A spectral convex set is a collection of symmetric matrices whose range of eigenvalues form a symmetric convex set. Spectral convex sets generalize the Schur-Horn orbitopes studied by Sanyal-Sottile-Sturmfels (2011). We study this class of convex bod
ies, which is closed under intersections, polarity, and Minkowski sums. We describe orbits of faces and give a formula for their Steiner polynomials. We then focus on spectral polyhedra. We prove that spectral polyhedra are spectrahedra and give small representations as spectrahedral shadows. We close with observations and questions regarding hyperbolicity cones, polar convex bodies, and spectral zonotopes.
We describe a new approach to certifying the global nonnegativity of multivariate polynomials by solving hyperbolic optimization problems---a class of convex optimization problems that generalize semidefinite programs. We show how to produce families
of nonnegative polynomials (which we call hyperbolic certificates of nonnegativity) from any hyperbolic polynomial. We investigate the pairs $(n,d)$ for which there is a hyperbolic polynomial of degree $d$ in $n$ variables such that an associated hyperbolic certificate of nonnegativity is not a sum of squares. If $dgeq 4$ we show that this occurs whenever $ngeq 4$. In the degree three case, we find an explicit hyperbolic cubic in $43$ variables that gives hyperbolic certificates that are not sums of squares. As a corollary, we obtain the first known hyperbolic cubic no power of which has a definite determinantal representation. Our approach also allows us to show that, given a cubic $p$, and a direction $e$, the decision problem Is $p$ hyperbolic with respect to $e$? is co-NP hard.
A convex optimization problem in conic form involves minimizing a linear functional over the intersection of a convex cone and an affine subspace. In some cases, it is possible to replace a conic formulation using a certain cone, with a lifted conic
formulation using another cone that is higher-dimensional, but simpler, in some sense. One situation in which this can be computationally advantageous is when the higher-dimensional cone is a Cartesian product of many low-complexity cones, such as second-order cones, or small positive semidefinite cones. This paper studies obstructions to a convex cone having a lifted representation with such a product structure. The main result says that whenever a convex cone has a certain neighborliness property, then it does not have a lifted representation using a finite product of cones, each of which has only short chains of faces. This is a generalization of recent work of Averkov (Optimal size of linear matrix inequalities in semidefinite approaches to polynomial optimization, SIAM J. Appl. Alg. Geom., Vol. 3, No. 1, 128--151, 2019) which considers only lifted representations using products of positive semidefinite cones of bounded size. Among the consequences of the main result is that various cones related to nonnegative polynomials do not have lifted representations using products of low-complexity cones, such as smooth cones, the exponential cone, and cones defined by hyperbolic polynomials of low degree.
We consider a new and general online resource allocation problem, where the goal is to maximize a function of a positive semidefinite (PSD) matrix with a scalar budget constraint. The problem data arrives online, and the algorithm needs to make an ir
revocable decision at each step. Of particular interest are classic experiment design problems in the online setting, with the algorithm deciding whether to allocate budget to each experiment as new experiments become available sequentially. We analyze two greedy primal-dual algorithms and provide bounds on their competitive ratios. Our analysis relies on a smooth surrogate of the objective function that needs to satisfy a new diminishing returns (PSD-DR) property (that its gradient is order-reversing with respect to the PSD cone). Using the representation for monotone maps on the PSD cone given by Lowners theorem, we obtain a convex parametrization of the family of functions satisfying PSD-DR. We then formulate a convex optimization problem to directly optimize our competitive ratio bound over this set. This design problem can be solved offline before the data start arriving. The online algorithm that uses the designed smoothing is tailored to the given cost function, and enjoys a competitive ratio at least as good as our optimized bound. We provide examples of computing the smooth surrogate for D-optimal and A-optimal experiment design, and demonstrate the performance of the custom-designed algorithm.
If $X$ is an $ntimes n$ symmetric matrix, then the directional derivative of $X mapsto det(X)$ in the direction $I$ is the elementary symmetric polynomial of degree $n-1$ in the eigenvalues of $X$. This is a polynomial in the entries of $X$ with the
property that it is hyperbolic with respect to the direction $I$. The corresponding hyperbolicity cone is a relaxation of the positive semidefinite (PSD) cone known as the first derivative relaxation (or Renegar derivative) of the PSD cone. A spectrahedal cone is a convex cone that has a representation as the intersection of a subspace with the cone of PSD matrices in some dimension. We show that the first derivative relaxation of the PSD cone is a spectrahedral cone, and give an explicit spectrahedral description of size $binom{n+1}{2}-1$. The construction provides a new explicit example of a hyperbolicity cone that is also a spectrahedron. This is consistent with the generalized Lax conjecture, which conjectures that every hyperbolicity cone is a spectrahedron.
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, man
y 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 off-the-shelf 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 consider the problem of jointly estimating the attitude and spin-rate of a spinning spacecraft. Psiaki (J. Astronautical Sci., 57(1-2):73--92, 2009) has formulated a family of optimization problems that generalize the classical least-squares attit
ude estimation problem, known as Wahbas problem, to the case of a spinning spacecraft. If the rotation axis is fixed and known, but the spin-rate is unknown (such as for nutation-damped spin-stabilized spacecraft) we show that Psiakis 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 relaxation-based approach to more complicated variations on the problem.
