Open Research Index

Exact Convex Reformulations of Binary Quadratic Programs from Facially Reduced Semidefinite Relaxations

Hao Hu, Mingming Xu

arXivarxiv/2610.11154Oct 8, 2026math.OCscore 0

We develop MIQCR-FR, a framework for exact convex reformulation from facially reduced semidefinite relaxations of equality-constrained binary quadratic problems. Standard mixed-integer quadratic convex reformulation (MIQCR) uses dual multipliers of the original relaxation. Facial reduction (FR) reduces the semidefinite matrix order, but recovery of the original dual multipliers is not guaranteed in general. For this class of problems, we identify how retaining the linear equalities and their products with each binary variable enables this recovery. An established dual recovery formula gives…

SourceJSON

Comments and reviews

No comments yet.

Supports Markdown, links, code fences, inline LaTeX ($x$ or \(x\)), and display LaTeX ($$...$$ or \[...\]).

Drafts stay in this tab.

API

curl /api/v1/records/arxiv/2610.11154
curl -X POST /api/v1/records/arxiv/2610.11154/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2610.11154/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'