{"id":"06c42bda-52de-4141-a4ce-6c9b297a43b5","arxiv_id":"2412.17178","paper_version":1,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":7.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"Multi-period MIQPs with linear dynamics and indicators have projected cost matrices whose inverses are block-tridiagonal; the paper exploits this to give an exact O(n^2)-constraint SOCP formulation and a polynomial shortest-path algorithm.","lead":"This paper gives an exact convex hull and a compact second-order cone reformulation for multi-period quadratic programs with binary action indicators and linear state dynamics, after eliminating the states. It also reduces the side-constraint-free case to a shortest path problem, and reports large speedups on calcium-imaging and hybrid-control benchmarks.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No significant objection identified: the convex-hull and SOCP/shortest-path claims are correct under the stated block-factorizable positive-definite assumptions; the singular-A_i caveat is an explicit scope condition, not an internal flaw.","rationale":"The reader's CONDITIONAL verdict is driven mainly by computational benchmarks, solver numerical errors, and missing code/data, not by a flaw in the central theorem. I agree that the block-factorizable assumption is the narrowest point of the paper, but it is an explicit premise of the model, so I do not treat it as a correctness gap. The theoretical chain from the inverse formula (Proposition 7), through the path-polytope description (Theorem 8), to the SOCP (Proposition 10) and shortest-path (Proposition 9) consequences is internally consistent. The only imported black box, Proposition 1, is a published result and appears to be applied faithfully in Proposition 2. Since the central mathematical claim survives scrutiny, the existing CONDITIONAL verdict should stand on the computational and reproducibility grounds the reader identified, without adding a mathematical objection.","tokens_in":35331,"tokens_out":28533,"duration_ms":252500,"concrete_test":"For n=3, d=2, generate random block-factorizable positive definite Q satisfying Assumption 2, enumerate all 8 supports S to compute the true MIQP optimal value, and compare it against the Proposition 10 SOCP relaxation solved to high precision; any nonzero gap would falsify Theorem 8.","verdict_should_be":"UNCHANGED","load_bearing_attack":"I found no load-bearing mathematical objection to the central claim. Theorem 8 rests on two ingredients: Proposition 1 (imported from Wei et al. [56]) and the exact description of P^B_Q via the path polytope (14). Both are used correctly. The integrality argument in Proposition 5 is sound because (14a) plus (14d) is a network-flow matrix, hence totally unimodular; Proposition 4 and Observation 2 show that the rank-one/rank-d matrices Λ reproduce hat-Q^{-1}_S for every support S. The SOCP reformulation in Proposition 10 is the standard Nesterov–Nemirovskii rotated-cone construction, and Proposition 9's shortest-path reduction is a valid linear-objective minimization over an integral polytope. The one condition the reader flags is that the reduction in Appendix A.3 requires nonsingular A_i and positive definite P_i so that the projected Q has the block structure (16). That is an explicit assumption of the problem class stated in Section 1 and in Assumptions 1–2, not a hidden or violated premise; Theorem 8 itself is conditional on Q being block-factorizable and positive definite, and within that class the argument holds. I therefore do not identify a correctness risk in the central convexification claim.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies a multi-period mixed-integer quadratic program with linear state dynamics and indicator variables on the controls. It projects out the state variables and observes that the resulting quadratic cost matrix is (block-)factorizable when the transition matrices are nonsingular and the weighting matrices are positive definite. For this class it derives a closed-form expression for the inverses of all principal (block-)submatrices as a sum of low-rank matrices indexed by consecutive pairs in the support. Using the Wei--Atamturk--Gomez--Kucukyavuz hull characterization, it then gives an exact closed convex hull of the mixed-integer epigraph in an extended space, expressed by a positive semidefinite constraint and an O(n^2)-sized network-flow path polytope. It further shows that the hull is SOCP-representable and that, without side constraints, the problem reduces to a shortest path problem on a DAG solvable in O(n^2 * pi(d)) time. Two computational case studies, calcium-imaging deconvolution and a hybrid electric vehicle path-following problem, demonstrate the practical impact and also report numerical robustness issues of the conic formulations.","tokens_in":35548,"tokens_out":38170,"duration_ms":334674,"significance":"If the results are correct, this is a substantial contribution to the convexification literature for MIQPs with indicators. The paper identifies a structured class -- (block-)factorizable cost matrices -- for which the exact convex hull, which for general positive definite Q requires an exponential-size polytope in the Wei et al. representation, collapses to a compact polynomial-size description based on a totally unimodular network polytope. The inverse formulas for block-factorizable matrices and their principal submatrices are new and are used in a clean way. The shortest path algorithm for the side-constraint-free case is a genuine polynomial-time result for a nontrivial class of multi-period MIQPs. The paper is also honest about limitations: it explicitly states the nonsingularity/positive-definiteness assumptions under which the block structure exists, it clearly notes where the exact hull does not apply (e.g., the nonnegativity constraint in calcium deconvolution), and it reports numerical failures of the SOCP models.","major_comments":[],"minor_comments":[{"comment":"In the displayed representation, the variable tau is not explicitly constrained to be nonnegative and the dimension of z is not stated; please make clear that z in R^n and tau in R_+, or note that these are implied by the PSD block and the definition of P^B_T.","section":"Section 2, Proposition 2"},{"comment":"The proof that all extreme points of (14) are integral is compressed: after projecting out z and W, one obtains a network-flow polytope in w only, but the argument should explicitly state that the linear map from w to (z,W) is injective, so integrality of w transfers to the original extreme points; as written, the claim that an integral optimal solution exists does not by itself rule out nonintegral extreme points of the extended polytope.","section":"Section 3.2, Proposition 5"},{"comment":"The reduction from (20) to (21) is terse at the point where the paper states that z* is binary in extreme optimal solutions; since (20) is an unbounded SDP set, arguing directly that the value function over P^B_Q is linear and therefore minimized at an integral extreme point of the bounded polytope P^B_Q would be more precise and would avoid relying on extreme points of the unbounded set.","section":"Section 4.1, Proposition 9"},{"comment":"Variables tau_{0j} and h_{0j} are declared for 0 <= i < j <= n+1 but are never used in the conic constraints, which begin at i=1; please restrict the index range or explicitly state that the 0-index variables are unused.","section":"Section 4.2, Proposition 10"},{"comment":"The convention '0f(x/0)' should be written as '0 * f(x/0)' or with a space, since as printed it can be misread as a function name.","section":"Notation, Section 1"},{"comment":"The telescoping step in the computation of Inverse of Xi uses symmetry of U_i V_i^T for all i, not only for i=n as the final sentence suggests; since this symmetry is implied by Assumption 2, it would be helpful to state it explicitly before the computation.","section":"Appendix C, proof of Proposition 7"}],"recommendation":"minor_revision","confidential_remarks":"The paper is a strong fit for a mathematical optimization journal. The central convex-hull, SOCP, and shortest-path claims appear correct under the stated assumptions, and I found no load-bearing mathematical error. The main revision work is expository: tighten the proofs of Propositions 5 and 9 and clean up a few notational and indexing issues. I do not have concerns about novelty or attribution: the paper clearly builds on the Wei et al. hull theorem and the Meurant inverse representation, both of which are independent of the present results."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Core result is correct and worth knowing: for MIQPs with a (block-)factorizable cost matrix, the paper gives an exact convex hull in an extended space, an O(n^2) SOCP, and a shortest-path algorithm that solves the unconstrained case in polynomial time. The novel pieces are Prop. 7 (closed-form inverse as sum of rank-d matrices) and the path-polytope description of P_Q. The d=1 case is mostly an assembly of known tools, but the block generalization is real.\n\nI checked the main arguments: the inverse formula telescopes, the path polytope is integral because it is a network-flow matrix, and the SDP/SOCP equivalence is standard. The paper is honest about scope - nonsingular A_i and positive definite P_i are explicit assumptions, and the nonnegativity case is outside the exact hull. The stress-test note is right: I do not see a load-bearing flaw.\n\nSoft spots are computational and presentational. First, the relaxed calcium experiment compares against a generic MIQP solver but not against the existing DP algorithms for that problem, so the claimed advantage is weaker than stated. Second, the MISOCP routinely hits numerical trouble (suboptimal or infeasible on a noticeable fraction of instances); the paper acknowledges it but doesn't diagnose it. For a theory paper that's tolerable, but it caps the practical claims. Third, minor: no code/data, and the relation to the banded-matrix convexifications in [30,42] is cited but not differentiated.\n\nBottom line: this deserves a serious referee. I'd suggest the referee ask for the DP baseline and a paragraph on the numerical failures. I'll cite the block inverse and the path-polytope construction.","headline":"Solid theory paper: exact convex hull for block-factorizable MIQPs, with correct math and a useful shortest-path algorithm; the computational section oversells by omitting the existing DP baseline.","tokens_in":36139,"tokens_out":2221,"would_cite":true,"duration_ms":21158,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C11","90C20","90C25","90C35","15A09"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper proves that after eliminating state variables via linear dynamics, the mixed-integer epigraph of a multi-period quadratic program with indicator variables has an exact closed convex hull described by one positive semidefinite…","keywords":["mixed-integer quadratic programming","indicator variables","convex hull","block-factorizable matrices","second-order cone programming","shortest path reformulation","multi-period optimization","hybrid system control"],"falsifier":"Generate a random side-constraint-free instance of the original form with n=10, nonsingular A_i and positive definite P_i, compute the value returned by the shortest-path algorithm of Proposition 9, and compare it with exhaustive enumeration of all $2^{10}$ indicator sets, each a small convex quadratic program; any gap between the two optimal values would refute the exactness claim.","tokens_in":35102,"feed_emoji":"🧮","tokens_out":9462,"duration_ms":75671,"temperature":0.7,"pith_summary":"This paper sets out to prove that a broad family of multi-period quadratic programs with fixed-charge indicators, where a state is driven by linear dynamics and an action either is zero or triggers a fixed cost, can be convexified exactly. The route is to eliminate the state variables: the resulting quadratic cost matrix has a special factorizable, or block-factorizable, structure. The paper derives a closed form for the inverse of every principal submatrix of such a matrix as a short sum of low-rank matrices indexed by the arcs of a directed acyclic graph. Combining that with a general hull characterization of quadratic sets with indicators yields an exact description of the mixed-integer epigraph in an extended space, using one positive semidefinite condition and O($n^{2}$) linear path constraints, and the description is shown to be second-order cone representable. If correct, the paper turns a class of problems that branch-and-bound solves poorly into one with a strong exact relaxation that commercial conic solvers handle quickly, and, without side constraints, into a shortest-path problem solvable in polynomial time.","feed_headline":"Exact convex hull found for multi-period indicator quadratic programs","feed_subtitle":"Eliminating states exposes a factorizable cost matrix; the mixed-integer hull becomes O(n^2) conic constraints.","key_machinery":"The engine is a rank decomposition of $Q^{{-1}}$, and of every principal-submatrix inverse, into O($n^{2}$) low-rank pieces indexed by DAG arcs. For scalar factorizable Q, each piece is Λ[i→j] = (u_j/(u_i(u_j v_i - u_i v_j))) (e_i - (u_i/u_j)e_j)(e_i - (u_i/u_j)e_j)^T, and the inverse of every principal submatrix uses only the pieces whose indices are consecutive in the active set; hence the entire family of inverse points is encoded by the path polytope (14). The block version replaces scalars by d×d matrices, with Λ[i→j] = (E_i - E_j $U_j^{{-T}}$ U_i^T)(U_i V_i^T - U_i $U_j^{{-1}}$ V_j U_i^T)^{-1}(E_i - E_j $U_j^{{-T}}$ U_i^T)^T. The positive semidefinite block matrix [W x; x^T τ] enforces τ ≥ x^T Q x whenever W is the inverse of Q[S], and because W is a nonnegative combination of positive semidefinite pieces, the whole hull is SOCP-representable.","core_discovery":"For a positive definite block-factorizable matrix Q = U • V, the central result (Theorem 8) is that the closed convex hull of X^B_Q = {(x,z,τ): τ ≥ x^T Q x, x[i](1-z_i)=0, z∈{0,1}^n} is exactly the set of (x,z,τ) for which there are nonnegative arc weights w and a matrix W satisfying the path-conservation equations (14a), the coupling z_ℓ = sum of incoming arc weights (14b), the identity W = Σ Λ[i→j] w_{ij} (18), and the positive semidefinite condition [[W,x],[x^T,τ]] ⪰ 0. The matrices Λ[i→j] are fixed rank-d matrices built from Q's factors; they are precisely the summands in the closed-form inverse of the principal submatrix Q[S] for the set S of active periods. Thus the hard part of the general hull theorem, the convex hull of inverse-submatrix points, becomes the vertex-arc incidence polytope of paths in a DAG, and the overall hull is polynomially sized. From this description the paper derives a tight SOCP formulation (Proposition 10) and, for the side-constraint-free version, a shortest-path algorithm (Proposition 9).","pith_inferences":["An extension the paper does not pursue: the same arc-based inverse decomposition may apply to banded or tree-structured cost matrices beyond the tridiagonal-inverse class, potentially yielding compact hulls for graph-structured multi-period problems.","We infer from the numerical results that the practical bottleneck has shifted from relaxation quality to numerical stability of the conic solver; the reported infeasible and suboptimal cases suggest that scaled or alternative SOCP representations could be as valuable as the hull itself.","The shortest-path reformulation has a natural linear-programming dual with arc potentials, and that dual may yield a combinatorial separation routine for adding cuts to problems with side constraints; this is implicit in the path polytope but not developed in the paper.","For singular transition matrices or time-varying state dimensions, block-factorizability fails; one could test whether a perturbed or limiting formulation recovers the hull approximately, but the exact statement as written stops at the nonsingular case."],"forward_implications":["For problems of the studied form with additional side constraints, the exact hull of the quadratic-plus-indicator part gives a SOCP relaxation with O(n^2) conic constraints that can be embedded in branch-and-bound; the paper's experiments show nearly zero root gaps and only a handful of branch-and-bound nodes.","In the absence of side constraints, the problem is solvable as a shortest path on a directed acyclic graph in O(n^2 · π(d)) time, where π(d) is the cost of a d×d matrix inversion and multiplication, and in O(n^2) time in the scalar case.","The rank-d decomposition of principal-submatrix inverses gives a finite catalog of O(n^2) precomputable matrices, so the convex hull description can be written down without solving any auxiliary optimization problem.","The settings covered include calcium-imaging deconvolution and hybrid-vehicle path following; in both case studies the MISOCP model solves instances that time out as plain MIQPs, although the conic model occasionally suffers numerical errors.","Because the description exactly convexifies the quadratic-plus-indicator part, adding any additional constraints from the feasible region's side constraints preserves the tightness of that core relaxation; the paper's constrained experiments confirm the resulting relaxation stays strong."],"supporting_citations":[{"why":"Supplies the base hull theorem (Proposition 1) that the paper imports and specializes to factorizable matrices.","marker":"[56]"},{"why":"Provides the recursive expression for the inverse of a factorizable or tridiagonal matrix used to derive the rank-one decomposition in Proposition 3.","marker":"[47]"},{"why":"Shows that inverses of nonsingular block-factorizable matrices are block-tridiagonal, the structural fact the block inverse result extends into closed form.","marker":"[46]"},{"why":"Gives the conic-quadratic representation of a nonnegative sum of positive semidefinite matrices, used to turn the PSD formulation into the SOCP of Proposition 10.","marker":"[48]"},{"why":"Provides the standard topological-order shortest-path method used to prove the polynomial-time algorithm of Proposition 9.","marker":"[24]"},{"why":"Supplies the calcium-imaging generative model and deconvolution setup on which the first case study is built.","marker":"[36]"}],"fun_headline_variants":["Exact hull for indicator quadratic programs via DAG paths","Convex hull of mixed-integer QP solved with O(n^2) conic constraints","Closed-form hull for multi-period quadratic with indicators","Shortest path recovers convex hull of indicator QPs","Tight SOCP for multi-period quadratic indicators"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The construction depends on the projected cost matrix Q being block-factorizable, which for the original multi-period problem holds when each transition matrix A_i is nonsingular, each weight matrix P_i is positive definite, and the state dimension does not change between periods; it also imports the general hull characterization of quadratic sets with indicators as a black box.","fun_headline_variants_meta":{"raw":{"variants":["Exact hull for indicator quadratic programs via DAG paths","Convex hull of mixed-integer QP solved with O(n^2) conic constraints","Closed-form hull for multi-period quadratic with indicators","Shortest path recovers convex hull of indicator QPs","Tight SOCP for multi-period quadratic indicators"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000813,"raw_usage":{"total_tokens":3581,"prompt_tokens":978,"completion_tokens":2603,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":594,"completion_tokens_details":{"reasoning_tokens":2518}},"tokens_in":594,"tokens_out":2603,"duration_ms":15877,"temperature":1.0,"reasoning_tokens":2518,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-11T05:46:09.904206+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Generate a random side-constraint-free instance of the original form with n=10, nonsingular A_i and positive definite P_i, compute the value returned by the shortest-path algorithm of Proposition 9, and compare it with exhaustive enumeration of all $2^{10}$ indicator sets, each a small convex quadratic program; any gap between the two optimal values would refute the exactness claim.","supporting_citations":[{"cited_title":"On the convex hull of convex quadratic optimization problems with indicators","cited_arxiv_id":null,"evidence_quote":"Supplies the base hull theorem (Proposition 1) that the paper imports and specializes to factorizable matrices."},{"cited_title":"Direct and iterative methods for linear systems","cited_arxiv_id":null,"evidence_quote":"Provides the recursive expression for the inverse of a factorizable or tridiagonal matrix used to derive the rank-one decomposition in Proposition 3."},{"cited_title":"A review on the inverse of symmetric tridiagonal and block tridiagonal matrices","cited_arxiv_id":null,"evidence_quote":"Shows that inverses of nonsingular block-factorizable matrices are block-tridiagonal, the structural fact the block inverse result extends into closed form."},{"cited_title":"Interior-point Polynomial Algorithms in Convex Program- ming","cited_arxiv_id":null,"evidence_quote":"Gives the conic-quadratic representation of a nonnegative sum of positive semidefinite matrices, used to turn the PSD formulation into the SOCP of Proposition 10."},{"cited_title":"Single-source shortest paths","cited_arxiv_id":null,"evidence_quote":"Provides the standard topological-order shortest-path method used to prove the polynomial-time algorithm of Proposition 9."},{"cited_title":"Exact spike train inference viaℓ0 optimization","cited_arxiv_id":null,"evidence_quote":"Supplies the calcium-imaging generative model and deconvolution setup on which the first case study is built."}],"review_version":1}