{"id":"bbf9efc7-c6e1-457f-b1cb-57a8448e1841","arxiv_id":"2606.22894","paper_version":1,"verdict":"UNVERDICTED","confidence":"LOW","novelty_score":7.0,"correctness_risk":"unknown","formal_verification":"none","parameter_count":0,"one_line_summary":"Introduces SC-SDP relaxation for sparse indefinite QPs that matches SDP-RLT bound quality with smaller matrix size, derives dual-based presolving, and solves via Riemannian augmented Lagrangian exploiting cone projection.","lead":"The paper proposes a sparsity-cone SDP relaxation (SC-SDP) for sparse quadratic programs using an (n+1)-dimensional matrix plus one sparsity-cone constraint, proving equivalence to the larger SDP-RLT relaxation while enabling presolving rules and a Riemannian solver. A smart generalist might read it because sparse QPs appear in feature selection, portfolio design, and network problems where tighter or faster relaxations could scale global optimization.","discovery_kind":"new_method","skeptic_critique":{"model":"grok-4.3","headline":"No significant objection identified","rationale":"The reader's weakest assumption concerns the one-dimensional projection subproblem, which is relevant to computational claims but not to the equivalence proof that constitutes the strongest claim. Because the equivalence is presented as a proved result and no counter-example or gap in the lifting argument is visible, the projection detail does not affect the load-bearing status of the equivalence statement.","tokens_in":1729,"tokens_out":274,"duration_ms":24024,"concrete_test":"Select a small indefinite sparse QP (n=4 or 5) with known optimal value; solve both the SC-SDP and SDP-RLT formulations to optimality with an SDP solver and check whether the optimal values agree to machine precision.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim is a proof that the SC-SDP formulation (n+1 matrix plus single sparsity-cone constraint K) is equivalent in strength to the standard SDP-RLT relaxation ((2n+1) matrix). The manuscript states that structural characterizations of K are derived and that projection onto K reduces to a one-dimensional subproblem; these support the solver and presolving sections but are not required for the equivalence statement itself. No internal inconsistency, hidden assumption in the lifting, or unsupported step in the claimed equivalence is apparent.","agreement_with_reader":"disagree"},"referee_report":{"model":"grok-4.3","summary":"The paper proposes a sparsity-cone SDP (SC-SDP) relaxation for sparse indefinite quadratic programs. It replaces the standard SDP-RLT lifting (a (2n+1)-dimensional PSD matrix) with an (n+1)-dimensional PSD matrix plus a single constraint that the lifted vector lies in a new sparsity cone K. The central claims are that SC-SDP is equivalent in strength to SDP-RLT, that K admits useful structural characterizations, that projection onto K reduces to a one-dimensional subproblem, and that the dual of SC-SDP yields explicit presolving rules (variable fixing, screening cuts, dual refinement). A two-phase Riemannian augmented Lagrangian solver is developed that exploits the projection structure, and numerical tests on several sparse QP classes are reported.","tokens_in":1856,"tokens_out":348,"duration_ms":14952,"significance":"If the equivalence and projection results hold, the work supplies a strictly smaller SDP formulation that preserves bound quality while enabling cheaper projection steps and dual-based presolving; both are practically relevant for global optimization of sparse QPs. The explicit derivation of presolving certificates from the dual and the structured solver constitute concrete algorithmic contributions.","major_comments":[],"minor_comments":[{"comment":"Abstract, last sentence: the clause 'and exploits the structured projection subproblems' is grammatically incomplete; rephrase for clarity.","section":null},{"comment":"The manuscript would benefit from an explicit statement (early in the introduction or after the equivalence theorem) of the precise dimension reduction achieved and any hidden assumptions on the support pattern that are required for the cone K to be well-defined.","section":null}],"recommendation":"accept","confidential_remarks":null},"author_rebuttal":{"model":"grok-4.3","summary":"We thank the referee for their positive assessment of the manuscript, including the recognition of the equivalence between SC-SDP and SDP-RLT, the utility of the sparsity cone projection, and the value of the dual-based presolving and Riemannian solver. We appreciate the recommendation to accept.","responses":[],"tokens_in":1334,"tokens_out":75,"duration_ms":6980,"standing_objections":[]},"desk_editor":{"model":"grok-4.3","letter":"The main takeaway is a new SC-SDP relaxation that replaces the usual (2n+1)-matrix SDP-RLT lift with an (n+1)-matrix plus a single sparsity-cone constraint K, and the authors prove the two give the same bound. They also give structural facts about K, reduce projection onto K to a one-dimensional subproblem, and pull out explicit dual-based presolving steps (variable fixing, screening cuts, dual refinement). A two-phase Riemannian augmented Lagrangian solver is built around the structure.\n\nThe equivalence claim and the projection result are the genuinely new pieces; the presolving rules follow directly from the dual and are not just re-packaged standard tricks. If the proof is clean, the size reduction is a real win for memory and time on larger sparse QPs. The experiments are said to keep the bound quality while cutting compute, which matches what the formulation promises.\n\nThe soft spots are modest. The one-dimensional projection claim needs to hold in floating point for the claimed speedups, and the Riemannian solver may still need careful implementation details to be reproducible. The presolving rules are derived cleanly but their practical hit rate will depend on instance distribution; the paper should show that clearly rather than just on selected cases.\n\nThis is for people working on convex relaxations for sparse quadratic programs in statistics, finance, or design. The work is coherent on its own terms and the central claims are falsifiable, so it deserves a serious referee even if revisions are needed on the solver section.","headline":"SC-SDP matches SDP-RLT strength with a smaller matrix plus one cone constraint, plus dual presolving rules that look practical.","tokens_in":2311,"tokens_out":380,"would_cite":true,"duration_ms":11040,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"grok-4.3","headline":"The sparsity-cone SDP relaxation equals SDP-RLT in strength for sparse quadratic programs but uses only an (n+1)-dimensional matrix.","keywords":["sparse quadratic programs","semidefinite programming relaxation","sparsity cone","variable fixing","presolving","augmented Lagrangian method"],"falsifier":"A concrete sparse quadratic program instance on which the optimal value of the SC-SDP relaxation is strictly weaker than the optimal value of the SDP-RLT relaxation.","tokens_in":2653,"feed_emoji":"","tokens_out":657,"duration_ms":26062,"temperature":0.7,"pith_summary":"The paper introduces a sparsity-cone semidefinite programming relaxation for quadratic programs with an l0-norm constraint on the decision variables. It proves that this SC-SDP formulation delivers the same relaxation strength as the standard SDP-RLT approach. SC-SDP replaces the usual (2n+1)-dimensional matrix with a smaller (n+1)-dimensional matrix plus one sparsity-cone constraint. The authors characterize the cone, show that projection onto it reduces to a one-dimensional subproblem, and extract dual-based presolving rules for variable fixing and support screening. They also give a Riemannian augmented Lagrangian solver that exploits the structure for faster computation on sparse QPs.","feed_headline":"Sparsity-cone SDP matches SDP-RLT strength for sparse QPs","feed_subtitle":"Smaller (n+1) matrix plus dual rules enable equivalent bounds with faster solving and variable presolving","key_machinery":"The sparsity cone K that relaxes the l0-norm constraint inside the (n+1)-dimensional lifted space.","core_discovery":"The central claim is that the SC-SDP relaxation, which employs an (n+1)-dimensional semidefinite matrix together with a single sparsity-cone constraint K to handle the l0-norm, is equivalent in strength to the SDP-RLT relaxation. The paper derives structural properties of K that permit efficient projection and uses the dual of SC-SDP to obtain explicit presolving mechanisms, including a dual-fixing rule for individual variables and a screening-cut rule for excluding larger support patterns.","pith_inferences":["The smaller matrix dimension may allow SC-SDP to handle larger n than SDP-RLT before memory or time limits are reached.","The derived presolving rules could be embedded inside branch-and-bound frameworks for global solution of sparse QPs.","Closed-form solutions for the one-dimensional projection subproblem might exist for special sparsity patterns."],"forward_implications":["SC-SDP can replace SDP-RLT without loss of bound quality on sparse QPs.","Efficient projection onto K enables first-order and augmented Lagrangian solvers.","Dual information directly yields variable-fixing and support-screening rules that reduce problem size before optimization.","The two-phase Riemannian method solves the relaxation faster than standard interior-point methods on the tested instances."],"fun_headline_variants":["SC-SDP equals SDP-RLT strength with n+1 matrix for sparse QPs","Sparsity-cone SDP matches SDP-RLT bounds using smaller matrix","SC-SDP enables dual variable fixing and screening cuts for QPs","Equivalent SC-SDP relaxation with efficient projection onto sparsity cone"],"cache_read_input_tokens":2112,"weakest_assumption_plain":"Projection onto the sparsity cone K can be computed efficiently via a one-dimensional subproblem.","fun_headline_variants_meta":{"raw":{"variants":["SC-SDP equals SDP-RLT strength with n+1 matrix for sparse QPs","Sparsity-cone SDP matches SDP-RLT bounds using smaller matrix","SC-SDP enables dual variable fixing and screening cuts for QPs","Equivalent SC-SDP relaxation with efficient projection onto sparsity cone"]},"model":"grok-4.3","cost_usd":0.004414,"raw_usage":{"total_tokens":2167,"prompt_tokens":749,"num_sources_used":0,"completion_tokens":78,"cost_in_usd_ticks":44140500,"prompt_tokens_details":{"text_tokens":749,"audio_tokens":0,"image_tokens":0,"cached_tokens":64},"completion_tokens_details":{"audio_tokens":0,"reasoning_tokens":1340,"accepted_prediction_tokens":0,"rejected_prediction_tokens":0}},"tokens_in":749,"tokens_out":78,"duration_ms":10289,"temperature":1.0,"reasoning_tokens":1340,"cache_read_input_tokens":64,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-06-26T07:52:28.802551+00:00","model_set":{"reader":"grok-4.3"},"falsifier":"A concrete sparse quadratic program instance on which the optimal value of the SC-SDP relaxation is strictly weaker than the optimal value of the SDP-RLT relaxation.","supporting_citations":[],"review_version":1}