Solving convex QPs with structured sparsity under indicator conditions

Daniel Bienstock; Tongtong Chen

REVIEW 3 major objections 5 minor 2 cited by

Solving convex QPs with structured sparsity under indicator conditions

T0 review · 3 major / 5 minor · reviewed 2026-08-12 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read This paper claims that a broad class of NP-hard convex quadratic programs with indicator variables becomes polynomial-time approximable when the constraint-block incidence graph has bounded treewidth, via a dynamic program over sketch…

desk verdict New treewidth framework for structured MIQPs, but the DP state for combinatorial constraints is defined with unweighted δ-sums, which breaks for negative coefficients; fixable, yet as written the main theorem is unsupported. read the letter →

arxiv 2411.11722 v1 pith:2PDP5SUE submitted 2024-11-18 math.OC cs.CCcs.DS

Daniel Bienstock , Tongtong Chen This is my paper · ORCID

classification math.OCcs.CCcs.DS MSC 90C1190C2068Q25

keywords mixed-integerquadraticprogrammingindicatorvariablestreewidthdynamiccardinalityconstraintsconvexQCQPNP-hardnessstructuredsparsity

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

The paper studies convex quadratic programs in which disjoint blocks of continuous variables are switched on and off by binary indicators, subject to mixed-integer constraints (convex quadratics) and combinatorial constraints such as cardinality limits. It claims that whenever the graph linking constraints to blocks has bounded treewidth, the problem admits a polynomial-time approximation algorithm: the algorithm returns a solution whose objective is no worse than the true optimum, which satisfies every combinatorial constraint exactly, and which violates each mixed-integer constraint by at most $\max_r |B_r|\varepsilon$. This matters because several practically studied problems—portfolio selection, banded-matrix indicator quadratic programs, and truss topology design—fit the template. The paper also proves that the tractability boundary is tight: even restricted feasibility versions are NP-hard when the graph has pathwidth 2 or when only two linear mixed-integer constraints are present.

What carries the argument

The load-bearing object is the sketch ensemble. A sketch for block $B_i$ is a pair $(\delta,\{\hat k_r\}_{r\in M_i})$ in which $\delta\in\{0,1\}$ says whether the block's indicator is on and each integer $\hat k_r$ buckets the block's contribution to mixed-integer constraint $r$ into intervals of width $\varepsilon$; the sketch's value is the optimum of a small convex QCQP restricted to that block. A feasible sketch ensemble selects one sketch per block so that the bucket sums fit each mixed-integer constraint's budget and the signed indicator sums satisfy each combinatorial constraint. The dynamic program propagates, up a tree decomposition of the constraint-block intersection graph, state pairs $(\{\hat k_r\}_{r\in M_t},\{\hat\kappa_r\}_{r\in C_t})$ summarizing the partial sums in the processed subtree; at a bag with two children it merges states by adding these counters. Lemma 312 asserts that merging in this way is exact, which is the step that carries the whole complexity bound.

What would settle it

Run the dynamic program on the instance whose only combinatorial constraint is $\delta_a+\delta_b-\delta_c\le 0$, with a tree decomposition whose two children contain only blocks $\{a\}$ and $\{b,c\}$. Take the left child state $\delta_a=1$ (so $\hat\kappa=1$) and the right child state $\delta_b=1$, $\delta_c=0$ (also $\hat\kappa=1$). The merge in Lemma 312 accepts total $\hat\kappa=2$, which lies in the interval $[-1,2]$ allowed by (15b) and matches Definition 39(d), yet the true signed sum is $1+1-0=2>0$, violating the constraint. If the algorithm returns the ensemble built from this merge as feasible, that is a counterexample to the DP's correctness.

Watch

Extended reading notes

Core claim

On its own terms, the paper establishes a fixed-parameter-style theorem. For problem QIB, let $\omega$ be the treewidth of the constraint-block intersection graph, $\kappa$ the largest support of a combinatorial constraint, and $m_c$ the number of combinatorial constraints. Theorem 14 states that for any $0<\varepsilon<1$ there is an algorithm running in time $O((n+m)(2/\varepsilon)^{2\omega+2\kappa^2\min\{m_c,\omega+1\}})$ plus the cost of solving $O(|B|(2/\varepsilon)^\omega)$ convex QCQPs, each with at most $\omega+1$ constraints, that either proves infeasibility or outputs a vector which is superoptimal (value no larger than the true optimum), feasible for all combinatorial constraints, and has maximum infeasibility at most $\max_r |B_r|\varepsilon$ over mixed-integer constraints. The proof builds a minimum-value sketch ensemble and assembles it by dynamic programming over a tree decomposition. The negative results are reductions from SUBSET SUM: feasibility with a cardinality constraint is NP-hard even when the incidence graph has pathwidth 2, and the full problem is NP-hard even with only two linear mixed-integer constraints plus a cardinality constraint.

Load-bearing premise

The dynamic program's correctness depends on the assumption that, for each combinatorial constraint, a single integer recording how many blocks are active in the processed subtree completely determines that subtree's contribution to the constraint, even when the constraint has negative coefficients.

Editorial extensions

If this is right

For cardinality-constrained portfolio optimization with a low-rank quadratic term and $O(1)$ linear constraints, the theorem gives a polynomial-time algorithm whose output is superoptimal, satisfies the cardinality constraint exactly, and violates the linear constraints by at most $\varepsilon$ per incident-block count.
For convex quadratic problems with banded matrices and indicator variables, the method gives an $O(n(2/\varepsilon)^{2k})$ algorithm when the bandwidth is $k$, an alternative to the existing real-time method.
For truss topology design with a bounded-treewidth constraint-block graph, approximate solutions can be computed in polynomial time even though testing feasibility exactly is NP-hard at pathwidth 2.
The algorithm either certifies infeasibility or produces the $\varepsilon$-feasible, superoptimal vector described in Theorem 14, so the approximation guarantee does not require guessing the active-block set in advance.
The NP-hardness results mark the boundary of this approach: bounded treewidth alone is insufficient once a cardinality constraint is added, and two linear constraints plus cardinality already make the problem weakly NP-hard.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The paper does not discuss the consequence that if exact merging requires signed counters rather than a single active-block count, the DP state would grow from $\kappa^2$ to something exponential in $\kappa$ or in the coefficient range, so the theorem's runtime would change.
A testable extension would be an empirical comparison on QPLIB instances such as 5925: run the sketch DP with modest $\varepsilon$ and check whether the superoptimal objective and $\varepsilon$-infeasible solution beat commercial solvers' 3% gap in wall-clock time; the paper reports no experiments.
Because the infeasibility guarantee is additive in the number of incident blocks, applying the theorem to constraints that touch many blocks requires rescaling $\varepsilon$ by $1/\max_r|B_r|$; the paper leaves this rescaling implicit.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Dear colleague,

The genuinely new idea here is the constraint-block intersection graph plus a sketch-based dynamic program for convex QIBs with indicator variables and combinatorial constraints. That is a real extension of the treewidth approach in [4], and the NP-hardness reductions from SUBSET SUM are clean and self-contained. If the main theorem held, this would be a useful general tool for structured MIQPs that previous treewidth methods could not touch, because blocks can be arbitrarily large.

But there is a load-bearing flaw in Definition 39(d). The DP state for a combinatorial constraint r is κ̂_r, defined as the unweighted sum of δ_i over blocks in the subtree. The actual combinatorial constraint is ∑ v_i^r δ_i ≤ b_r with v_i^r ∈ {0,1,-1}. Take a leaf covering a single block with v_i^r = -1 and δ_i = 1: the signed contribution is -1, feasible in many cases, but (d) forces κ̂_r = 1, which violates the upper bound in (15b) (which is 0 for that leaf). That state is discarded, so the DP cannot represent feasible solutions using negatively signed blocks. Lemma 312 merges states by adding κ̂ values, which is only valid when all v_i^r = +1. This is not a peripheral typo; it is the state definition used in the correctness proof of Theorem 14.

I also want to give credit where it is due: the sketch construction respects the row-scaling assumption, the complexity analysis is careful, and the hardness results are solid. The good news is that the fix is straightforward — define κ̂_r as the signed sum ∑ v_i^r δ_i, which is what (15b) actually bounds, and the merge works because subtrees are disjoint. Nothing I saw requires the unweighted version.

This paper deserves a serious referee and a revision. I would not cite the current version in my own work until the DP state is fixed, but the framework is worth watching. Bring it to the reading group if you want a concrete case of a small definitional slip breaking a treewidth DP.

Referee Report

3 major / 5 minor

Summary. The paper studies convex quadratic programs in which blocks of continuous variables are activated by binary indicators, with constraints split into mixed-integer constraints (carrying quadratic/linear terms in the continuous variables) and combinatorial constraints (with coefficients v_i^r in {0,1,-1} on the indicators). The main contribution is a treewidth-parameterized approximation scheme: under a normalized scaling assumption, the authors define per-block convex QCQP sketches and combine them by dynamic programming on the constraint-block intersection graph. Theorem 14 claims a running time of O((n+m)(2/ε)^{2ω+2κ^2 min{mc,ω+1}}) plus per-block sketch solves to either certify infeasibility or return a superoptimal solution that satisfies all combinatorial constraints and violates mixed-integer constraints by at most max_r |B_r| ε. The paper also gives two NP-hardness reductions from SUBSET SUM for very restricted cases, and discusses applications to portfolio optimization, banded quadratic programs, and truss topology design.

Significance. If the main theorem is correct, the paper provides a clean parameterized approximation framework for a broad class of structured MIQPs, with the attractive feature that combinatorial constraints are enforced exactly while mixed-integer constraints are violated only by an additive amount controlled by ε. The proof strategy is coherent, mostly self-contained, and does not rely on fitted constants or external assumptions; the per-block sketch idea is natural, and the hardness reductions are elementary and appear sound. The potential value is substantial, since many practical sparse/QP models fit the QIB form. However, the correctness of the DP state for combinatorial constraints and the claimed polynomial-time consequences for the applications currently need repair before the results can be accepted as stated.

major comments (3)

[Definition 39 / Lemma 312] Definition 39(d) states ∑_{i∈β_t} δ_i = κ̂_r, but the actual combinatorial constraint is ∑_{i∈β_t} v_i^r δ_i ≤ b_r with v_i^r ∈ {0,1,-1}, and the declared range in (15b) is a bound on the signed quantity. As written, the state is not a sufficient statistic: for a block with v_i^r = -1 and δ_i = 1, condition (d) increments κ̂_r while the signed contribution is -1, so a feasible solution using that block may be discarded. The merging rule in Lemma 312, which adds κ̂ values across children, is valid only for v_i^r = +1. This is load-bearing for Theorem 14: the DP recurrence can undercount the optimum unless (d) is replaced by ∑_{i∈β_t} v_i^r δ_i = κ̂_r (with corresponding changes in the merge equations), or a separate proof is given that the unweighted δ-sum is recoverable from the state.
[Lemma 21 / Lemma 22] The application results are claimed as polynomial-time consequences, but the displayed complexity in Lemma 21 contains an exponent of 2n²: in the portfolio model the cardinality constraint has support κ = n, so a direct application of the Theorem 14 bound is O(n(2/ε)^{2ω+2n²}), which is not polynomial in n. Lemma 22 inherits the same issue, since the orthogonality and cardinality constraints again have O(n) support. The paper should state the precise parameter regime for the polynomial-time claim, either by treating κ as a fixed parameter or by proving a sharper DP bound in which the combinatorial state ranges are bounded by the size of the current bag/subtree rather than by the global support κ.
[Theorem 14 / Lemma 314] The complexity estimate appears inconsistent with the state-count argument. Lemma 314 bounds the number of Π states by (2/ε)^{|M_t|} (max_{r∈C_t}|B_r|)^{|C_t|} ≤ (2/ε)^{ω+1} κ^{min{mc,ω+1}}. When combining two children, the enumeration of pairs of child states squares this quantity, giving roughly (2/ε)^{2ω+2} κ^{2 min{mc,ω+1}}. The printed formula in Theorem 14 and Lemma 314 instead displays an exponent of the form 2ω + 2κ² min{mc,ω+1}, which does not follow from that bound. The authors should reconcile the displayed exponent with the actual DP state enumeration, or provide the precise derivation of the stated complexity.

minor comments (5)

[Lemma 37(c)] Lemma 37(c) states that every node of T has degree ≤ 2, but Case 2 in Section 3.1 describes a node with two children, so the intended statement is that every node has at most two children (equivalently, degree at most 3 in the rooted tree).
[Lemma 38, Eq. (12a)] The quantification 'for all r ∈ β_t' in equation (12a) is not meaningful because β_t is a set of blocks; it should read 'for each mixed-integer constraint r contained in T_t'.
[Lemma 312, Eq. (17a)] In the last two lines of equation (17a), the notation for the combinatorial state uses ˜k_r where the context requires ˜κ_r; the equality κ̂_r = ˜κ_r should be stated consistently.
[Section 5 Glossary] The glossary entry for R_t says 'Ct ∪ Rt', which is circular; it should be 'Ct ∪ Mt' as in Definition 310.
[Footnote 3, page 2] The footnote claims the results extend to combinatorial constraints with integral v_i^r in a fixed range, but Definition 39 and Lemma 312 do not explicitly handle this extension; if retained, the extension should be justified in the DP proof.

Circularity Check

0 steps flagged · score 1.0 of 10

No significant circularity: main algorithm and hardness results are derived from first principles; author self-citations are contextual only.

full rationale

The derivation chain for Theorem 14 is self-contained. The sketch-ensemble formulation (Definitions 31-33 and Lemmas 34-35) is defined directly from problem (1), and the approximation factors follow from Assumption 13 and the epsilon-quantization of mixed-integer constraint slacks; no parameter is fitted to the quantity later reported as a prediction. The DP correctness (Lemmas 311-314) operates on these sketches and on the given tree-decomposition, and the complexity bound counts the state space from (15), using kappa, mc, and omega as instance inputs. The NP-hardness results (Lemmas 41-42) are proved by explicit polynomial reductions from SUBSET SUM, not by appeal to prior work. The only self-citations are [3] (a literature pointer for cardinality-constrained optimization) and [4] (a comparison of treewidth setups); neither supplies a load-bearing premise of Theorem 14 or of the lower bounds. The skeptical concern about Definition 39(d), that the DP state sums unweighted delta_i for combinatorial constraints while feasibility uses signed coefficients v_i^r, is a potential correctness gap in the proof as written, not a circularity: it does not make any output equivalent to an input by construction. Accordingly the circularity score is low.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

No fitted parameters or invented physical or mathematical entities. The only free input is ε, the user-chosen accuracy parameter, which is not fitted to data. The axioms are standard computational assumptions plus the normalization assumption for the problem class.

assumptions (4)

domain assumption Assumption 13: variables can be transformed to [0,1] and each mixed-integer constraint normalized to L1 coefficient norm 1.
Invoked in Section 1 and used in the proof of Lemma 38 to bound the sum of block contributions by 1; the paper says it is obtained via change of variables and scaling.
standard math A tree-decomposition of given width can be found or used in linear time (folklore).
Used in Section 3 to set up the DP; the paper notes it is folklore.
standard math Convex QCQPs with O(ω) constraints can be solved in polynomial time.
The algorithm calls for solving O(|B|(2/ε)^ω) convex QCQPs; the paper does not discuss the underlying solver oracle, but this is a standard result.
domain assumption Eigen-decomposition of the quadratic term is provided as input for portfolio reformulations.
Stated explicitly in Section 2.1, bypassing numerical linear algebra concerns; this is an input assumption for the application, not the core Theorem 14.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Solving convex QPs with structured sparsity under indicator conditions." pith.science (2026). https://pith.science/paper/2PDP5SUE

@misc{pith2026241111722,
  author       = {Pith},
  title        = {Pith review of: Solving convex QPs with structured sparsity under indicator conditions},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/2PDP5SUE}},
  note         = {Machine review of arXiv:2411.11722}
}

read the original abstract

We study convex optimization problems where disjoint blocks of variables are controlled by binary indicator variables that are also subject to conditions, e.g., cardinality. Several classes of important examples can be formulated in such a way that both the objective and the constraints are separable convex quadratics. We describe a family of polynomial-time approximation algorithms and negative complexity results.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 2 Pith papers

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

Coordinate Optimality Reformulation for Mixed-Integer Convex Programs with Indicators
math.OC 2026-08 conditional novelty 7.0 of 10

A reformulation that injects coordinate-optimality conditions into indicator MIPs sharply cuts branch-and-bound work and yields polynomial tree bounds in several structured cases.
Rank-one convexification for quadratic optimization problems with step function penalties
math.OC 2025-04 conditional novelty 7.0 of 10

An explicit convex hull for rank-one quadratic optimization with step function penalties is derived, enabling stronger copositive and SDP relaxations and a robust convex SVM surrogate.

Reference graph

Works this paper leans on

10 extracted references · 9 canonical work pages · cited by 2 Pith papers

[4]

Bienstock, D., Mu˜ noz, G.: LP Formulations for Polynomial Optimization Problems. SIAM J. Optimization 28(2), 1121–1150 (2018)

work page 2018
[1]

SIAM Journal on Optimization 3(2), 322–358 (1993)

Ben-Tal, A., Bendsøe, M.P.: A new method for optimal truss topol- ogy design. SIAM Journal on Optimization 3(2), 322–358 (1993). https://doi.org/10.1137/0803015, https://doi.org/10.1137/0803015

work page doi:10.1137/0803015 1993
[2]

Informs J

Bertsimas, D., Cory-Wright, R.: A scalable algorithm for sparse portfolio selection. Informs J. Computing 34, 1489–1511 (2022)

work page 2022
[3]

Mathematical Programming 74, 121–140 (1996)

Bienstock, D.: Computational study of a family of mixed-i nteger quadratic pro- gramming problems. Mathematical Programming 74, 121–140 (1996)

work page 1996
[5]

In: Lepist¨ o, T., Salomaa, A

Bodlaender, H.L.: Dynamic programming on graphs with bou nded treewidth. In: Lepist¨ o, T., Salomaa, A. (eds.) Automata, Languages and Pr ogramming, Lecture Notes in Computer Science, vol. 317, pp. 105–118. Springer B erlin Heidelberg (1988)

work page 1988
[6]

Mathematical Programming Computation 11(2), 237–265 (Jun 2019)

Furini, F., Traversi, E., Belotti, P., Frangioni, A., Gle ixner, A., Gould, N., Liberti, L., Lodi, A., Misener, R., Mittelmann, H., Sahi nidis, N., Vigerske, S., Wiegele, A.: Qplib: a library of quadratic pro gramming in- stances. Mathematical Programming Computation 11(2), 237–265 (Jun 2019). https://doi.org/10.1007/s12532-018-0147-4 , publisher Copyrigh...

doi:10.1007/s12532-018-0147-4 2019
[7]

Golub, G.H., Van Loan, C.F.: Matrix computations, vol. 3. JHU Press (2012)

work page 2012
[8]

arXiv:2 405.03051 pp

G´ omez, A., Han, S., Lozano, L.: Real-time solution of qua dratic optimization prob- lems with banded matrices and indicator variables. arXiv:2 405.03051 pp. 1–30 (2024)

work page 2024

Show all 10 references

[9]

Mathematical Progr amming 124, 183–205 (2010)

G¨ unl¨ uk, O., Linderoth, J.: Perspective reformulation s of mixed integer nonlin- ear programs with indicator variables. Mathematical Progr amming 124, 183–205 (2010)

2010
[10]

John Wiley & Sons, Inc., New York, NY, USA (1986)

Schrijver, A.: Theory of Linear and Integer Programming . John Wiley & Sons, Inc., New York, NY, USA (1986)

1986

Pith tools

Reviewed August 12, 2026 · model on record in the stance chip above.

[1] [4]

Bienstock, D., Mu˜ noz, G.: LP Formulations for Polynomial Optimization Problems. SIAM J. Optimization 28(2), 1121–1150 (2018)

work page 2018

[2] [1]

SIAM Journal on Optimization 3(2), 322–358 (1993)

Ben-Tal, A., Bendsøe, M.P.: A new method for optimal truss topol- ogy design. SIAM Journal on Optimization 3(2), 322–358 (1993). https://doi.org/10.1137/0803015, https://doi.org/10.1137/0803015

work page doi:10.1137/0803015 1993

[3] [2]

Informs J

Bertsimas, D., Cory-Wright, R.: A scalable algorithm for sparse portfolio selection. Informs J. Computing 34, 1489–1511 (2022)

work page 2022

[4] [3]

Mathematical Programming 74, 121–140 (1996)

Bienstock, D.: Computational study of a family of mixed-i nteger quadratic pro- gramming problems. Mathematical Programming 74, 121–140 (1996)

work page 1996

[5] [5]

In: Lepist¨ o, T., Salomaa, A

Bodlaender, H.L.: Dynamic programming on graphs with bou nded treewidth. In: Lepist¨ o, T., Salomaa, A. (eds.) Automata, Languages and Pr ogramming, Lecture Notes in Computer Science, vol. 317, pp. 105–118. Springer B erlin Heidelberg (1988)

work page 1988

[6] [6]

Mathematical Programming Computation 11(2), 237–265 (Jun 2019)

Furini, F., Traversi, E., Belotti, P., Frangioni, A., Gle ixner, A., Gould, N., Liberti, L., Lodi, A., Misener, R., Mittelmann, H., Sahi nidis, N., Vigerske, S., Wiegele, A.: Qplib: a library of quadratic pro gramming in- stances. Mathematical Programming Computation 11(2), 237–265 (Jun 2019). https://doi.org/10.1007/s12532-018-0147-4 , publisher Copyrigh...

doi:10.1007/s12532-018-0147-4 2019

[7] [7]

Golub, G.H., Van Loan, C.F.: Matrix computations, vol. 3. JHU Press (2012)

work page 2012

[8] [8]

arXiv:2 405.03051 pp

G´ omez, A., Han, S., Lozano, L.: Real-time solution of qua dratic optimization prob- lems with banded matrices and indicator variables. arXiv:2 405.03051 pp. 1–30 (2024)

work page 2024