REVIEW 2 major objections 2 minor
Instance-specific linear relaxations of semidefinite optimization problems
T0 review · 2 major / 2 minor · reviewed 2026-05-24 · grok-4.3
Pith's one-line read Commutativity of matrices allows construction of linear relaxations for semidefinite programs that match the SDP optimum under stated conditions and strengthen known bounds for max-cut.
desk verdict Commutativity gives exact SDP-LP value matching and a stronger max-cut LP than the eigenvalue bound, but the relaxed general methodology lacks broad guarantees when matrices do not commute. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
Commutativity between the objective matrix and the linear constraint matrices of the SDP, which reduces the semidefinite feasible set to a polyhedral set whose optimum matches or approximates the SDP value.
What would settle it
An explicit max-cut SDP instance on which the proposed linear program returns a strictly smaller upper bound than the eigenvalue bound would disprove the strengthening claim.
Extended reading notes
Core claim
A generic technique obtains linear relaxations of semidefinite programs with provable guarantees from the commutativity of the constraint and objective matrices; exact agreement between the SDP and linear relaxation holds under identified eigenvector conditions, which can then be relaxed while preserving effective bounds; specialization to the max-cut SDP produces a linear program that both certifies and exceeds the known eigenvalue bound, and the same ideas generate linear programs for the Lovasz theta number and for convex relaxations of quadratically constrained quadratic programs.
Load-bearing premise
Commutativity (or a usable relaxation of it) occurs often enough in the SDPs for max-cut, Lovasz theta, and QCQP relaxations that the derived linear programs remain tight.
Editorial extensions
If this is right
- The linear program for max-cut is at least as strong as the eigenvalue bound and strictly stronger on some instances.
- The same construction yields a linear program for the Lovasz theta number.
- The linear programs serve as warm-starts for polyhedral approximation algorithms solving the original SDPs.
- The approach extends to three families of SDPs arising as convex relaxations of quadratically constrained quadratic programs.
Reading between the lines
- If exact commutativity is infrequent, one could search for nearby commuting bases or low-rank projections to retain instance-specific linear relaxations.
- The technique might apply to other SDP relaxations in combinatorial optimization such as graph partitioning or quadratic assignment.
- Empirical success on moderate-sized instances suggests the linear programs could replace SDP solves in branch-and-bound frameworks when only bounds are needed.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The manuscript introduces a generic technique to obtain linear relaxations of semidefinite programs (SDPs) with provable guarantees based on commutativity of the objective and constraint matrices. It studies conditions for exact matching of optimal values between the SDP and the linear relaxation, relaxes these conditions to a flexible methodology for effective approximations, specializes the results to the Poljak-Rendl SDP for max-cut and the Lovász theta number, proves that the proposed max-cut LP certifies and strengthens a known eigenvalue bound, and demonstrates the use of the LPs to warm-start iterative polyhedral approximations of SDPs through experiments on max-cut, Lovász theta, and QCQP relaxations.
Significance. If the claims hold, the work offers a concrete method for generating instance-specific linear programs that approximate certain SDPs, with a notable strengthening result for the max-cut eigenvalue bound and practical value for warm-starting SDP solvers. The specialization to max-cut and the experimental verification on multiple problem families are strengths; the approach could be useful in optimization if the relaxed methodology retains effectiveness beyond strictly commuting cases.
major comments (2)
- [§3] §3 (relaxation of matching condition): The paper relaxes the exact commutativity-based matching condition to a 'flexible methodology' for effective linear relaxations but provides no general quantitative bound or guarantee on approximation quality when the objective and constraint matrices do not commute; this is load-bearing for the central claim that the technique yields effective approximations for the target problem classes (max-cut, Lovász theta, QCQPs).
- [§5] §5 (max-cut specialization): The proof that the proposed LP certifies the eigenvalue bound and is strictly stronger relies on the Poljak-Rendl formulation matrices permitting simultaneous diagonalization; the manuscript does not clarify whether this holds for arbitrary max-cut instances or only selected ones, which directly affects the scope of the strengthening claim.
minor comments (2)
- [Notation throughout] The notation for the instance-specific linear relaxation (e.g., how the diagonalization is applied per instance) could be made more explicit to aid reproducibility.
- [Experimental section] Table or figure captions in the experimental section would benefit from explicit mention of the number of instances and how commutativity was verified or assumed.
Simulated Author's Rebuttal
We thank the referee for the careful reading and constructive comments on our manuscript. We address each major comment below, indicating revisions where appropriate.
read point-by-point responses
-
Referee: [§3] §3 (relaxation of matching condition): The paper relaxes the exact commutativity-based matching condition to a 'flexible methodology' for effective linear relaxations but provides no general quantitative bound or guarantee on approximation quality when the objective and constraint matrices do not commute; this is load-bearing for the central claim that the technique yields effective approximations for the target problem classes (max-cut, Lovász theta, QCQPs).
Authors: We acknowledge that the manuscript provides no general quantitative bound on approximation quality for non-commuting cases. The exact matching result requires commutativity, while the flexible methodology is offered as a practical heuristic whose effectiveness is supported by the experimental results on max-cut, Lovász theta, and QCQP instances. The central theoretical claims remain tied to the commuting case; the experiments serve to illustrate utility beyond that case. We will revise §3 to explicitly note the absence of general bounds and the reliance on empirical validation for the non-commuting regime. revision: yes
-
Referee: [§5] §5 (max-cut specialization): The proof that the proposed LP certifies the eigenvalue bound and is strictly stronger relies on the Poljak-Rendl formulation matrices permitting simultaneous diagonalization; the manuscript does not clarify whether this holds for arbitrary max-cut instances or only selected ones, which directly affects the scope of the strengthening claim.
Authors: The Poljak-Rendl SDP formulation has the structural property that its objective and constraint matrices permit simultaneous diagonalization for every max-cut instance, independent of the underlying graph. This follows from the diagonal nature of the equality constraints together with the form of the objective matrix (derived from the graph Laplacian). The strengthening result therefore applies to arbitrary instances. We will add an explicit statement and brief justification of this fact in the revised §5. revision: yes
Circularity Check
No circularity: derivation relies on external commutativity property and standard SDP theory.
full rationale
The paper introduces linear relaxations conditioned on commutativity of objective and constraint matrices (an external algebraic property allowing simultaneous diagonalization). Conditions for exact matching between SDP and LP values are derived from this property, then relaxed to a methodology for approximations; specializations to Poljak-Rendl max-cut SDP and Lovász theta use known formulations and prove certification of the eigenvalue bound under the stated commutativity assumption. No step reduces a claimed prediction or guarantee to a fitted parameter, self-defined quantity, or load-bearing self-citation chain inside the paper. The approach remains self-contained against external matrix properties and SDP duality without internal circular reduction.
Assumptions & free parameters
assumptions (1)
- domain assumption Commutativity of constraint and objective matrices provides conditions under which SDP and linear relaxation optimal values match.
Cite this review
Pith. "Pith review of Instance-specific linear relaxations of semidefinite optimization problems." pith.science (2026). https://pith.science/paper/W4XAHCEY
@misc{pith2026230208118,
author = {Pith},
title = {Pith review of: Instance-specific linear relaxations of semidefinite optimization problems},
year = {2026},
howpublished = {\url{https://pith.science/paper/W4XAHCEY}},
note = {Machine review of arXiv:2302.08118}
}
read the original abstract
We introduce a generic technique to obtain linear relaxations of semidefinite programs with provable guarantees based on the commutativity of the constraint and the objective matrices. We study conditions under which the optimal value of the SDP and the proposed linear relaxation match, which we then relax to provide a flexible methodology to derive effective linear relaxations. We specialize these results to provide linear programs that approximate well-known semidefinite programs for the max cut problem proposed by Poljak and Rendl, and the Lovasz theta number; we prove that the linear program proposed for max cut certifies a known eigenvalue bound for the maximum cut value and is in fact stronger. Our ideas can be used to warm-start algorithms that solve semidefinite programs by iterative polyhedral approximation of the feasible region. We verify this capability through multiple experiments on the max cut semidefinite program, the Lovasz theta number and on three families of semidefinite programs obtained as convex relaxations of certain quadratically constrained quadratic problems.
Reviewed May 24, 2026 · model on record in the stance chip above.
Discussion (0). Sign in to comment.