Pith. sign in

REVIEW 3 major objections 6 minor 1 cited by

An Overview of GPU-based First-Order Methods for Linear Programming and Extensions

T0 review · 3 major / 6 minor · reviewed 2026-08-07 · deepseek-v4-flash

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

Pith's one-line read A first-order-method-based LP solver on a GPU can compete with strong simplex and barrier implementations even at high accuracy.

desk verdict A solid survey of the authors' GPU first-order LP line, but the headline high-accuracy claim rests on a tolerance mismatch that is acknowledged and not resolved. read the letter →

arxiv 2506.02174 v1 pith:ERPQWR52 submitted 2025-06-02 math.OC

Haihao Lu , Jinwen Yang This is my paper
classification math.OC MSC 90C0590C0665K05
keywords GPUcomputinglinearprogrammingprimal-dualhybridgradientPDLPcufirst-ordermethodssharpnessinfeasibilitydetection
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

This survey assembles the case that linear programming, long dominated by simplex and interior-point methods built on sparse matrix factorization, is entering a GPU era. The authors argue that a first-order method based on the primal-dual hybrid gradient (PDHG) algorithm, implemented on a GPU as cuPDLP, can match or beat industrial CPU solvers on large linear programs, and even reach high-accuracy solutions at 1e-8 tolerance in many cases. The survey's central claim is that a first-order-method-based LP solver on a GPU can be a new horse in the race with strong implementations of simplex and barrier methods. If true, this matters because it offers a memory-efficient, factorization-free route to solving much larger LPs than current CPU solvers handle.

What carries the argument

The load-bearing object is the PDHG iteration written in the form $P(z^k - z^{k+1}) \in F(z^{k+1})$, where $P$ is a positive semidefinite matrix pairing the step sizes with the constraint matrix, and $F$ is the subdifferential of the primal-dual objective. This representation shows that PDHG is a preconditioned proximal point method, and it makes the $O(1/k)$ average-iterate rate and the $O(1/\sqrt{k})$ last-iterate rate straightforward. The path to fast practical performance is sharpness: LP satisfies a Hoffman-type inequality, so last iterates converge linearly, and restarting the averaged or Halpern variants yields a rate $O(\kappa \log(1/\epsilon))$ that matches the lower bound for span-respecting first-order methods. The paper also documents the spiral-ray geometry of PDHG iterates, which underlies the averaging and restart heuristics.

What would settle it

Run the same GPU first-order solver against a CPU interior-point method with presolve and crossover enabled on a wide set of LP instances with varying factorization cost, at 1e-8 tolerance, and compare solved counts within equal time limits; a consistent CPU advantage on medium and large instances would falsify the new-horse claim.

Watch

Extended reading notes

Core claim

The core discovery the survey presents is that PDHG, a simple iteration alternating a projected primal step and a dual step built on matrix-vector products, can be engineered into a production-grade LP solver. The engineering includes diagonal preconditioning, averaging or Halpern anchoring, reflection, adaptive restarts, adaptive step sizes, primal weighting, feasibility polishing, and infeasibility detection. On a curated benchmark of 383 LP relaxations, the GPU implementations cuPDLP.jl and reflected Halpern PDHG solve more than 99 percent of instances to moderate accuracy within the time limits and remain competitive with interior-point methods at high accuracy; on medium and large instances they are several times faster than CPU first-order solvers and outperform CPU simplex and barrier methods at moderate accuracy. The survey concludes that this makes GPU first-order LP a credible new horse in the race.

Load-bearing premise

The load-bearing premise is that the reported speedups, taken from the authors' earlier experimental papers, reproduce on representative LP workloads and are not an artifact of one benchmark set or one GPU-versus-CPU hardware pairing.

Editorial extensions

If this is right

  • A factorization-free LP solver on a GPU can handle problems whose factorization-based solvers run out of memory or time, because the dominant operations are sparse matrix-vector products.
  • At moderate accuracy (1e-4), the GPU first-order solvers are competitive with and often faster than CPU simplex and interior-point methods on large benchmark instances.
  • At high accuracy (1e-8), the GPU solvers still solve most benchmark instances, though a CPU interior-point method remains the strongest on the full set.
  • Restarted Halpern PDHG attains the optimal worst-case complexity among span-respecting first-order methods for LP, up to logarithmic factors.
  • The same PDHG-based machinery extends to quadratic, conic, semidefinite, and nonlinear programming, so the GPU-first-order approach is not confined to LP.

Reading between the lines

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

  • If the benchmark results generalize beyond curated LP relaxations, one practical consequence is that solver design will shift from minimizing factorizations to minimizing memory traffic, with presolve and crossover routines re-engineered around first-order iterates.
  • The reliance on a GPU-friendly restart metric rather than a trust-region normalized duality gap suggests that other GPU-native progress metrics could further accelerate first-order solvers.
  • A testable extension is to run the same solver on sparse network-flow and optimal-transport instances, where PDHG's polynomial complexity is provable, to see whether the practical speedups exceed those on general LP.
  • The survey leaves open whether a GPU crossover can convert approximate PDHG solutions into basic feasible solutions cheaply; a fast parallel crossover would make first-order solvers far more useful inside mixed-integer programming.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

3 major / 6 minor

Summary. This manuscript is a survey of GPU-based first-order methods for linear programming, centered on the authors' own PDLP/cuPDLP line of work. It covers the design rationale for PDHG-based solvers, practical enhancements (preconditioning, restart, averaging, Halpern/reflection, adaptive step-size, primal weight, feasibility polishing, infeasibility detection), numerical comparisons of cuPDLP.jl and r2HPDHG against Gurobi and CPU-based PDLP on the MIP Relaxations benchmark, a theoretical overview of PDHG convergence including sharpness and restart optimality, and extensions to QP, SDP, conic, and nonlinear programming. The central claim is that a GPU-based first-order LP solver can be a competitive alternative to strong simplex and barrier implementations, including at high accuracy.

Significance. The survey is timely and useful: it organizes a rapidly evolving literature, provides a unified theoretical perspective (PDHG as a preconditioned proximal point method, sharpness-based linear convergence, restart optimality, Halpern/reflection acceleration), and is unusually candid about limitations, including the lack of guarantees for adaptive step-size, the unreliability of primal-weight heuristics, and the inferiority of the current GPU first-order solvers to Gurobi barrier at high accuracy. The paper also points to concrete open-source artifacts such as cuPDLP.jl and cuPDLP-C, which strengthens its practical value. If the high-accuracy performance claims survive scrutiny, the survey would support an important reorientation of LP solver development toward massively parallel, factorization-free algorithms. However, the numerical evidence for the high-accuracy component of the central claim is weakened by the relative-versus-absolute tolerance mismatch detailed below, so the survey currently overstates the degree to which the 'new horse in the race' conclusion is established.

major comments (3)
  1. [Section 3.4.2 / Footnote 10] The high-accuracy claim rests on a termination-criteria mismatch. PDLP, cuPDLP.jl, and r2HPDHG terminate when the relative KKT error is below 1e-8, with components scaled by problem-dependent quantities such as (1+|c^T x|), (1+||q||_2), and (1+||c||_2), while Gurobi applies absolute tolerances, as Footnote 10 concedes. When data norms are large, a PDLP solve can be labeled 'high accuracy' while the absolute primal infeasibility, dual infeasibility, or objective gap is orders of magnitude larger than 1e-8. The footnote states that empirical observations show PDLP still produces high-quality solutions, but the survey reports no supporting data. Because the solved counts in Tables 6 and 8 are the basis for the sentence that the GPU first-order solver is competitive 'even in obtaining high-accuracy solutions,' this mismatch is load-bearing. The authors should either report the absolute KKT residuals at termination, rerun the comparison with a common absolute tolerance, or explicitly restrict the high-accuracy claim to relative accuracy and temper the conclusion accordingly.
  2. [Section 3.4.1] The central scalability and competitiveness claims are supported almost entirely by one curated benchmark family (MIPLIB 2017 root LP relaxations with at least 100K nonzeros) and one hardware pairing (NVIDIA H100-PCIe-80GB versus Intel Xeon Gold 6248R, Table 4). The numerical tables in Section 3.4 are imported from the authors' earlier papers [95, 100], and the survey ships no reproducibility artifacts that would allow an independent check. The additional evidence in Section 3.4.4 is anecdotal and reported second-hand. Since the conclusion in Section 3.4.2 states that a first-order GPU solver can be 'a new horse in the race' with strong simplex and barrier implementations, the authors should either provide a reproducibility statement with open code and benchmark data, or add corroborating results on independent benchmark suites (e.g., Netlib, Mittelmann's LP set) and explicitly discuss how the choice of benchmark and CPU/GPU hardware affects the claimed generalizability. Without this, the conclusion is not established beyond the curated MIP Relaxations setting.
  3. [Section 3.6] The survey acknowledges in Section 3.6 that PDLP is sensitive to hyper-parameter tuning, especially step-size and primal weight, and states in Section 3.3 that the proposed adaptive primal-weight rule is 'not always reliable' and that per-instance tuning can yield significant improvements. This interacts with the central performance claim: the strong numbers in Tables 5-10 are presumably obtained with the implementations' default settings, but the manuscript never states this explicitly, nor does it quantify how much of the reported performance depends on default heuristics versus tuning. For a survey whose central message is that a first-order method can compete with mature simplex and barrier solvers, the authors should clarify whether the benchmark results use default parameters and, if tuning was used, report the tuning procedure and its sensitivity. This is load-bearing for the practical conclusion that the solver is a reliable alternative rather than a method that requires expert per-instance configuration.
minor comments (6)
  1. [Section 1.1] There is a typo: 'advencements' should be 'advancements'.
  2. [References] Reference [18] lists the author as 'J BnnoBRs'; this should be 'J. F. Benders'.
  3. [Section 4.7] The heading and text use the misspelling 'infeasiblity'; it should be 'infeasibility'.
  4. [Section 4.6.2] The word 'precesily' in the discussion of [155] should be 'precisely'.
  5. [Section 3.3 / Figure 1 / Table 2] Figure 1 and Table 2 present experiments on 383 MIPLIB instances, but the benchmark description is deferred to Section 3.4.1; consider referencing Section 3.4.1 when these are introduced so the reader knows the data source.
  6. [Section 3.3] In the 'Feasibility polishing' bullet, there is a stray formatting artifact ('F easibility'); this should be cleaned up.

Circularity Check

0 steps flagged · score 2.0 of 10

No significant circularity: the survey summarizes the authors' own prior work, but the central claim is independently supported by third-party implementations and benchmarks.

full rationale

This paper is a survey rather than a self-contained derivation, so its 'derivation chain' consists mostly of summarizing existing algorithms and results. The numerical sections explicitly attribute the headline experiments to the authors' earlier papers ([95], [100]), and the theoretical sections cite standard results alongside the authors' own preprints. That self-citation is real but not load-bearing in a circular sense: the 'new horse in the race' claim is supported by independent evidence cited in Section 3.4.4 (COPT's cuPDLP-C, NVIDIA cuOpt, Gurobi's own internal tests) and by open-source implementations, so the conclusion does not reduce to the authors' own inputs. The optimality claim for restarted reflected Halpern PDHG relies on a peer-reviewed complexity lower bound [7] with stated assumptions, not on an unverified uniqueness theorem imported from the authors. No fitted parameter is relabeled as a prediction: PDLP's relative KKT-error stopping rule is a defined termination criterion, and the acknowledged mismatch with Gurobi's absolute tolerance is a fairness caveat, not a construction that forces the comparison. The tolerance issue is a weakness in the high-accuracy comparison, but it is a benchmarking interpretation matter rather than circularity. Overall, the self-citation burden is mild and does not make the central derivation equivalent to its inputs.

Assumptions & free parameters 3 free parameters · 5 assumptions · 0 invented entities

The survey's central claims rest primarily on the authors' prior theoretical and experimental work, plus the assumption that the curated benchmark and hardware setup are representative. The algorithmic hyperparameters are heuristic and, by the authors' own admission, not fully reliable.

free parameters (3)
  • step-size eta (PDLP adaptive line search)
    Central to PDHG convergence; PDLP uses an adaptive heuristic (Section 3.3, inequality (12)) that the survey says breaks the theoretical convergence guarantees.
  • primal weight omega
    Balances primal and dual step sizes; survey states the adaptive rule 'is not always reliable as expected' and per-instance tuning can yield significant gains (Section 3.3).
  • restart hyperparameters (decay factor 1/e and initial inner-loop limit tau0) = 1/e, tau0 not specified
    Used in restarted Halpern PDHG (Algorithm 1, condition (25)); these choices are heuristic and affect the outer-loop complexity bound.
assumptions (5)
  • standard math Hoffman sharpness of LP KKT error (Proposition 4)
    Underpins linear convergence theorems in Section 4.4; cited to [73,121].
  • standard math PDHG operator is firmly nonexpansive in the P-norm (Lemma 1)
    Basis for Halpern/reflection acceleration results in Section 4.3; from [6,9,137].
  • standard math Span-respecting lower bound (Theorem 7) is the correct model for FOMs
    Used to claim optimality of restarted Halpern PDHG; lower bound is for span-respecting algorithms only.
  • domain assumption MIP Relaxations benchmark set is representative of large-scale LP workloads
    All numerical comparisons are on 383 curated MIPLIB 2017 relaxations with at least 100K nonzeros; excludes unstable/infeasible/indicator instances (Section 3.4.1).
  • domain assumption Relative KKT tolerance for PDLP and absolute tolerance for Gurobi yield comparable stopping
    The survey discusses this difference but does not quantify its effect on solve times (Section 3.4.1).

how reviews work

0 comments
Cite this review

Pith. "Pith review of An Overview of GPU-based First-Order Methods for Linear Programming and Extensions." pith.science (2026). https://pith.science/paper/ERPQWR52

@misc{pith2026250602174,
  author       = {Pith},
  title        = {Pith review of: An Overview of GPU-based First-Order Methods for Linear Programming and Extensions},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/ERPQWR52}},
  note         = {Machine review of arXiv:2506.02174}
}
read the original abstract

The rapid progress in GPU computing has revolutionized many fields, yet its potential in mathematical programming, such as linear programming (LP), has only recently begun to be realized. This survey aims to provide a comprehensive overview of recent advancements in GPU-based first-order methods for LP, with a particular focus on the design and development of cuPDLP. We begin by presenting the design principles and algorithmic foundation of the primal-dual hybrid gradient (PDHG) method, which forms the core of the solver. Practical enhancements, such as adaptive restarts, preconditioning, Halpern-type acceleration and infeasibility detection, are discussed in detail, along with empirical comparisons against industrial-grade solvers, highlighting the scalability and efficiency of cuPDLP. We also provide a unified theoretical framework for understanding PDHG, covering both classical and recent results on sublinear and linear convergence under sharpness conditions. Finally, we extend the discussion to GPU-based optimization beyond LP, including quadratic, semidefinite, conic, and nonlinear programming.

Figures

Figures reproduced from arXiv: 2506.02174 by the authors.

Figure 1
Figure 1. Scatter plots showing the speedup in running time speedup of GPU versus CPU for SpMV, [PITH_FULL_IMAGE:figures/full_fig_p005_1.png] view at source ↗
Figure 2
Figure 2. Trajectories of GDA, PPM and PDHG to solve a simple bilinear problem (4) with initial solution [PITH_FULL_IMAGE:figures/full_fig_p009_2.png] view at source ↗
Figure 3
Figure 3. Primal-dual trajectory of PDHG for solving two toy LP instances. [PITH_FULL_IMAGE:figures/full_fig_p010_3.png] view at source ↗
Figures from the paper (5 more)
Figure 4
Figure 4. Figure 4: Number of instances solved for MIP Relaxations under moderate accuracy (left) and high accuracy (right): cuPDLP.jl versus Gurobi without presolve. Small (269) (1-hour limit) Medium (94) (1-hour limit) Large (20) (5-hour limit) Total (383) Count Time Count Time Count Ti…
Figure 5
Figure 5. Figure 5: Number of instances solved for MIP Relaxations under moderate accuracy (left) and high accuracy (right): cuPDLP.jl versus Gurobi with presolve. 3.4.3 Comparison with CPU-based PDLP Small (269) (1-hour limit) Medium (94) (1-hour limit) Large (20) (5-hour limit) Total (3…
Figure 6
Figure 6. Figure 6: Number of instances solved for MIP Relaxations under moderate accuracy (left) and high accuracy (right): cuPDLP.jl versus PDLP. Similar to [PITH_FULL_IMAGE:figures/full_fig_p020_6.png]
Figure 7
Figure 7. Figure 7: Illustration of update schemes of Halpern PDHG and reflected Halpern PDHG [PITH_FULL_IMAGE:figures/full_fig_p028_7.png]
Figure 8
Figure 8. Figure 8: PDHG on four LP relaxation of instances from benchmark sets [PITH_FULL_IMAGE:figures/full_fig_p032_8.png]

Discussion (0). Sign in to comment.

Forward citations

Cited by 1 Pith paper

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

  1. Large-Scale Linear Energy System Optimization: A Systematic Review on Parallelization Strategies via Decomposition

    math.OC 2025-07 conditional novelty 6.0 of 10

    Parallelized decomposition can speed up large linear energy system optimization models, but no single method dominates and the field needs standardized benchmarks and reporting rules.

Reference graph

Works this paper leans on

166 extracted references · 50 canonical work pages · cited by 1 Pith paper

  1. [1]

    Jacob M Aguirre, Diego Cifuentes, Vincent Guigues, Renato DC Monteiro, Victor Hugo Nascimento, and Arnesh Sujanani,cuhallar: A gpu accelerated low-rank augmented lagrangian method for large-scale semidefinite programming, arXiv preprint arXiv:2505.13719 (2025)

    arXiv 2025

  2. [2]

    Ravindra K Ahuja, Thomas L Magnanti, and James B Orlin,Network flows, (1988)

    1988

  3. [3]

    Erling D Andersen, Cees Roos, and Tamas Terlaky,On implementing a primal-dual interior-point method for conic quadratic optimization, Mathematical Programming95(2003), 249–277

    2003

  4. [4]

    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 Systems34(2021), 20243–20257

    2021

  5. [5]

    ,Pdlp: A practical first-order method for large-scale linear programming, arXiv preprint arXiv:2501.07018 (2025)

    arXiv 2025

  6. [6]

    1, 459–484

    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 Optimization34(2024), no. 1, 459–484

    2024

  7. [7]

    1, 133–184

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

    2023

  8. [8]

    Heinz H Bauschke, Patrick L Combettes, Heinz H Bauschke, and Patrick L Combettes,Correction to: convex analysis and monotone operator theory in hilbert spaces, Springer, 2017

    2017

Show all 166 references
  1. [9]

    HH Bauschke and PL Combettes,Convex analysis and monotone operator theory in hilbert spaces, corrected printing, 2019

    2019

  2. [10]

    Mokhtar S Bazaraa, John J Jarvis, and Hanif D Sherali,Linear programming and network flows, John Wiley & Sons, 2011

    2011

  3. [11]

    Amir Beck,First-order methods in optimization, SIAM, 2017

    2017

  4. [12]

    1, 95–107

    Alexandre Belloni and Robert M Freund,A geometric analysis of renegar’s condition number, and its interplay with conic curvature, Mathematical programming119(2009), no. 1, 95–107

    2009

  5. [13]

    6, Athena Scientific Belmont, MA, 1997

    Dimitris Bertsimas and John N Tsitsiklis,Introduction to linear optimization, vol. 6, Athena Scientific Belmont, MA, 1997

    1997

  6. [14]

    4, 827–841

    Tim Besard, Christophe Foket, and Bjorn De Sutter,Effective extensible programming: unleashing julia on gpus, IEEE Transactions on Parallel and Distributed Systems30(2018), no. 4, 827–841

    2018

  7. [15]

    1, 65–98

    Jeff Bezanson, Alan Edelman, Stefan Karpinski, and Viral B Shah,Julia: A fresh approach to numerical computing, SIAM review59(2017), no. 1, 65–98

    2017

  8. [16]

    6, 1039–1091

    Robert G Bland, Donald Goldfarb, and Michael J Todd,The ellipsoid method: A survey, Operations research29(1981), no. 6, 1039–1091. 40

    1981

  9. [17]

    Nicolas Blin,Accelerate large linear programming problems with nvidia cuopt, 2024,https:// developer.nvidia.com/blog/accelerate-large-linear-programming-problems-with-nvidia-cuopt/

    2024

  10. [18]

    Math 4(1962), no

    J BnnoBRs,Partitioning procedures for solving mixed-variables programming problems, Numer. Math 4(1962), no. 1, 238–252

    1962

  11. [19]

    1, 1–122

    Stephen Boyd, Neal Parikh, Eric Chu, Borja Peleato, Jonathan Eckstein, et al.,Distributed opti- mization and statistical learning via the alternating direction method of multipliers, Foundations and Trends®in Machine learning3(2011), no. 1, 1–122

    2011

  12. [20]

    Stephen Boyd and Lieven Vandenberghe,Convex optimization, Cambridge university press, 2004

    2004

  13. [21]

    George Brown and Tjalling Koopmans,Computational suggestions for maximizing a linear function subject to linear inequalities, Activity Analysis of Production and Allocation (1951), 377–380

    1951

  14. [22]

    3, 493–512

    Samuel Burer and Changhui Choi,Computational enhancements in low-rank semidefinite programming, Optimisation Methods and Software21(2006), no. 3, 493–512

    2006

  15. [23]

    2, 329–357

    Samuel Burer and Renato DC Monteiro,A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization, Mathematical programming95(2003), no. 2, 329–357

    2003

  16. [24]

    3, 427–444

    ,Local minima and convergence in low-rank semidefinite programming, Mathematical program- ming103(2005), no. 3, 427–444

    2005

  17. [25]

    Antonin Chambolle and Thomas Pock,A first-order primal-dual algorithm for convex problems with applications to imaging, Journal of mathematical imaging and vision40(2011), 120–145

    2011

  18. [26]

    1-2, 253–287

    ,On the ergodic convergence rates of a first-order primal–dual algorithm, Mathematical Pro- gramming159(2016), no. 1-2, 253–287

    2016

  19. [27]

    3, 211–239

    Soo Chang and Katta Murty,The steepest descent gravitational method for linear programming, Dis- crete Applied Mathematics25(1989), no. 3, 211–239

    1989

  20. [28]

    1, 20–46

    Abraham Charnes, William W Cooper, and Merton H Miller,Application of linear programming to financial budgeting and the costing of funds, The Journal of Business32(1959), no. 1, 20–46

    1959

  21. [29]

    Kaihuang Chen, Defeng Sun, Yancheng Yuan, Guojun Zhang, and Xinyuan Zhao,Hpr-lp: An imple- mentation of an hpr method for solving linear programming, arXiv preprint arXiv:2408.12179 (2024)

    2024 arXiv

  22. [30]

    4, 1779–1814

    Yunmei Chen, Guanghui Lan, and Yuyuan Ouyang,Optimal primal-dual methods for a class of saddle point problems, SIAM Journal on Optimization24(2014), no. 4, 1779–1814

    2014

  23. [31]

    Yuwen Chen, Danny Tse, Parth Nobel, Paul Goulart, and Stephen Boyd,Cuclarabel: Gpu acceleration for a conic optimization solver, arXiv preprint arXiv:2412.19027 (2024)

    2024

  24. [32]

    4, 609–624

    Dennis Cheung, Felipe Cucker, and Javier Pena,Unifying condition numbers for linear programming, Mathematics of Operations Research28(2003), no. 4, 609–624

    2003

  25. [33]

    Barry A Cipra,The best of the 20th century: Editors name top 10 algorithms, SIAM news33(2000), no. 4, 1–2

    2000

  26. [34]

    1, 341–370

    Joachim Dahl and Erling D Andersen,A primal-dual interior-point algorithm for nonsymmetric exponential-cone optimization, Mathematical Programming194(2022), no. 1, 341–370

    2022

  27. [35]

    Munther Dahleh and Ignacio Diaz-Bobillo,Control of uncertain systems: a linear programming ap- proach, Prentice-Hall, Inc., 1994

    1994

  28. [36]

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

    1963

  29. [37]

    George B Dantzig,Programming in a linear structure, Washington, DC (1948)

    1948

  30. [38]

    1, 101–111

    George B Dantzig and Philip Wolfe,Decomposition principle for linear programs, Operations research 8(1960), no. 1, 101–111. 41

    1960

  31. [39]

    3, 1912–1943

    Damek Davis,Convergence rate analysis of primal-dual splitting schemes, SIAM Journal on Optimiza- tion25(2015), no. 3, 1912–1943

    2015

  32. [40]

    Damek Davis and Wotao Yin,Convergence rate analysis of several splitting schemes, Splitting methods in communication, imaging, science, and engineering (2016), 115–163

    2016

  33. [41]

    Antonio De Rosa, Aida Khajavirad, and Yakun Wang,On the power of linear programming for k-means clustering, arXiv preprint arXiv:2402.01061 (2024)

    2024 arXiv

  34. [42]

    3, 1155–1163

    Jerome Delson and Mohammad Shahidehpour,Linear programming applications to power system eco- nomics, planning and operations, IEEE Transactions on Power Systems7(1992), no. 3, 1155–1163

    1992

  35. [43]

    1428– 1451

    Jelena Diakonikolas,Halpern iteration for near-optimal and parameter-free monotone inclusion and strong solutions to variational inequalities, Conference on Learning Theory, PMLR, 2020, pp. 1428– 1451

    2020

  36. [44]

    Dokl., vol

    Iliya Iosiphovich Dikin,Iterative solution of problems of linear and quadratic programming, Soviet Math. Dokl., vol. 8, 1967, pp. 674–675

    1967

  37. [45]

    Lijun Ding, Haihao Lu, and Jinwen Yang,New understandings and computation on augmented la- grangian methods for low-rank semidefinite programming, arXiv preprint arXiv:2505.15775 (2025)

    2025 arXiv

  38. [46]

    Asen L Dontchev and R Tyrrell Rockafellar,Regularity and conditioning of solution mappings in variational analysis, Set-Valued Analysis12(2004), 79–109

    2004

  39. [47]

    543, Springer, 2009

    ,Implicit functions and solution mappings, vol. 543, Springer, 2009

    2009

  40. [48]

    1, 256–267

    Dmitriy Drusvyatskiy and Adrian S Lewis,Tilt stability, uniform quadratic growth, and strong metric regularity of the subdifferential, SIAM Journal on Optimization23(2013), no. 1, 256–267

    2013

  41. [49]

    3, 919–948

    ,Error bounds, quadratic growth, and linear convergence of proximal methods, Mathematics of Operations Research43(2018), no. 3, 919–948

    2018

  42. [50]

    Dmitriy Drusvyatskiy, Boris S Mordukhovich, and Tran TA Nghia,Second-order growth, tilt stability, and metric regularity of the subdifferential, arXiv preprint arXiv:1304.7385 (2013)

    2013 arXiv

  43. [51]

    Jonathan Eckstein and Dimitri P Bertsekas,On the douglas—rachford splitting method and the proxi- mal point algorithm for maximal monotone operators, Mathematical programming55(1992), 293–318

    1992

  44. [52]

    3, 451–485

    Marina Epelman and Robert M Freund,Condition number complexity of an elementary algorithm for computing a reliable solution of a conic linear system, Mathematical Programming88(2000), no. 3, 451–485

    2000

  45. [53]

    124, 1–27

    Julius Farkas,Theorie der einfachen ungleichungen., Journal f¨ ur die reine und angewandte Mathematik (Crelles Journal)1902(1902), no. 124, 1–27

    1902

  46. [54]

    Olivier Fercoq,Quadratic error bound of the smoothed gap and the restarted averaged primal-dual hybrid gradient, arXiv preprint arXiv:2206.03041 (2022)

    2022 arXiv

  47. [55]

    4, 601–617

    Anthony V Fiacco and Garth P McCormick,Computational algorithm for the sequential unconstrained minimization technique for nonlinear programming, Management Science10(1964), no. 4, 601–617

    1964

  48. [56]

    2, 360–366

    ,The sequential unconstrained minimization technique for nonlinear programing, a primal-dual method, Management Science10(1964), no. 2, 360–366

    1964

  49. [57]

    1, 341–374

    John J Forrest and Donald Goldfarb,Steepest-edge simplex algorithms for linear programming, Math- ematical programming57(1992), no. 1, 341–374

    1992

  50. [58]

    Robert Freund,Professor george dantzig: Linear programming founder turns 80, SIAM News, Novem- ber (1994)

    1994

  51. [59]

    4, 1004–1013

    Robert M Freund,On the primal-dual geometry of level sets in linear and conic optimization, SIAM Journal on Optimization13(2003), no. 4, 1004–1013. 42

    2003

  52. [60]

    ,Complexity of convex optimization using geometry-based measures and a reference point, Math- ematical Programming99(2004), 197–221

    2004

  53. [61]

    distance to ill- posedness

    Robert M Freund and Jorge R Vera,Some characterizations and properties of the “distance to ill- posedness” and the condition measure of a conic linear system, Mathematical Programming86(1999), no. 2, 225–260

    1999

  54. [62]

    David Gale, Harold W Kuhn, and Albert W Tucker,Linear programming and the theory of games, Activity analysis of production and allocation13(1951), 317–335

    1951

  55. [63]

    Christophel, Kati Jarck, Thorsten Koch, Jeff Linderoth, Marco L¨ ubbecke, Hans D

    Ambros Gleixner, Gregor Hendel, Gerald Gamrath, Tobias Achterberg, Michael Bastubbe, Timo Berthold, Philipp M. Christophel, Kati Jarck, Thorsten Koch, Jeff Linderoth, Marco L¨ ubbecke, Hans D. Mittelmann, Derya Ozyurt, Ted K. Ralphs, Domenico Salvagnin, and Yuji Shinano,MI- PL...

    2021

  56. [64]

    Paul J Goulart and Yuwen Chen,Clarabel: An interior-point solver for conic programs with quadratic objectives, arXiv preprint arXiv:2405.12762 (2024)

    2024 arXiv

  57. [65]

    David Applegate Haihao Lu,Scaling up linear programming with pdlp,https://research.google/ blog/scaling-up-linear-programming-with-pdlp/, 2024-09-20

    2024

  58. [66]

    Benjamin Halpern,Fixed points of nonexpanding maps, (1967)

    1967

  59. [67]

    Qiushi Han, Chenxi Li, Zhenwei Lin, Caihua Chen, Qi Deng, Dongdong Ge, Huikang Liu, and Yinyu Ye,A low-rank admm splitting approach for semidefinite programming, arXiv preprint arXiv:2403.09133 (2024)

    2024 arXiv

  60. [68]

    Qiushi Han, Zhenwei Lin, Hanwen Liu, Caihua Chen, Qi Deng, Dongdong Ge, and Yinyu Ye,Ac- celerating low-rank factorization-based semidefinite programming algorithms on gpu, arXiv preprint arXiv:2407.15049 (2024)

    2024 arXiv

  61. [69]

    2, 235–244

    Peter Hazell and Pasquale Scandizzo,Competitive demand structures under risk in agricultural linear programming models, American Journal of Agricultural Economics56(1974), no. 2, 235–244

    1974

  62. [70]

    1, 119–149

    Bingsheng He and Xiaoming Yuan,Convergence analysis of primal-dual algorithms for a saddle-point problem: from contraction perspective, SIAM Journal on Imaging Sciences5(2012), no. 1, 119–149

    2012

  63. [71]

    2, 700–709

    ,On the o(1/n) convergence rate of the douglas–rachford alternating direction method, SIAM Journal on Numerical Analysis50(2012), no. 2, 700–709

    2012

  64. [72]

    Oliver Hinder,Worst-case analysis of restarted primal-dual hybrid gradient on totally unimodular linear programs, Operations Research Letters57(2024), 107199

    2024

  65. [73]

    Alan J Hoffman,On approximate solutions of systems of linear inequalities, Journal of Research of the National Bureau of Standards49(1952), 263–265

    1952

  66. [74]

    Yicheng Huang, Wanyu Zhang, Hongpei Li, Dongdong Ge, Huikang Liu, and Yinyu Ye,Restarted primal-dual hybrid conjugate gradient method for large-scale quadratic programming, arXiv preprint arXiv:2405.16160 (2024)

    2024 arXiv

  67. [75]

    vol 66, 366-422] (1939)

    L V Kantarovich,Mathematical methods in the organization and planning of production, Publication House of the Leningrad State University.[Translated in Management Sc. vol 66, 366-422] (1939)

    1939

  68. [76]

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

    1984

  69. [77]

    Nils-Christian Kempke and Thorsten Koch,Low-precision first-order method-based fix-and-propagate heuristics for large-scale mixed-integer linear optimization, arXiv preprint arXiv:2503.10344 (2025)

    2025

  70. [78]

    1, 53–72

    Leonid G Khachiyan,Polynomial algorithms in linear programming, USSR Computational Mathemat- ics and Mathematical Physics20(1980), no. 1, 53–72. 43

    1980

  71. [79]

    1, 57–87

    Donghwan Kim,Accelerated proximal point method for maximally monotone operators, Mathematical Programming190(2021), no. 1, 57–87

    2021

  72. [80]

    3, 159–175

    Victor Klee and George J Minty,How good is the simplex algorithm, Inequalities3(1972), no. 3, 159–175

    1972

  73. [81]

    thesis, Paderborn University, Germany, 2005

    Achim Koberstein,The dual simplex method, techniques for a fast and stable implementation, Ph.D. thesis, Paderborn University, Germany, 2005

    2005

  74. [82]

    1, Springer, 2011

    Bernhard H Korte, Jens Vygen, B Korte, and J Vygen,Combinatorial optimization, vol. 1, Springer, 2011

    2011

  75. [83]

    Carlton Lemke,The constrained gradient method of linear programming, Journal of the Society for Industrial and Applied Mathematics9(1961), no. 1, 1–17

    1961

  76. [84]

    1, 501–546

    Adrian S Lewis and Stephen J Wright,A proximal method for composite minimization, Mathematical Programming158(2016), no. 1, 501–546

    2016

  77. [85]

    1, 408–437

    Jingwei Liang, Jalal Fadili, and Gabriel Peyr´ e,Activity identification and local linear convergence of forward–backward-type methods, SIAM Journal on Optimization27(2017), no. 1, 408–437

    2017

  78. [86]

    3, 874–913

    ,Local convergence properties of Douglas–Rachford and alternating direction method of multi- pliers, Journal of Optimization Theory and Applications172(2017), no. 3, 874–913

    2017

  79. [87]

    6, 821–853

    ,Local linear convergence analysis of primal–dual splitting methods, Optimization67(2018), no. 6, 821–853

    2018

  80. [88]

    2, 405–418

    Felix Lieder,On the convergence rate of the halpern-iteration, Optimization letters15(2021), no. 2, 405–418

    2021

  81. [89]

    Zhenwei Lin, Zikai Xiong, Dongdong Ge, and Yinyu Ye,Pdcs: A primal-dual large-scale conic pro- gramming solver with gpu enhancements, arXiv preprint arXiv:2505.00311 (2025)

    2025

  82. [90]

    2, 288–310

    Qian Liu and Garrett Van Ryzin,On the choice-based linear programming model for network revenue management, Manufacturing & Service Operations Management10(2008), no. 2, 288–310

    2008

  83. [91]

    Tianhao Liu and Haihao Lu,A new crossover algorithm for lp inspired by the spiral dynamic of pdhg, arXiv preprint arXiv:2409.14715 (2024)

    2024 arXiv

  84. [92]

    Haihao Lu, Zedong Peng, and Jinwen Yang,Mpax: Mathematical programming in jax, arXiv preprint arXiv:2412.09734 (2024)

    2024

  85. [93]

    Haihao Lu, Duncan Simester, and Yuting Zhu,Optimizing scalable targeted marketing policies with constraints, arXiv preprint arXiv:2312.01035 (2023)

    2023 arXiv

  86. [94]

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

    2022 arXiv

  87. [95]

    jl: A gpu implementation of restarted primal-dual hybrid gradient for linear program- ming in julia, arXiv preprint arXiv:2311.12180 (2023)

    ,cupdlp. jl: A gpu implementation of restarted primal-dual hybrid gradient for linear program- ming in julia, arXiv preprint arXiv:2311.12180 (2023)

    2023 arXiv

  88. [96]

    ,On a unified and simplified proof for the ergodic convergence rates of ppm, pdhg and admm, arXiv preprint arXiv:2305.02165 (2023)

    2023 arXiv

  89. [97]

    ,On the geometry and refined rate of primal-dual hybrid gradient for linear programming, arXiv preprint arXiv:2307.03664 (2023)

    2023 arXiv

  90. [98]

    ,A practical and optimal first-order method for large-scale convex quadratic programming, arXiv preprint arXiv:2311.07710 (2023)

    2023 arXiv

  91. [99]

    ,Pdot: A practical primal-dual algorithm and a gpu-based solver for optimal transport, arXiv preprint arXiv:2407.19689 (2024)

    2024 arXiv

  92. [100]

    ,Restarted halpern pdhg for linear programming, arXiv preprint arXiv:2407.16144 (2024). 44

    2024 arXiv

  93. [101]

    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)

    2023 arXiv

  94. [102]

    Haihao Lu and Luyang Zhang,The power of linear programming in sponsored listings ranking: Evidence from field experiments, arXiv preprint arXiv:2403.14862 (2024)

    2024

  95. [103]

    61, Springer Science & Business Media, 2002

    Istv´ an Maros,Computational techniques of the simplex method, vol. 61, Springer Science & Business Media, 2002

    2002

  96. [104]

    4, 575–601

    Sanjay Mehrotra,On the implementation of a primal-dual interior point method, SIAM Journal on optimization2(1992), no. 4, 575–601

    1992

  97. [105]

    Gaspard Monge,The founding fathers of optimal transport, 1781

  98. [106]

    1, 229–251

    Arkadi Nemirovski,Prox-method with rate of convergence o (1/t) for variational inequalities with lips- chitz continuous monotone operators and smooth convex-concave saddle point problems, SIAM Journal on Optimization15(2004), no. 1, 229–251

    2004

  99. [107]

    Yu E Nesterov and Michael J Todd,Self-scaled barriers and interior-point methods for convex pro- gramming, Mathematics of Operations research22(1997), no. 1, 1–42

    1997

  100. [108]

    2, 324–364

    ,Primal-dual interior-point methods for self-scaled cones, SIAM Journal on optimization8 (1998), no. 2, 324–364

    1998

  101. [109]

    87, Springer Science & Business Media, 2003

    Yurii Nesterov,Introductory lectures on convex optimization: A basic course, vol. 87, Springer Science & Business Media, 2003

    2003

  102. [110]

    137, Springer, 2018

    Yurii Nesterov et al.,Lectures on convex optimization, vol. 137, Springer, 2018

    2018

  103. [111]

    Yurii Nesterov and Arkadi Nemirovskii,Interior-point polynomial algorithms in convex programming, SIAM, 1994

    1994

  104. [112]

    nvidia.com/en-us/high-performance-computing/

    NVIDIA,High-performance computing: Accelerating the rate of scientific discovery.,https://www. nvidia.com/en-us/high-performance-computing/

  105. [113]

    ,Why gpus are great for ai.,https://blogs.nvidia.com/blog/ why-gpus-are-great-for-ai/

  106. [114]

    3, 1999–2023

    Brendan O’Donoghue,Operator splitting for a homogeneous embedding of the linear complementarity problem, SIAM Journal on Optimization31(2021), no. 3, 1999–2023

    2021

  107. [115]

    1, 85–108

    Daniel O’Connor and Lieven Vandenberghe,On the equivalence of the primal-dual hybrid gradient method and douglas–rachford splitting, Mathematical Programming179(2020), no. 1, 85–108

    2020

  108. [116]

    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 Applications169 (2016), 1042–1068

    2016

  109. [117]

    1, 184–203

    Fran¸ cois Pacaud, Sungho Shin, Michel Schanen, Daniel Adrian Maldonado, and Mihai Anitescu,Accel- erating condensed interior-point methods on simd/gpu architectures, Journal of Optimization Theory and Applications202(2024), no. 1, 184–203

    2024

  110. [118]

    17420–17457

    Jisun Park and Ernest K Ryu,Exact optimal accelerated complexity for fixed-point iterations, Interna- tional Conference on Machine Learning, PMLR, 2022, pp. 17420–17457

    2022

  111. [119]

    Amnon Pazy,Asymptotic behavior of contractions in hilbert space, Israel Journal of Mathematics9 (1971), 235–240

    1971

  112. [120]

    2, 534–550

    Javier Pena,Understanding the geometry of infeasible perturbations of a conic linear system, SIAM Journal on Optimization10(2000), no. 2, 534–550

    2000

  113. [121]

    Javier Pena, Juan C Vera, and Luis F Zuluaga,New characterizations of hoffman constants for systems of linear constraints, Mathematical Programming187(2021), 79–109. 45

    2021

  114. [122]

    1, 323–335

    Javier F Pe˜ na,An easily computable upper bound on the hoffman constant for homogeneous inequality systems, Computational Optimization and Applications87(2024), no. 1, 323–335

    2024

  115. [123]

    5-6, 355–607

    Gabriel Peyr´ e, Marco Cuturi, et al.,Computational optimal transport: With applications to data sci- ence, Foundations and Trends®in Machine Learning11(2019), no. 5-6, 355–607

    2019

  116. [124]

    1762–1769

    Thomas Pock and Antonin Chambolle,Diagonal preconditioning for first order primal-dual algorithms in convex optimization, 2011 International Conference on Computer Vision, IEEE, 2011, pp. 1762–1769

    2011

  117. [125]

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

    2020 arXiv

  118. [126]

    1-3, 59–93

    James Renegar,A polynomial-time algorithm, based on newton ’s method, for linear programming, Mathematical programming40(1988), no. 1-3, 59–93

    1988

  119. [127]

    report, Cornell University Operations Research and Industrial Engineering, 1993

    ,Some perturbation theory for linear programming, Tech. report, Cornell University Operations Research and Industrial Engineering, 1993

    1993

  120. [128]

    3, 506–524

    ,Incorporating condition measures into the complexity theory of linear programming, SIAM Journal on Optimization5(1995), no. 3, 506–524

    1995

  121. [129]

    1, 279–351

    ,Linear programming, complexity theory and elementary functional analysis, Mathematical Programming70(1995), no. 1, 279–351

    1995

  122. [130]

    ,A mathematical view of interior-point methods in convex optimization, SIAM, 2001

    2001

  123. [131]

    Stephen M Robinson,Some continuity properties of polyhedral multifunctions, Springer, 1981

    1981

  124. [132]

    5, 877–898

    R Tyrrell Rockafellar,Monotone operators and the proximal point algorithm, SIAM journal on control and optimization14(1976), no. 5, 877–898

    1976

  125. [133]

    317, Springer Science & Business Media, 2009

    R Tyrrell Rockafellar and Roger J-B Wets,Variational analysis, vol. 317, Springer Science & Business Media, 2009

    2009

  126. [134]

    Ben Rosen,The gradient projection method for nonlinear programming

    J. Ben Rosen,The gradient projection method for nonlinear programming. part ii. nonlinear constraints, Journal of the Society for Industrial and Applied Mathematics9(1961), no. 4, 514–532

    1961

  127. [135]

    Ed Rothberg,New options for solving giant lps, 2024,https://cdn.gurobi.com/wp-content/ uploads/New-Options-for-Solving-Giant-LPs.pdf

    2024

  128. [136]

    report, CM-P00040415, 2001

    Daniel Ruiz,A scaling algorithm to equilibrate both rows and columns norms in matrices, Tech. report, CM-P00040415, 2001

    2001

  129. [137]

    Ernest K Ryu and Wotao Yin,Large-scale convex optimization: algorithms & analyses via monotone operators, Cambridge University Press, 2022

    2022

  130. [138]

    Ruhul Amin Sarker and Charles S Newton,Optimization modelling: a practical approach, CRC press, 2007

    2007

  131. [139]

    Alexander Schrijver,Theory of linear and integer programming, John Wiley & Sons, 1998

    1998

  132. [140]

    Sungho Shin, Carleton Coffrin, Kaarthik Sundar, and Victor M Zavala,Graph-based modeling and decomposition of energy infrastructures, arXiv preprint arXiv:2010.02404 (2020)

    2020 arXiv

  133. [141]

    Sungho Shin, Fran¸ cois Pacaud, and Mihai Anitescu,Accelerating optimal power flow with GPUs: SIMD abstraction of nonlinear programs and condensed-space interior-point methods, arXiv preprint arXiv:2307.16830 (2023)

    2023 arXiv

  134. [142]

    4, 637–672

    Bartolomeo Stellato, Goran Banjac, Paul Goulart, Alberto Bemporad, and Stephen Boyd,Osqp: An operator splitting solver for quadratic programs, Mathematical Programming Computation12(2020), no. 4, 637–672

    2020

  135. [143]

    shanshu.ai/news/breaking-barriers-in-linear-programming.html

    COPT team,Copt breaks barriers in linear programming with nvidia cuopt, 2025,https://www. shanshu.ai/news/breaking-barriers-in-linear-programming.html. 46

    2025

  136. [144]

    1-4, 545–581

    Kim-Chuan Toh, Michael J Todd, and Reha H T¨ ut¨ unc¨ u,Sdpt3—a matlab software package for semidef- inite programming, version 1.3, Optimization methods and software11(1999), no. 1-4, 545–581

    1999

  137. [145]

    Cara Touretzky, Robert Luce, and David Torres Sanchez,Using gpus to solve lps: What’s in it for me?, 2025,https://www.gurobi.com/resources/using-gpus-to-solve-lps-whats-in-it-for-me/

    2025

  138. [146]

    1-2, 237–252

    Paul Tseng,On linear convergence of iterative methods for the variational inequality problem, Journal of Computational and Applied Mathematics60(1995), no. 1-2, 237–252

    1995

  139. [147]

    org/documentation/coneprog

    Lieven Vandenberghe,The cvxopt linear and quadratic cone program solvers, Online: http://cvxopt. org/documentation/coneprog. pdf53(2010)

    2010

  140. [148]

    2, 245–261

    Juan Carlos Vera, Juan Carlos Rivera, Javier Pena, and Yao Hui,A primal–dual symmetric relaxation for homogeneous conic systems, Journal of Complexity23(2007), no. 2, 245–261

    2007

  141. [149]

    58, American Mathematical Soc., 2021

    C´ edric Villani,Topics in optimal transportation, vol. 58, American Mathematical Soc., 2021

    2021

  142. [150]

    338, Springer, 2009

    C´ edric Villani et al.,Optimal transport: old and new, vol. 338, Springer, 2009

    2009

  143. [151]

    Andreas W¨ achter and Lorenz T Biegler,On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming, Mathematical programming106(2006), 25–57

    2006

  144. [152]

    Stephen Wright,Primal-dual interior-point methods, SIAM, 1997

    1997

  145. [153]

    4, 1063–1079

    Stephen J Wright,Identifiable surfaces in constrained optimization, SIAM Journal on Control and Optimization31(1993), no. 4, 1063–1079

    1993

  146. [154]

    Zikai Xiong,Accessible theoretical complexity of the restarted primal-dual hybrid gradient method for linear programs with unique optima, arXiv preprint arXiv:2410.04043 (2024)

    2024 arXiv

  147. [155]

    ,High-probability polynomial-time complexity of restarted pdhg for linear programming, arXiv preprint arXiv:2501.00728 (2025)

    2025

  148. [156]

    Zikai Xiong and Robert M Freund,On the relation between lp sharpness and limiting error ratio and complexity implications for restarted pdhg, arXiv preprint arXiv:2312.13773 (2023)

    2023 arXiv

  149. [157]

    ,The role of level-set geometry on the performance of pdhg for conic linear optimization, arXiv preprint arXiv:2406.01942 (2024)

    2024 arXiv

  150. [158]

    Zikai Xiong and Robert Michael Freund,Computational guarantees for restarted pdhg for lp based on” limiting error ratios” and lp sharpness, arXiv preprint arXiv:2312.14774 (2023)

    2023

  151. [159]

    1, 53–67

    Yinyu Ye, Michael J Todd, and Shinji Mizuno,Ano( √nl)-iteration homogeneous and self-dual linear programming algorithm, Mathematics of operations research19(1994), no. 1, 53–67

    1994

  152. [160]

    2, 22–45

    David B Yudin and Arkadi S Nemirovskii,Informational complexity and efficient methods for the solution of convex extremal problems, Matekon13(1976), no. 2, 22–45

    1976

  153. [161]

    2, 437–460

    Xi Yin Zheng and Kung Fu Ng,Metric subregularity and constraint qualifications for convex generalized equations in banach spaces, SIAM Journal on Optimization18(2007), no. 2, 437–460

    2007

  154. [162]

    1, 154– 174

    Xi Yin Zheng and Kung Fu Ng,Metric subregularity of piecewise linear multifunctions and applications to piecewise linear multiobjective optimization, SIAM Journal on Optimization24(2014), no. 1, 154– 174

    2014

  155. [163]

    8, 2911–2916

    Peng Zhou and Beng Wah Ang,Linear programming models for measuring economy-wide energy effi- ciency performance, Energy Policy36(2008), no. 8, 2911–2916

    2008

  156. [164]

    Mingqiang Zhu and Tony Chan,An efficient primal-dual hybrid gradient algorithm for total variation image restoration, Ucla Cam Report34(2008), 8–34

    2008

  157. [165]

    Guus Zoutendijk,Methods of feasible directions, 1960 (1960)

    1960

  158. [166]

    ,Some algorithms based on the principle of feasible directions, Nonlinear programming, Elsevier, 1970, pp. 93–121. 47

    1970

Pith tools

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