On the Semidefinite Representability of Continuous Quadratic Submodular Minimization With Applications to Moment Problems

Karthik Natarajan; Samuel Burer

arxiv: 2504.03996 · v2 · submitted 2025-04-04 · 🧮 math.OC

On the Semidefinite Representability of Continuous Quadratic Submodular Minimization With Applications to Moment Problems

Samuel Burer , Karthik Natarajan This is my paper

Pith reviewed 2026-05-22 20:45 UTC · model grok-4.3

classification 🧮 math.OC

keywords continuous quadratic submodular minimizationsemidefinite relaxationmoment problemsdistributionally robust optimizationcovariance boundspolynomial sized SDP

0 comments

The pith

A polynomially sized semidefinite relaxation exactly solves continuous quadratic submodular minimization for dimensions at most three.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper examines the problem of minimizing a continuous quadratic function that is submodular, subject to bounds on the variables. It introduces a semidefinite programming relaxation that uses a polynomial number of variables and constraints. This relaxation is proven to be exact when the dimension is three or less. The approach is then applied to moment problems that appear in distributionally robust optimization and in finding bounds on covariances. A sympathetic reader would care because it provides a tractable way to solve certain nonconvex optimization problems that arise in robust decision making.

Core claim

We study continuous quadratic submodular minimization with bounds and propose a polynomially sized semidefinite relaxation, which is provably tight for dimension n ≤ 3 and empirically tight for larger n. We apply the relaxation to two moment problems arising in distributionally robust optimization and the computation of covariance bounds.

What carries the argument

The polynomially sized semidefinite relaxation that captures the feasible set of the continuous quadratic submodular minimization problem.

If this is right

The relaxation yields exact solutions for the minimization problem when n is at most 3.
It provides a method to solve moment problems in distributionally robust optimization.
It enables computation of covariance bounds via the same relaxation.
The method works empirically even when the dimension exceeds 3.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

If the empirical tightness holds in general, this could provide a scalable method for higher-dimensional instances.
The technique may extend to other classes of submodular functions beyond quadratic ones.
Applications could include additional problems in stochastic programming where moment information is used.

Load-bearing premise

The continuous quadratic function must satisfy the submodular property such that the proposed SDP relaxation exactly captures the feasible set for n ≤ 3.

What would settle it

Finding a counterexample instance with dimension n=3 where the optimal value of the SDP relaxation differs from the true minimum of the quadratic submodular function.

read the original abstract

We study continuous quadratic submodular minimization with bounds and propose a polynomially sized semidefinite relaxation, which is provably tight for dimension $n \le 3$ and empirically tight for larger $n$. We apply the relaxation to two moment problems arising in distributionally robust optimization and the computation of covariance bounds. Accordingly, this research advances the ongoing study of continuous submodular minimization and opens new application areas therein.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper builds a polynomial-size SDP relaxation for continuous quadratic submodular minimization that is proven tight for n ≤ 3 and applied to moment problems in DRO.

read the letter

The main thing to know is that Burer and Natarajan give a polynomially sized SDP for minimizing a continuous quadratic submodular function over box constraints, with a proof of exactness when the dimension is at most 3 and empirical evidence of tightness beyond that. They then use the relaxation on two moment problems that arise in distributionally robust optimization and covariance bounding. The construction itself is the new piece. Standard Shor lifts already produce an SDP of size O(n) for quadratics, so the contribution is the additional structure that folds in the submodularity condition while keeping the size polynomial and without introducing extra solutions in low dimensions. The applications section shows how this can be plugged into existing robust-optimization pipelines, which is a practical plus. The tightness argument for n ≤ 3 is the part that needs the closest look. The claim is that the SDP recovers the true minimum for every bounded quadratic submodular objective in those dimensions, which requires showing that feasible SDP matrices correspond to feasible points of the original problem or that the duality gap vanishes. If the proof proceeds by checking sign patterns or by using dimension-specific properties of 3×3 PSD matrices, it is important to confirm that all boundary cases with the given bounds are covered. The paper states a proof exists, so the argument is presumably there, but any missed case would affect the result. For larger n the empirical checks are useful but do not replace a guarantee. This work is aimed at researchers who already work with continuous submodular problems or who need tractable relaxations inside distributionally robust models. It is not a sweeping theoretical advance, but the explicit SDP and the moment-problem applications are concrete enough that a serious referee should see it. I would recommend sending it out for review.

Referee Report

2 major / 2 minor

Summary. The manuscript proposes a polynomially sized semidefinite programming relaxation for the continuous quadratic submodular minimization problem subject to box constraints. It claims that this relaxation is provably tight (i.e., recovers the exact global minimum) for all instances when the dimension n ≤ 3 and is empirically tight for larger n. The relaxation is then applied to two moment problems arising in distributionally robust optimization and covariance bounding.

Significance. A polynomially sized, provably exact SDP formulation for quadratic submodular minimization in low dimensions would be a useful addition to the continuous submodular optimization literature and would directly enable exact solutions for the cited moment problems when n ≤ 3. The empirical tightness results, if reproducible, would also support practical use of the relaxation beyond n = 3.

major comments (2)

[Main tightness theorem for n ≤ 3] The proof of exactness for n ≤ 3 (presumably in the section containing the main theorem on tightness) must explicitly demonstrate that the added submodularity constraints do not introduce spurious feasible points whose objective value is strictly lower than any feasible point of the original problem. It is not sufficient to appeal only to the standard Shor lift; the argument must rule out all possible rank-deficient or boundary cases for 3 × 3 PSD matrices satisfying the submodularity sign conditions.
[Formulation of the SDP relaxation] The definition of the continuous submodular property (likely Eq. (X) in the preliminaries) and its translation into linear matrix inequalities must be shown to be necessary as well as sufficient for the relaxation to remain outer. If the translation is only sufficient, the claimed tightness for n ≤ 3 cannot hold for all bounded quadratic submodular objectives.

minor comments (2)

Clarify whether the polynomial size of the SDP is O(n^3) or better; the current description leaves the precise scaling ambiguous.
In the numerical section, report the maximum observed relative gap together with the distribution of gaps rather than only average or “empirically tight” statements.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for their careful reading and constructive comments on our manuscript. We address each major comment below and are prepared to revise the paper accordingly to strengthen the presentation and proofs.

read point-by-point responses

Referee: [Main tightness theorem for n ≤ 3] The proof of exactness for n ≤ 3 (presumably in the section containing the main theorem on tightness) must explicitly demonstrate that the added submodularity constraints do not introduce spurious feasible points whose objective value is strictly lower than any feasible point of the original problem. It is not sufficient to appeal only to the standard Shor lift; the argument must rule out all possible rank-deficient or boundary cases for 3 × 3 PSD matrices satisfying the submodularity sign conditions.

Authors: We agree that the current proof sketch would benefit from an explicit case analysis to rule out spurious points. In the revised manuscript we will expand the tightness theorem (Section 4) with a dedicated lemma that performs exhaustive case analysis on all 3×3 PSD matrices satisfying the submodularity sign pattern. The cases will cover rank-1, rank-2, and rank-3 matrices, as well as all boundary configurations where one or more variables attain their box bounds. For each case we will show that any feasible point of the lifted SDP either corresponds to a feasible point of the original problem or cannot attain a strictly lower objective value, thereby confirming that the added linear matrix inequalities do not enlarge the set of attainable objective values beyond the Shor relaxation. revision: yes
Referee: [Formulation of the SDP relaxation] The definition of the continuous submodular property (likely Eq. (X) in the preliminaries) and its translation into linear matrix inequalities must be shown to be necessary as well as sufficient for the relaxation to remain outer. If the translation is only sufficient, the claimed tightness for n ≤ 3 cannot hold for all bounded quadratic submodular objectives.

Authors: The translation is in fact an equivalence. The continuous submodularity condition on a quadratic form is precisely equivalent to the stated sign pattern on the off-diagonal entries of the lifted matrix (i.e., the LMIs are both necessary and sufficient). We will insert a short proposition immediately after the definition of continuous submodularity that proves this equivalence by direct algebraic manipulation of the quadratic coefficients. With this equivalence established, the SDP relaxation remains a valid outer approximation for every bounded quadratic submodular objective, and the tightness claim for n ≤ 3 continues to hold without restriction. revision: yes

Circularity Check

0 steps flagged

No circularity; tightness presented as independent result

full rationale

The abstract states a polynomially sized SDP relaxation is proposed and then shown to be provably tight for n≤3. No equations or claims in the provided text reduce the tightness result to a definition, a fitted parameter renamed as prediction, or a self-citation chain. The derivation chain is therefore self-contained against external verification of the SDP validity and rank-1 recovery arguments.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Abstract-only review provides no explicit free parameters, axioms, or invented entities; the submodularity assumption is implicit but not detailed.

pith-pipeline@v0.9.0 · 5596 in / 953 out tokens · 26023 ms · 2026-05-22T20:45:02.969783+00:00 · methodology

discussion (0)

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

IndisputableMonolith/Foundation/AlexanderDuality.lean alexander_duality_circle_linking echoes

?

echoes
ECHOES: this paper passage has the same mathematical shape or conceptual pattern as the Recognition theorem, but is not a direct formal dependency.

Theorem 1. For n≤3, the SDP relaxation (2) is tight for all submodular data (Q,c).
IndisputableMonolith/Foundation/AlexanderDuality.lean no_circle_linking_high_dim echoes

?

echoes
ECHOES: this paper passage has the same mathematical shape or conceptual pattern as the Recognition theorem, but is not a direct formal dependency.

Lemma 1 ... r(r+1)≤2(a+1) ... r=3 with a≥5

What do these tags mean?

matches: The paper's claim is directly supported by a theorem in the formal canon.
supports: The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends: The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses: The paper appears to rely on the theorem as machinery.
contradicts: The paper's claim conflicts with a theorem or certificate in the canon.
unclear: Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

A second-order cone representable class of nonconvex quadratic programs
math.OC 2025-08 unverdicted novelty 7.0

The authors give sufficient conditions for the convex hull of a lifted sparse nonconvex quadratic program over the unit hypercube to be SOC-representable and identify structural cases yielding a polynomial-size SOC fo...