Semidefinite approximations of conical hulls of measured sets

DOI10.1007/S00454-016-9825-ZzbMATH Open1379.52006arXiv1409.8272OpenAlexW2270965815MaRDI QIDQ512256FDOQ512256

Authors: Julian Romero, Mauricio Velasco 

Publication date: 24 February 2017

Published in: Discrete \& Computational Geometry (Search for Journal in Brave)

Abstract: Let $C$ be a proper convex cone generated by a compact set which supports a measure $mu$. A construction due to A.Barvinok, E.Veomett and J.B. Lasserre produces, using $mu$, a sequence $(P_k{)}_{kinmathbbN}$ of nested spectrahedral cones which contains the cone $C^{\ast }$ dual to $C$. We prove convergence results for such sequences of spectrahedra and provide tools for bounding the distance between $P_k$ and $C^{\ast }$. These tools are especially useful on cones with enough symmetries and allow us to determine bounds for several cones of interest. We compute such upper bounds for semidefinite approximations of cones over traveling salesman polytopes and for cones of nonnegative ternary sextics and quaternary quartics.

Full work available at URL: https://arxiv.org/abs/1409.8272

Recommendations

• Approximations of convex bodies by measure-generated sets
• Semidefinite Representation of Convex Sets and Convex Hulls
• scientific article; zbMATH DE number 3354146
• Semiconvex hulls of quasiconformal sets
• Polyhedral approximations of the semidefinite cone and their application
• Semidefinite Approximation of Closed Convex Set
• Approximation of convex sets by polytopes
• Simultaneous approximation from convex sets
• scientific article; zbMATH DE number 1303653
• On convex and strongly convex approximations of sets

zbMATH Keywords

spectrahedraapproximation of convex bodiesSDr sets

Mathematics Subject Classification ID

Convex programming (90C25) Approximation by convex sets (52A27)

Cites Work

• Title not available (Why is that?)
• Lectures on modern convex optimization. Analysis, algorithms, and engineering applications
• Harmonic Function Theory
• Global optimization with polynomials and the problem of moments
• Title not available (Why is that?)
• Most tensor problems are NP-hard
• The ellipsoid method and its consequences in combinatorial optimization
• Semidefinite programming relaxations for semialgebraic problems
• A New Look at Nonnegativity on Closed Sets and Polynomial Optimization
• Title not available (Why is that?)
• Semidefinite Optimization and Convex Algebraic Geometry
• Semidefinite representations for finite varieties
• On the computational complexity of membership problems for the completely positive cone and its dual
• All 0-1 polytopes are traveling salesman polytopes
• Nonnegative polynomials and sums of squares
• Equivariant Semidefinite Lifts and Sum-of-Squares Hierarchies
• Theta bodies for polynomial ideals
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Convexity properties of the cone of nonnegative polynomials
• How to Integrate a Polynomial over a Sphere
• Der Maßbegriff in der Theorie der kontinuierlichen Gruppen
• A positive semidefinite approximation of the symmetric traveling salesman polytope
• Convex hulls of algebraic sets
• Linearization functors on real convex sets
• Title not available (Why is that?)

Cited In (8)

• Semidefinite Relaxations for Lebesgue and Gaussian Measures of Unions of Basic Semialgebraic Sets
• Best Approximation from the Intersection of a Closed Convex Set and a Polyhedron in Hilbert Space, Weak Slater Conditions, and the Strong Conical Hull Intersection Property
• Evaluating approximations of the semidefinite cone with trace normalized distance
• A positive semidefinite approximation of the symmetric traveling salesman polytope
• Semiconvex hulls of quasiconformal sets
• Bounds for stable measures of convex shells and stable approximations
• On approximatingD-induced polar sets of geometric and extended geometric cones
• On approximations of the PSD cone by a polynomial number of smaller-sized PSD cones

Uses Software

• Macaulay2

This page was built for publication: Semidefinite approximations of conical hulls of measured sets

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q512256)