Polyhedral approximation of spectrahedral shadows via homogenization

DOI10.1007/S10957-023-02363-5MaRDI QIDQ6150652zbMATH OpenOpenAlexWikidataFDO

Authors Daniel Dörfler, Andreas Löhne

Publication date 9 February 2024

Published in Journal of Optimization Theory and Applications (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

homogenizationpolyhedral approximationspectrahedral shadowsunbounded convex sets

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Approximation by convex sets (52A27)

Abstract: This article is concerned with the problem of approximating a not necessarily bounded spectrahedral shadow, a certain convex set, by polyhedra. By identifying the set with its homogenization the problem is reduced to the approximation of a closed convex cone. We introduce the notion of homogeneous {delta}-approximation of a convex set and show that it defines a meaningful concept in the sense that approximations converge to the original set if the approximation error {delta} diminishes. Moreover, we show that a homogeneous {delta}-approximation of the polar of a convex set is immediately available from an approximation of the set itself under mild conditions. Finally, we present an algorithm for the computation of homogeneous {delta}-approximations of spectrahedral shadows and demonstrate it on examples.

Recommendations

• On the approximation of unbounded convex sets by polyhedra
• Spectrahedral approximations of convex hulls of algebraic sets
• Generic Spectrahedral Shadows
• Some recent developments in spectrahedral computation
• On approximatingD-induced polar sets of geometric and extended geometric cones

Cites work

• scientific article; zbMATH DE number 4216876 (Why is no real title available?)
• scientific article; zbMATH DE number 477581 (Why is no real title available?)
• scientific article; zbMATH DE number 823382 (Why is no real title available?)
• scientific article; zbMATH DE number 2205688 (Why is no real title available?)
• A Benson-type algorithm for bounded convex vector optimization problems with vertex selection
• A unifying polyhedral approximation framework for convex optimization
• Approximation algorithms and semidefinite programming.
• Continuity of Some Convex-Cone-Valued Mappings
• Convex Analysis
• Convex analysis for optimization. A unified approach
• Convex and Discrete Geometry
• Distances between closed convex cones: old and new results
• On the approximation of unbounded convex sets by polyhedra
• Primal and dual approximation algorithms for convex vector optimization problems
• Semidefinite Optimization and Convex Algebraic Geometry
• Semidefinite Representation of Convex Sets and Convex Hulls
• Some geometric results in semidefinite programming
• The Schur complement and its applications
• The Supporting Hyperplane Method for Unimodal Programming
• The extended supporting hyperplane algorithm for convex mixed-integer nonlinear programming
• The homogenization cone: polar cone and projection
• Tractability of convex vector optimization problems in the sense of polyhedral approximations
• Variational Analysis

This page was built for publication: Polyhedral approximation of spectrahedral shadows via homogenization

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