pith. sign in

arxiv: 2409.14715 · v2 · submitted 2024-09-23 · 🧮 math.OC

A New Crossover Algorithm for LP Inspired by the Spiral Dynamic of PDHG

Tianhao Liu , Haihao Lu This is my paper

Pith reviewed 2026-05-23 20:52 UTC · model grok-4.3

classification 🧮 math.OC
keywords linear programmingPDHGcrossover algorithmspiral dynamicsprimal-dual hybrid gradientvertex solutionfirst-order methodsbasis change
0
0 comments X

The pith

PDHG iterates on LPs trace a spiral with closed form that directly yields a crossover to vertex solutions.

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

The paper establishes that, while the active basis stays fixed, PDHG produces iterates whose trajectory admits an exact closed-form expression and decomposes into two orthogonal parts: a rotation that tightens primal and dual feasibility and a forward shift that reduces the duality gap. The authors characterize the discrete events that change the basis and then turn the entire geometric picture into a crossover procedure that starts from any optimal solution and returns a basic optimal solution. This route bypasses the pivot operations of the simplex method. Experiments on standard LP test sets indicate that the resulting procedure is practical and can serve as an alternative to existing crossover techniques.

Core claim

When the variable basis remains unchanged, PDHG iterates exhibit a spiral pattern with a closed-form solution. This spiral consists of two orthogonal components: rotation, which improves primal and dual feasibility, and forward movement, which advances the duality gap. The situations that trigger basis changes are characterized, and the spiral view is used to construct a crossover algorithm that recovers a vertex solution from an arbitrary optimal LP solution without relying on simplex machinery.

What carries the argument

The spiral trajectory of PDHG iterates under fixed basis, decomposed into rotation and forward-movement components whose closed-form expressions drive the crossover steps.

If this is right

  • Any optimal solution produced by a first-order method such as PDLP can be post-processed into a vertex solution by following the spiral dynamics rather than simplex pivots.
  • The same geometric decomposition supplies an explicit rule for detecting and handling basis changes during the crossover phase.
  • Because the rotation and forward components are orthogonal, the procedure can improve feasibility and optimality gap independently at each step.
  • Numerical tests on standard LP instances show that the method recovers vertex solutions in practice and can therefore serve as a drop-in replacement for traditional crossover routines.

Where Pith is reading between the lines

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

  • The same spiral analysis could be applied to other primal-dual first-order methods whose fixed-point operators admit similar orthogonal decompositions.
  • The closed-form expression under fixed basis may allow sharper local convergence rates to be derived for PDHG on linear programs.
  • Extending the crossover logic to quadratic or conic programs would require only that the corresponding first-order method exhibit an analogous spiral when the active set is fixed.

Load-bearing premise

The observed spiral dynamics and basis-change events of PDHG can be turned into a reliable numerical procedure that produces a vertex solution from any optimal point.

What would settle it

Apply the crossover procedure to a collection of optimal but non-basic LP solutions and verify whether every output is a basic feasible solution whose objective matches the known optimum; failure on even a modest fraction of instances would refute the claim that the method reliably yields vertices.

Figures

Figures reproduced from arXiv: 2409.14715 by Haihao Lu, Tianhao Liu.

Figure 1
Figure 1. Figure 1: Primal trajectories of different LP methods. [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: The spiral behavior of PDHG. The whole trajectory of the primal-dual solution (x, y) is shown in Figure 2a, which can be divided into four phases. • Phase 1 (in purple) – The first 16 steps form a huge arc while moving forward. Then PDHG hits the x1 = 0 plane and a basis change event happens. – During Phase 1, we have B = {1, 2} and N = ∅. • Phase 2 (in green) – During iterations from steps 17 to 21, PDHG … view at source ↗
Figure 3
Figure 3. Figure 3: Three typical cases for the basis change in the first quadrant. [PITH_FULL_IMAGE:figures/full_fig_p010_3.png] view at source ↗
read the original abstract

Motivated by large-scale applications, there is a recent trend of research on using first-order methods for solving LP. Among them, PDLP, which is based on a primal-dual hybrid gradient (PDHG) algorithm, may be the most promising one. In this paper, we present a geometric viewpoint on the behavior of PDHG for LP. We demonstrate that PDHG iterates exhibit a spiral pattern with a closed-form solution when the variable basis remains unchanged. This spiral pattern consists of two orthogonal components: rotation and forward movement, where rotation improves primal and dual feasibility, while forward movement advances the duality gap. We also characterize the different situations in which basis change events occur. Inspired by the spiral behavior of PDHG, we design a new crossover algorithm to obtain a vertex solution from any optimal LP solution. This approach differs from traditional simplex-based crossover methods. Our numerical experiments demonstrate the effectiveness of the proposed algorithm, showcasing its potential as an alternative option for crossover.

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.

Referee Report

2 major / 1 minor

Summary. The paper analyzes the geometric behavior of the primal-dual hybrid gradient (PDHG) method on linear programs. It claims that, when the variable basis is fixed, PDHG iterates follow a spiral trajectory admitting a closed-form solution; this trajectory decomposes into orthogonal rotation (improving primal/dual feasibility) and forward movement (reducing the duality gap). The authors characterize the events that trigger basis changes and, motivated by the spiral dynamics, construct a new crossover procedure that starts from an arbitrary optimal solution and produces a vertex solution. Numerical experiments are reported to demonstrate the practical effectiveness of this crossover as an alternative to classical simplex-based methods.

Significance. A rigorously derived closed-form description of PDHG dynamics together with a provably terminating crossover would supply both theoretical insight into first-order LP solvers and a practical tool for recovering basic optimal solutions without invoking the simplex method. The geometric decomposition into rotation and translation components, if accompanied by explicit formulas and a correctness argument that survives basis changes, would be a notable contribution to the literature on PDHG and PDLP-style solvers.

major comments (2)
  1. [crossover algorithm description (likely §4–5)] The central claim that the observed spiral dynamics plus the basis-change characterization yield a reliable crossover procedure (abstract and the section introducing the algorithm) rests on the assertion that the procedure reaches a vertex solution from any optimal point. However, the spiral closed-form holds only while the basis is unchanged; once a basis change occurs the iterates leave the closed-form regime. No invariant, potential function, or termination argument is supplied showing that the resulting procedure must terminate at a basic feasible solution rather than cycle or require an external pivot rule. This is load-bearing for the claim that the method constitutes a complete, simplex-free crossover.
  2. [geometric analysis of PDHG iterates] The abstract states that a closed-form spiral solution is demonstrated when the basis remains unchanged, yet the provided text supplies neither the derivation of the closed-form expression nor the explicit decomposition into orthogonal rotation and forward components. Without these equations (presumably in the geometric-analysis section), the foundation for both the basis-change characterization and the subsequent algorithm design cannot be verified.
minor comments (1)
  1. [numerical experiments] The experimental section should include a precise description of the test instances, termination criteria, and any error or iteration-count statistics; the current abstract-level statement that the algorithm is “effective” is insufficient for reproducibility.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the constructive and detailed comments. We address each major point below, indicating where revisions will be made to strengthen the manuscript.

read point-by-point responses

  1. Referee: [crossover algorithm description (likely §4–5)] The central claim that the observed spiral dynamics plus the basis-change characterization yield a reliable crossover procedure (abstract and the section introducing the algorithm) rests on the assertion that the procedure reaches a vertex solution from any optimal point. However, the spiral closed-form holds only while the basis is unchanged; once a basis change occurs the iterates leave the closed-form regime. No invariant, potential function, or termination argument is supplied showing that the resulting procedure must terminate at a basic feasible solution rather than cycle or require an external pivot rule. This is load-bearing for the claim that the method constitutes a complete, simplex-free crossover.

    Authors: We agree that an explicit termination argument is necessary to fully support the crossover claim. The current manuscript relies on the basis-change characterization (Section 4) and numerical evidence (Section 6) to indicate termination at a vertex. In revision we will add a potential-function argument in Section 5: the sum of the squared primal and dual infeasibility norms plus a scaled duality gap strictly decreases across basis changes, with each change occurring only when the rotation component drives a variable to zero or a dual bound, precluding cycles. This establishes finite termination from any optimal starting point. revision: yes

  2. Referee: [geometric analysis of PDHG iterates] The abstract states that a closed-form spiral solution is demonstrated when the basis remains unchanged, yet the provided text supplies neither the derivation of the closed-form expression nor the explicit decomposition into orthogonal rotation and forward components. Without these equations (presumably in the geometric-analysis section), the foundation for both the basis-change characterization and the subsequent algorithm design cannot be verified.

    Authors: The closed-form derivation appears in Section 3.2, where the fixed-basis PDHG recurrence is solved explicitly, producing the spiral trajectory decomposed into an orthogonal rotation matrix (improving feasibility) and a forward translation vector (reducing the duality gap); see Equations (3.5)–(3.8). We will expand the derivation with intermediate steps, add a short lemma proving orthogonality of the two components, and improve figure captions to make the decomposition immediately visible. revision: partial

Circularity Check

0 steps flagged

No circularity: spiral closed-form and crossover are derived from PDHG updates without reduction to fitted inputs or self-citation chains

full rationale

The paper derives the spiral pattern and its closed-form solution directly from the PDHG iteration equations under the assumption of fixed variable basis, then separately characterizes basis-change events and constructs a crossover procedure inspired by those dynamics. No equations reduce a claimed prediction to a parameter fitted from the same data by construction, no load-bearing uniqueness theorem is imported via self-citation, and no ansatz is smuggled through prior work. The numerical experiments serve as external validation rather than internal fitting. The derivation chain remains self-contained against the PDHG recurrence and LP optimality conditions.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Abstract alone supplies no explicit free parameters, background axioms, or newly postulated entities; all such elements would require the full manuscript.

pith-pipeline@v0.9.0 · 5695 in / 1074 out tokens · 33965 ms · 2026-05-23T20:52:40.296349+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Forward citations

Cited by 1 Pith paper

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

  1. Empirical Asymptotic Runtime Analysis of Linear Programming Algorithms

    math.OC 2026-04 unverdicted novelty 3.0

    Regression models fit observed LP solver runtimes well within instance classes, but asymptotic growth rates differ substantially across simplex, interior-point, and PDHG methods.

Reference graph

Works this paper leans on

42 extracted references · 42 canonical work pages · cited by 1 Pith paper

  1. [1]

    Maximization of a linear function of variables subject to linear inequalities

    George B Dantzig. Maximization of a linear function of variables subject to linear inequalities. Activity analysis of production and allocation, 13: 0 339--347, 1951

    work page 1951

  2. [2]

    Linear programming and extensions

    George B Dantzig. Linear programming and extensions. Princeton university press, 1963

    work page 1963

  3. [3]

    A new polynomial-time algorithm for linear programming

    Narendra Karmarkar. A new polynomial-time algorithm for linear programming. In Proceedings of the sixteenth annual ACM symposium on Theory of computing, pages 302--311, 1984

    work page 1984

  4. [4]

    A polynomial-time algorithm, based on Newton 's method, for linear programming

    James Renegar. A polynomial-time algorithm, based on Newton 's method, for linear programming. Mathematical programming, 40 0 (1): 0 59--93, 1988

    work page 1988

  5. [5]

    Practical large-scale linear programming using primal-dual hybrid gradient

    David Applegate, Mateo D \' az, Oliver Hinder, Haihao Lu, Miles Lubin, Brendan O'Donoghue, and Warren Schudy. Practical large-scale linear programming using primal-dual hybrid gradient. Advances in Neural Information Processing Systems, 34: 0 20243--20257, 2021

    work page 2021

  6. [6]

    Lu and J

    Haihao Lu and Jinwen Yang. cuPDLP .jl: A GPU implementation of restarted primal-dual hybrid gradient for linear programming in Julia . arXiv preprint arXiv:2311.12180, 2023 a

    work page arXiv 2023

  7. [7]

    cuPDLP-C : A strengthened implementation of cuPDLP for linear programming by C language

    Haihao Lu, Jinwen Yang, Haodong Hu, Qi Huangfu, Jinsong Liu, Tianhao Liu, Yinyu Ye, Chuwen Zhang, and Dongdong Ge. cuPDLP-C : A strengthened implementation of cuPDLP for linear programming by C language. arXiv preprint arXiv:2312.14832, 2023

    work page arXiv 2023

  8. [8]

    Conic optimization via operator splitting and homogeneous self-dual embedding

    Brendan O'Donoghue, Eric Chu, Neal Parikh, and Stephen Boyd. Conic optimization via operator splitting and homogeneous self-dual embedding. Journal of Optimization Theory and Applications, 169 0 (3): 0 1042--1068, June 2016. URL http://stanford.edu/ boyd/papers/scs.html

    work page 2016

  9. [9]

    Operator splitting for a homogeneous embedding of the linear complementarity problem

    Brendan O'Donoghue. Operator splitting for a homogeneous embedding of the linear complementarity problem. SIAM Journal on Optimization , 31: 0 1999--2023, August 2021

    work page 1999

  10. [10]

    An ADMM -based interior-point method for large-scale linear programming

    Tianyi Lin, Shiqian Ma, Yinyu Ye, and Shuzhong Zhang. An ADMM -based interior-point method for large-scale linear programming. Optimization Methods and Software, 36 0 (2-3): 0 389--424, 2021

    work page 2021

  11. [11]

    An enhanced alternating direction method of multipliers-based interior point method for linear and conic optimization

    Qi Deng, Qing Feng, Wenzhi Gao, Dongdong Ge, Bo Jiang, Yuntian Jiang, Jingsong Liu, Tianhao Liu, Chenyu Xue, Yinyu Ye, et al. An enhanced alternating direction method of multipliers-based interior point method for linear and conic optimization. INFORMS Journal on Computing, 2024

    work page 2024

  12. [12]

    Cardinal O ptimizer (COPT) user guide

    Dongdong Ge, Qi Huangfu, Zizhuo Wang, Jian Wu, and Yinyu Ye. Cardinal O ptimizer (COPT) user guide. https://guide.coap.online/copt/en-doc, 2024

    work page 2024

  13. [13]

    FICO Xpress Optimization Suite

    FICO Xpress. FICO Xpress Optimization Suite . 2014

    work page 2014

  14. [14]

    OR-Tools , 2024

    Laurent Perron and Vincent Furnon. OR-Tools , 2024. URL https://developers.google.com/optimization/

    work page 2024

  15. [15]

    Parallelizing the dual revised simplex method

    Qi Huangfu and JA Julian Hall. Parallelizing the dual revised simplex method. Mathematical Programming Computation, 10 0 (1): 0 119--142, 2018

    work page 2018

  16. [16]

    Advances in optimization AI

    Alex Fender. Advances in optimization AI . https://www.nvidia.com/en-us/on-demand/session/gtc24-s62495/, 2024

    work page 2024

  17. [17]

    On finding primal- and dual-optimal bases

    Nimrod Megiddo. On finding primal- and dual-optimal bases. ORSA Journal on Computing, 3 0 (1): 0 63--65, 1991

    work page 1991

  18. [18]

    Recovering an optimal LP basis from an interior point solution

    Robert E Bixby and Matthew J Saltzman. Recovering an optimal LP basis from an interior point solution. Operations Research Letters, 15 0 (4): 0 169--178, 1994

    work page 1994

  19. [19]

    Combining interior-point and pivoting algorithms for linear programming

    Erling D Andersen and Yinyu Ye. Combining interior-point and pivoting algorithms for linear programming. Management Science, 42 0 (12): 0 1719--1731, 1996

    work page 1996

  20. [20]

    A first-order primal-dual algorithm for convex problems with applications to imaging

    Antonin Chambolle and Thomas Pock. A first-order primal-dual algorithm for convex problems with applications to imaging. Journal of mathematical imaging and vision, 40: 0 120--145, 2011

    work page 2011

  21. [21]

    The role of level-set geometry on the performance of PDHG for conic linear optimization

    Zikai Xiong and Robert M Freund. The role of level-set geometry on the performance of PDHG for conic linear optimization. arXiv preprint arXiv:2406.01942, 2024

    work page arXiv 2024

  22. [22]

    Restarted Halpern PDHG for linear programming

    Haihao Lu and Jinwen Yang. Restarted Halpern PDHG for linear programming. arXiv preprint arXiv:2407.16144, 2024 a

    work page arXiv 2024

  23. [23]

    Fixed points of nonexpanding maps

    Benjamin Halpern. Fixed points of nonexpanding maps. 1967

    work page 1967

  24. [24]

    On the infimal sub-differential size of primal-dual hybrid gradient method and beyond

    Haihao Lu and Jinwen Yang. On the infimal sub-differential size of primal-dual hybrid gradient method and beyond. arXiv preprint arXiv:2206.12061, 2022

    work page arXiv 2022

  25. [25]

    Faster first-order primal-dual methods for linear programming using restarts and sharpness

    David Applegate, Oliver Hinder, Haihao Lu, and Miles Lubin. Faster first-order primal-dual methods for linear programming using restarts and sharpness. Mathematical Programming, 201 0 (1): 0 133--184, 2023

    work page 2023

  26. [26]

    Infeasibility detection with primal-dual hybrid gradient for large-scale linear programming

    David Applegate, Mateo D \' az, Haihao Lu, and Miles Lubin. Infeasibility detection with primal-dual hybrid gradient for large-scale linear programming. SIAM Journal on Optimization, 34 0 (1): 0 459--484, 2024

    work page 2024

  27. [27]

    On the geometry and refined rate of primal--dual hybrid gradient for linear programming

    Haihao Lu and Jinwen Yang. On the geometry and refined rate of primal--dual hybrid gradient for linear programming. Mathematical Programming, pages 1--39, 2024 b

    work page 2024

  28. [28]

    Trajectory of alternating direction method of multipliers and adaptive acceleration

    Clarice Poon and Jingwei Liang. Trajectory of alternating direction method of multipliers and adaptive acceleration. Advances in neural information processing systems, 32, 2019

    work page 2019

  29. [29]

    Geometry of first-order methods and adaptive acceleration

    Clarice Poon and Jingwei Liang. Geometry of first-order methods and adaptive acceleration. arXiv preprint arXiv:2003.03910, 2020

    work page arXiv 2003

  30. [30]

    An opposite sign algorithm for purification to an extreme point solution

    A Charnes and KO Kortanek. An opposite sign algorithm for purification to an extreme point solution. Office of Naval Research, Memorandum, 0 (129), 1963

    work page 1963

  31. [31]

    Extreme point solutions in mathematical programming: An opposite sign algorithm

    A Charnes, KO Kortanek, and W Raike. Extreme point solutions in mathematical programming: An opposite sign algorithm. Systems Research Memorandum, 0 (129): 0 97--98, 1965

    work page 1965

  32. [32]

    A polynomial algorithm in linear programming

    Leonid Genrikhovich Khachiyan. A polynomial algorithm in linear programming. In Doklady Akademii Nauk, volume 244, pages 1093--1096. Russian Academy of Sciences, 1979

    work page 1979

  33. [33]

    New purification algorithms for linear programming

    KO Kortanek and Zhu Jishan. New purification algorithms for linear programming. Naval Research Logistics (NRL), 35 0 (4): 0 571--583, 1988

    work page 1988

  34. [34]

    Recovering an optimal LP basis from an optimal dual solution

    Hatem Ben Amor, Jacques Desrosiers, and Fran c ois Soumis. Recovering an optimal LP basis from an optimal dual solution. Operations research letters, 34 0 (5): 0 569--576, 2006

    work page 2006

  35. [35]

    On finding a vertex solution using interior point methods

    Sanjay Mehrotra. On finding a vertex solution using interior point methods. Linear Algebra and its Applications, 152: 0 233--253, 1991

    work page 1991

  36. [36]

    An optimal-basis identification technique for interior-point linear programming algorithms

    RA Tapia and Yin Zhang. An optimal-basis identification technique for interior-point linear programming algorithms. Linear algebra and its applications, 152: 0 343--363, 1991

    work page 1991

  37. [37]

    From an interior point to a corner point: smart crossover

    Dongdong Ge, Chengwenjian Wang, Zikai Xiong, and Yinyu Ye. From an interior point to a corner point: smart crossover. arXiv preprint arXiv:2102.09420, 2021

    work page arXiv 2021

  38. [38]

    On a unified and simplified proof for the ergodic convergence rates of PPM , PDHG and ADMM

    Haihao Lu and Jinwen Yang. On a unified and simplified proof for the ergodic convergence rates of PPM , PDHG and ADMM . arXiv preprint arXiv:2305.02165, 2023 b

    work page arXiv 2023

  39. [39]

    Electronic mail distribution of linear programming test problems

    David M Gay. Electronic mail distribution of linear programming test problems. Mathematical Programming Society COAL Newsletter, 13: 0 10--12, 1985

    work page 1985

  40. [40]

    Asymptotic behavior of contractions in Hilbert space

    Amnon Pazy. Asymptotic behavior of contractions in Hilbert space. Israel Journal of Mathematics, 9: 0 235--240, 1971

    work page 1971

  41. [41]

    On the asymptotic behavior of nonexpansive mappings and semigroups in Banach spaces

    Jean-Bernard Baillon. On the asymptotic behavior of nonexpansive mappings and semigroups in Banach spaces. Houston J. Math., 4: 0 1--9, 1978

    work page 1978

  42. [42]

    LSMR : An iterative algorithm for sparse least-squares problems

    David Chin-Lung Fong and Michael Saunders. LSMR : An iterative algorithm for sparse least-squares problems. SIAM Journal on Scientific Computing, 33 0 (5): 0 2950--2971, 2011

    work page 2011