Face Structure in Partial Facial Reduction of Semidefinite Relaxations of Binary Programs
Semidefinite relaxations of binary optimization problems often fail Slater's condition. Full facial reduction restores strict feasibility but may require auxiliary problems as costly as the original relaxation. We analyze partial facial reduction based on tractable inner approximations of the positive semidefinite cone: the nonnegative diagonal, diagonally dominant (DD), and scaled diagonally dominant (SDD) cones. For this class of SDP relaxations, we prove that every terminal face identified by SDD-partial FR is described by variables fixed to zero or one and groups of variables forced to…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2607.25689
curl -X POST /api/v1/records/arxiv/2607.25689/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2607.25689/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'