An algorithm for minimum cardinality generators of cones

2024/12/02 by Mayer, Matthias Georg, Fabian von der Warth, von der Warth, Fabian
Computer Science · #90C25 #FOS: Mathematics #Metaheuristic Optimization Algorithms Research #Optimization and Control (math.OC) #Robotic Path Planning Algorithms #Rough Sets and Fuzzy Logic

paper · pdf · doi:10.48550/arxiv.2412.01451

openalex publication_date 2024/12/02 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

This paper presents a novel proof that for any convex cone, the size of conically independent generators is at most twice that of minimum cardinality generators. While this result is known for linear spaces, we extend it to general cones through a decomposition into linear and pointed components. Our constructive approach leads to a polynomial-time algorithm for computing minimum cardinality generators of finitely generated cones, improving upon existing methods that only compute conically independent generators.

Related

• Limitations on the expressive power of convex cones without long chains\n of faces
• Replacing projection on finitely generated convex cones with projection on bounded polytopes
• Identifying Maximal Non-Redundant Integer Cone Generators
• Another Proof of the Fact that Polyhedral Cones are Finitely Generated
• Normalizations of factorizations over convex cones and their effects on extension complexity