{"id":"509e1dfb-79be-456e-b8d4-1b1d0f37a581","arxiv_id":"2411.16015","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":4,"one_line_summary":"A primal interior point method, accelerated by preconditioned iterative solvers, can outperform primal-dual IPM in the final iterations of many linear and semidefinite programs.","lead":"This paper shows that a pure primal interior point method can beat the standard primal-dual method on some linear and semidefinite programs by exploiting the stability of its scaling matrix near convergence. The authors build a hybrid solver that switches to primal IPM for the final iterations and report speedups on benchmark LPs and SDPs.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 3.3's total complexity is not proven as stated: Appendix C assumes the iteration is already in the stable regime (μ1 below the Theorem 3.2 threshold) and a cached factorization is available, so the O(n^3 k*) initial-phase cost is asserted, not derived.","rationale":"The reader's CONDITIONAL verdict is appropriate, but the sharpest load-bearing concern is not only that A2 may fail on benchmark instances; it is that the proof of the headline complexity theorem does not establish the stated result. Appendix C proves a warm-start statement and leaves the O(n^3 k*) initial-phase cost asserted rather than derived. This is an internal proof gap, not a disagreement with consensus: the stability insight of Theorem 3.2 is plausible, and the empirical speedups are informative, but the theoretical 'when' claim is weaker than advertised. The A2 restriction remains a genuine scope limitation, and the lack of condition-number or non-degeneracy checks in the experiments means the theory-practice bridge is not fully validated. Since both concerns support the same CONDITIONAL verdict already given by the reader, no verdict change is needed.","tokens_in":22546,"tokens_out":12943,"duration_ms":122807,"concrete_test":"Re-derive the proof of Theorem 3.3 under its actual hypotheses: start from an arbitrary feasible initial μ1 and track how many times Algorithm 2 factorizes before the Theorem 3.2 threshold is reached, and whether Lemmas C.3–C.4 control the inexact-direction error during that early phase. If the early phase cannot be bounded by O(n^3 k*) total cost, then Theorem 3.3 must be revised to a warm-start complexity statement, and the advertised total-complexity claim is unsupported.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The paper's headline theoretical contribution is Theorem 3.3: Algorithm 2 has total arithmetic complexity O(n^3 k* + n^{2.5} log^2(1/ε)). The proof is deferred to Appendix C, but Theorem C.1 does not prove that statement. Its hypothesis is not 'run Algorithm 2 from an arbitrary feasible start'; it requires μ1 < sqrt(λ*)/(40 sqrt(n) γ) (1 + ||A_N||/sqrt(λ_min(A_B^T A_B)))^{-1}, δ(x1, μ1) ≤ 1/2, and uses a cached factorization of M_{x1}. That is exactly the warm-start, stable regime after k* in Theorem 3.2. Nothing in Appendix C bounds the number or cost of iterations needed to reach that regime under Algorithm 2: Lemma C.4's error bound uses λ_min(A X^2 A^T) ≥ λ*/4, which is only valid after the stable phase begins, so the inexact-solver analysis cannot be applied to early iterations. The n^3 k* term is therefore an unproven assertion about a phase that is never analyzed. The standard primal IPM analysis cited for that phase assumes exact solves, not the cached-iterative procedure of Algorithm 2. Independently, the whole analysis relies on A2: if the LP is degenerate and λ* = 0, the condition-number bound of Theorem 3.2 fails even in the warm-start regime. The experiments do not verify A2 or measure the preconditioned condition numbers on the MIPLIB instances, so the empirical speedups are not explicitly connected to the theoretical regime.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper revisits the primal barrier interior point method for linear optimization and argues that, near convergence, the primal normal matrices M_{X_k} = A X_k^2 A^T are stable: under assumptions A1 and A2 (nonempty relative interiors, full row rank A, and primal nondegeneracy with |B| = m), Theorem 3.2 states that the preconditioned condition number κ(M_{X_k}^{-1/2} M_{X_j} M_{X_k}^{-1/2}) ≤ 9 for all j ≥ k ≥ k^*. This motivates Algorithms 2 and 3, which cache a factorization of one normal matrix and use it as a preconditioner for iterative solves of later normal equations. The claimed payoff is a total arithmetic complexity O(n^3 k^* + n^{2.5} log^2(1/ε)) for the preconditioned primal IPM. Numerical experiments on 924 MIPLIB LP relaxations and on SDP benchmark instances show that a hybrid primal-dual/primal IPM speeds up a subset of instances, and Section 5.4 offers a qualitative taxonomy of IPM convergence patterns.","tokens_in":22876,"tokens_out":5934,"duration_ms":58264,"significance":"If the stability theorem is correct, it is a genuinely useful structural observation: it identifies a concrete reason why a primal scaling can outperform primal-dual scaling near convergence, and it gives a principled preconditioning strategy for normal-equation solves. The paper's experimental reporting is honest about the limited regime of benefit: 744 of 924 instances fall into cases C1/C2, and the reported speedups for the remaining instances are moderate and carefully qualified. The proofs in Appendix B are mostly self-contained and the dependence of the constants on λ^* and γ is explicit rather than fitted. However, two issues are load-bearing for the paper's central claim: the formal complexity theorem in Appendix C does not prove the initial-phase term in Theorem 3.3, and the experiments do not verify the nondegeneracy assumption A2 on which all the theoretical guarantees rest. These gaps do not destroy the empirical contribution, but they mean the paper currently overstates the connection between its provable stability regime and its numerical results.","major_comments":[{"comment":"Theorem C.1 does not prove Theorem 3.3 as stated in the main text. The formal theorem assumes the iteration starts in the stable regime: μ1 below the threshold of Theorem 3.2, δ(x1, μ1) ≤ 1/2, and a cached factorization. Its proof invokes λ_min(A X^2 A^T) ≥ λ^*/4, which is only valid after the stable phase has begun. Consequently, the O(n^3 k^*) initial-phase cost in Theorem 3.3 is asserted, not derived: nothing in Appendix C bounds the number or cost of the iterations needed to reach the stable regime under Algorithm 2's inexact, cached-iterative solves. The standard primal IPM analysis cited for that phase assumes exact solves, so it cannot be applied directly to Algorithm 2. Please either prove the missing phase bound or restate Theorem 3.3 as a warm-start result with the initial-phase term removed.","section":"§C.4 / Theorem C.1"},{"comment":"Assumption A2 is load-bearing for all of the stability and complexity results: Lemma 3.1, Theorems 3.1, 3.2, 3.3, and C.1 all rely on the maximal complementarity partition satisfying |B| = m so that λ^* = λ_min(M_{X^*}) > 0. For degenerate LPs, λ^* can be zero and the condition-number bound of Theorem 3.2 fails even in the warm-start regime. The experiments in Section 5.2 apply the hybrid solver to MIPLIB instances without checking nondegeneracy and without reporting the preconditioned condition numbers, so the observed speedups are not explicitly connected to the proved theoretical regime. To close this gap, the authors should at least report λ_min of the relevant normal matrices (or another degeneracy measure) for the instances on which primal IPM is invoked, or restrict the theoretical claims to the regime in which A2 is verified.","section":"§3.1 / §5.2"},{"comment":"The warm-start index k^* in Theorem 3.2 and the complexity bound in Theorem 3.3 depend on constants that are not available to a solver: λ^*, γ, ∥A_N∥/sqrt(λ_min(A_B^T A_B)), and ∥A∥. The practical algorithm instead switches heuristically on ∥x_k − x_{k−1}∥_{x_k,ν} ≤ 10^{-1} and a time-ratio threshold of 30. This is acceptable for an experimental paper, but the text should state explicitly that Theorem 3.3 is an existence-level result that does not translate into an implementable guarantee for the switching rule, and that the rule is validated only empirically.","section":"§3.2 / §5.2"}],"minor_comments":[{"comment":"The sentence preceding Theorem 3.3 contains a typo: 'yeilds' should be 'yields'. Also, Theorem 3.3 is labeled 'Informal' but no formal statement is given in the main text; the formal statement appears only as Theorem C.1 in Appendix C, which makes the main-text claim hard to check.","section":"§3.2"},{"comment":"In the proof of Lemma C.3, the displayed inequality after (26) reads 'δ(x_+, μ) ≤ √2 δ(x_+, μ)^2 + ...'; the first δ(x_+, μ) on the right should be δ(x, μ). As written, the line is self-referential and the square-root step is unclear.","section":"§C.3 / Lemma C.3"},{"comment":"The small-multiple plots in Figures 2–4 would be much easier to verify if they had axis labels, legends, and consistent scales; the current captions do not explain how the 'scaled' distance is computed for primal-dual iterates in the same way as Definition 4.","section":"§5.4 / Figures 2–4"},{"comment":"The threshold ν in Definition 4, the update tolerance θ in Algorithm 3, and the switch parameters 0.1 and 30 in Section 5.2 are introduced without any sensitivity analysis; a brief study of how results depend on these parameters would strengthen the empirical claims.","section":"Definition 4 / Algorithm 3"},{"comment":"The text says 'Only six instances slow down when primal IPM is invoked and passes the test', but Table 1 contains several additional negative speedup entries (for example neos-885524, graph40-20-1rand, and supportcase29); the sentence should either quantify the criterion precisely or refer to the table for the exact count.","section":"§5.2 / Table 1"}],"recommendation":"major_revision","confidential_remarks":"The paper has two separable contributions: a conditional stability theorem for the primal normal matrix and an empirical demonstration of a hybrid primal-dual/primal solver. The empirical part is honest and potentially useful, but the main-text complexity claim is not proven by the appendix theorem, and the theory-experiment link is not validated because assumption A2 is not checked. I would suggest telling the authors that the complexity claim can be repaired by relabeling Theorem 3.3 as a warm-start result or by adding the missing initial-phase analysis, and that adding degeneracy/condition-number statistics for the invoked MIPLIB instances would materially strengthen the paper. I do not see this as a reject: the stability observation and the practical heuristic are worth publishing once the claims are aligned with the proofs."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Read this paper: it has a genuinely useful idea for accelerating the late iterations of an IPM solver, but the headline complexity theorem is not fully proven as stated, and the empirical baseline is a textbook primal-dual implementation rather than a commercial solver.\n\nWhat is new: the paper observes that under primal non-degeneracy the primal normal matrix M_X = A X^2 A^T becomes stable near the optimum, so a cached factorization of an earlier iterate serves as a good preconditioner for later normal equations. The condition-number bound in Theorem 3.2 (≤9 after k* iterations) is plausible and well-motivated. The thresholded scaled distance and delayed scaling matrix are a clever workaround to handle coordinates that converge to zero or to large values, and the hybrid primal/primal-dual scheme is sensible. The SDP results, with up to 10x speedups on constraints-heavy instances, are the most interesting part. The authors are honest that primal IPM should complement, not replace, primal-dual IPM, and they cite the earlier stability result (Güler et al.) rather than claiming it as new.\n\nThe soft spots are the following. First, the total-complexity theorem (Theorem 3.3) is not proven as written. Appendix C's formal statement (Theorem C.1) assumes the iteration is already in the stable regime: μ1 below the threshold, δ(x1, μ1) ≤ 1/2, and a cached factorization available. The O(n^3 k*) cost for the earlier phase is asserted from standard primal IPM analysis, but that analysis assumes exact solves, not the iterative procedure of Algorithm 2. The paper should either prove a bound for the full algorithm or state the complexity as a warm-start result. Second, Assumption A2 (non-degeneracy) is load-bearing: if λ* = 0 the condition-number bound fails. The experiments do not check non-degeneracy on the MIPLIB instances, so the connection between the theoretical regime and the empirical speedups is not established. The paper should at least discuss how often A2 is expected to hold and how the algorithm behaves without it. Third, the LP comparison is against a textbook primal-dual IPM inside the same codebase, not against Gurobi or COPT. That is a fine proof of concept, but it is not evidence that the hybrid beats a state-of-the-art solver. Minor issues: some implementation thresholds (ν, θ, switch parameters) are heuristic and not all are disclosed precisely.\n\nOverall, the core stability idea is solid, the paper is well-written, and the empirical claims are made honestly. The gaps are fixable. This deserves a serious referee: I would send it to review, with the expectation that the complexity claim be corrected or re-stated and the degeneracy issue discussed. For an IPM reading group, it is worth reading.","headline":"A useful hybrid IPM idea with a real gap in the headline complexity theorem and an unverified non-degeneracy assumption.","tokens_in":23447,"tokens_out":3292,"would_cite":true,"duration_ms":30444,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C05","90C51","65F08"],"pacs":[],"model":"deepseek-v4-flash","headline":"The primal interior point method can beat primal-dual near convergence by reusing one factorization as a preconditioner.","keywords":["interior point method","linear programming","primal method","normal matrix","preconditioning","conjugate gradient","central path","semidefinite programming"],"falsifier":"Solve a degenerate LP where an optimal solution has a zero coordinate in every optimal basis, so $\\lambda_* = 0$, with the paper's preconditioned primal IPM and track $\\kappa(M_{X_k}^{-1/2} M_{X_j} M_{X_k}^{-1/2})$; observing the bound exceed 9, or the conjugate-gradient iteration count failing to stay near $O(\\log(1/\\varepsilon))$ despite closeness in the thresholded distance, would overturn the stability claim.","tokens_in":22307,"feed_emoji":"⚡","tokens_out":9996,"duration_ms":73164,"temperature":0.7,"pith_summary":"The paper argues that the classic primal interior point method, long overshadowed by the primal-dual variant, has a hidden advantage in the final phase of solving a linear program. As the iterate sequence converges, the primal normal matrix $M_X = AX^2A^T$ settles down and stops changing, so a single cached factorization can precondition every later linear solve. The central theorem bounds the preconditioned condition number by 9 once the barrier parameter is small enough, which turns the per-iteration cost of solving the normal equations from $O(n^3)$ to $O(n^2)$ with a Krylov solver. If this holds, a hybrid solver that starts with primal-dual and switches to primal IPM near convergence should be faster on a broad class of LPs; experiments on hundreds of benchmark instances and on semidefinite programs with many constraints support that expectation.","feed_headline":"One cached matrix factorization cuts IPM solve cost to quadratic","feed_subtitle":"After enough iterations the primal normal matrix stops changing, so later solves reuse one preconditioner at O(n^2).","key_machinery":"The load-bearing object is the primal normal matrix $M_X = AX^2A^T$, the coefficient matrix of the normal equations whose solution produces the primal IPM search direction. Its stability is controlled by two proximity notions: Euclidean distance between iterates, which via Lemma 3.2 turns a close iterate into a good preconditioner, and the thresholded scaled distance of Definition 4, which handles coordinates that are large or tending to zero by mixing the Euclidean and scaled geometries. The delayed scaling matrix $W$ with $w_S = x_S$ and $w_L = z_L$ is the device that lets one cached factorization of $M_Z$ serve future iterates $x$ while the shifted scaling theorem keeps the surrogate direction accurate.","core_discovery":"The central claim is that the primal normal matrix $M_{X_k} = AX_k^2A^T$ is stable under primal IPM convergence: Theorem 3.2 states that $\\kappa(M_{X_k}^{-1/2} M_{X_j} M_{X_k}^{-1/2}) \\le 9$ for all $j \\ge k \\ge k^*$, so after a threshold number of iterations one cached factorization of an earlier normal matrix serves as a uniformly good preconditioner for all later normal equations. The paper constructs a hybrid algorithm that uses primal-dual IPM until medium accuracy and then switches to the primal IPM with a delayed scaling matrix, which combines Euclidean proximity for preconditioning with scaled-distance proximity for an accurate search direction. The result is an $O(n^3 k^* + n^{2.5}\\log^2(1/\\varepsilon))$ complexity bound for primal non-degenerate LPs and a demonstrated speedup on benchmark LP instances and on SDPs with many constraints.","pith_inferences":["The stability argument should also hold when the barrier parameter is reduced adaptively rather than by a fixed schedule, so an adaptive step-size primal IPM might reach the preconditionable regime in fewer iterations.","The non-degeneracy assumption suggests the benefit of primal IPM is most pronounced on LPs with a unique primal optimum; on degenerate or badly scaled instances the condition number bound may degrade, and a practical solver would need a fallback to fresh factorizations.","A testable consequence: on instances where the primal-dual solver already converges superlinearly in one or two iterations, switching to primal IPM should give no speedup; a prospective study could quantify the optimal iteration at which to switch."],"forward_implications":["The per-iteration cost of the final IPM phase drops from $O(n^3)$ for a fresh factorization to $O(n^2)$ for a preconditioned Krylov solve, giving the hybrid algorithm its speedup.","A primal-dual solver can be modified to switch to primal IPM mid-run by caching one factorization and using iterative refinement; the paper's hybrid does this and reports a speedup on most of the 139 instances where both solvers pass.","For semidefinite programs with far more constraints than variables, the saving is larger because forming and factoring the normal matrix dominates the cost; the paper reports up to 10x speedup on such SDPs.","The complexity bound $O(n^3 k^* + n^{2.5}\\log^2(1/\\varepsilon))$ shows the iterative-solver phase has only logarithmic dependence on the accuracy target."],"supporting_citations":[{"why":"Supplies the primal logarithmic barrier method and the outer-iteration complexity analysis used in the proof of the final complexity bound.","marker":"[34]"},{"why":"Supplies the shifted scaling theorem that lets a surrogate search direction computed with a different scaling matrix stay accurate.","marker":"[21]"},{"why":"Supplies the central path proximity framework and the near-center bound used to show the iterates cluster once the barrier parameter is small.","marker":"[33]"},{"why":"Supplies the maximal complementarity partition and the bound that non-basic coordinates of the central path are $O(\\mu)$.","marker":"[23]"},{"why":"Supplies the complexity of preconditioned conjugate gradient: $O(n^2\\log(1/\\varepsilon))$ per solve once the preconditioned condition number is bounded.","marker":"[35]"},{"why":"Documents the instability of the primal-dual normal matrix and the comparative stability of the primal normal matrix, motivating the paper's focus.","marker":"[22]"},{"why":"Supplies the 924 benchmark LP instances used to measure the hybrid solver's speedup.","marker":"[17]"},{"why":"Supplies the semidefinite benchmark instances with many constraints used to test the SDP extension.","marker":"[31]"}],"fun_headline_variants":["Stable primal normal matrix reuses one preconditioner","After threshold, one factorization handles all IPM steps","Primal IPM beats dual when matrix stabilizes","Cached preconditioner drops IPM cost to quadratic","Hybrid IPM: primal-dual then primal with cached scaling"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is the paper's assumption A2: the primal problem is non-degenerate, so the optimal primal solution is unique and the smallest eigenvalue $\\lambda_*$ of the limiting normal matrix is strictly positive.","fun_headline_variants_meta":{"raw":{"variants":["Stable primal normal matrix reuses one preconditioner","After threshold, one factorization handles all IPM steps","Primal IPM beats dual when matrix stabilizes","Cached preconditioner drops IPM cost to quadratic","Hybrid IPM: primal-dual then primal with cached scaling"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000407,"raw_usage":{"total_tokens":2071,"prompt_tokens":857,"completion_tokens":1214,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":473,"completion_tokens_details":{"reasoning_tokens":1135}},"tokens_in":473,"tokens_out":1214,"duration_ms":8608,"temperature":1.0,"reasoning_tokens":1135,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T13:38:27.644816+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Solve a degenerate LP where an optimal solution has a zero coordinate in every optimal basis, so $\\lambda_* = 0$, with the paper's preconditioned primal IPM and track $\\kappa(M_{X_k}^{-1/2} M_{X_j} M_{X_k}^{-1/2})$; observing the bound exceed 9, or the conjugate-gradient iteration count failing to stay near $O(\\log(1/\\varepsilon))$ despite closeness in the thresholded distance, would overturn the stability claim.","supporting_citations":[{"cited_title":"A polynomial method of approximate centers for linear programming","cited_arxiv_id":null,"evidence_quote":"Supplies the primal logarithmic barrier method and the outer-iteration complexity analysis used in the proof of the final complexity bound."},{"cited_title":"Properties of the central points in linear programming problems","cited_arxiv_id":null,"evidence_quote":"Supplies the shifted scaling theorem that lets a surrogate search direction computed with a different scaling matrix stay accurate."},{"cited_title":"Wiley Chichester, 1997","cited_arxiv_id":null,"evidence_quote":"Supplies the central path proximity framework and the near-center bound used to show the iterates cluster once the barrier parameter is small."},{"cited_title":"Convergence behavior of interior-point algorithms.Mathematical Program- ming, 60(1-3):215–228, 1993","cited_arxiv_id":null,"evidence_quote":"Supplies the maximal complementarity partition and the bound that non-basic coordinates of the central path are $O(\\mu)$."},{"cited_title":"Degeneracy in interior point methods for linear programming: a survey","cited_arxiv_id":null,"evidence_quote":"Documents the instability of the primal-dual normal matrix and the comparative stability of the primal normal matrix, motivating the paper's focus."},{"cited_title":"Christophel, Kati Jarck, Thorsten Koch, Jeff Linderoth, Marco Lübbecke, Hans D","cited_arxiv_id":null,"evidence_quote":"Supplies the 924 benchmark LP instances used to measure the hybrid solver's speedup."},{"cited_title":"Benchmarking optimization software-a (hi) story","cited_arxiv_id":null,"evidence_quote":"Supplies the semidefinite benchmark instances with many constraints used to test the SDP extension."}],"review_version":1}