Integer points in arbitrary convex cones: the case of the PSD and SOC cones

• 成果类型: Article; Early Access
• 署名作者: De Loera, Jesus A.; Marsters, Brittney; Xu, Luze; Zhang, Shixuan
• 署名单位: University of California System; University of California Davis; Texas A&M University System; Texas A&M University College Station
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-024-02188-8
• 发表日期: 2025
• 关键词: total dual integrality; REPRESENTATION; semidefinite

摘要

We investigate the semigroup of integer points inside a convex cone. We extend classical results in integer linear programming to integer conic programming. We show that the semigroup associated with nonpolyhedral cones can sometimes have a notion of finite generating set with the help of a group action. We show this is true for the cone of positive semidefinite matrices (PSD) and the second-order cone (SOC). Both cones have a finite generating set of integer points, similar in spirit to Hilbert bases, under the action of a finitely generated group. We also extend notions of total dual integrality, Gomory-Chv & aacute;tal closure, and Carath & eacute;odory rank to integer points in arbitrary cones.