Open Research Index

Sparse Cuts for the Positive Semidefinite Cone

Oktay Günlük, Paul Jünger, Jeff Linderoth, Andrea Lodi, James Luedtke

arXivarxiv/2603.09864Mar 10, 2026math.OCscore 0

We consider optimization problems containing nonconvex quadratic functions for which semidefinite programming (SDP) relaxations often yield strong bounds. We investigate linear inequalities that outer approximate the positive semidefinite cone and are sparse in the sense that they are supported only on the variables corresponding to products of variables present in quadratic functions. We show that these sparse linear inequalities yield an LP relaxation that gives the same bound as the SDP relaxation. We demonstrate how to identify these inequalities via a separation procedure that involves…

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