Semidefinite approximations of conical hulls of measured sets

DOI10.1007/S00454-016-9825-ZMaRDI QIDQ512256zbMATH OpenOpenAlexFDO

Authors Julian Romero, Mauricio Velasco

Publication date 24 February 2017

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

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

zbMATH Keywords

spectrahedraapproximation of convex bodiesSDr sets

Mathematics Subject Classification ID

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

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.

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

Cites work

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

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

Describes a project that uses

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)