Polyhedral approximation of spectrahedral shadows via homogenization

DOI10.1007/S10957-023-02363-5arXiv2305.16909OpenAlexW4390949947WikidataQ129743861 ScholiaQ129743861MaRDI QIDQ6150652FDOQ6150652

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)

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.

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

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

zbMATH Keywords

homogenizationpolyhedral approximationspectrahedral shadowsunbounded convex sets

Mathematics Subject Classification ID

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

Cites Work

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

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)