Pith. sign in

REVIEW 3 major objections 4 minor 58 references

GPU-Accelerated Conic Quadratic Programming with Local Linear Convergence under Strict Complementarity

T0 review · 3 major / 4 minor · reviewed 2026-08-11 · deepseek-v4-flash

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

Pith's one-line read Restarted averaged PDHG converges locally linearly for conic quadratic programs under strict complementarity, and a GPU implementation scales to hundreds of millions of variables.

desk verdict A serious GPU conic-QP solver with a genuine local linear convergence theorem, but the explicit contraction constant in Proposition 3.12 is wrong as written and the implemented acceleration is outside the theory. read the letter →

arxiv 2608.09159 v1 pith:WPDDIBTG submitted 2026-08-10 math.OC cs.DCcs.MS

Hongpei Li , Yicheng Huang , Huikang Liu , Dongdong Ge , Yinyu Ye This is my paper · ORCID
classification math.OCcs.DCcs.MS MSC 90C2090C2590C0665K05
keywords conicquadraticprogrammingprimal-dualhybridgradientlocallinearconvergencestrictcomplementarityGPUaccelerationmatrix-freeoptimizationsmootheddualitygaplarge-scale
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 paper establishes that a restarted averaged primal-dual hybrid gradient method, PDHCG-CQP, converges locally linearly for conic convex quadratic programming whenever the smoothed primal-dual gap grows quadratically near the solution set. It then proves that this quadratic growth holds under strict complementarity for products of nonnegative, second-order, rotated second-order, and positive-semidefinite cones. The convergence proof covers inexact proximal solves, so each iteration needs only matrix-vector products and cone projections, not factorizations. The result is a matrix-free GPU solver with a proven geometric contraction rate, demonstrated on instances with up to 4.4×$10^{8}$ stored primal coordinates and on multiple GPUs. This matters because previous first-order conic solvers either reformulate the quadratic objective at extra cost or lack a local linear convergence guarantee under strict complementarity.

What carries the argument

The load-bearing object is the smoothed duality gap $G_\xi(z; z_\star)$ of Definition 2.1, which penalizes the distance of the comparison point to a fixed center. One epoch's Cesàro averaging converts PDHG energy inequalities into an $O(1/T)$ bound on this gap, and uniform quadratic growth of the gap, Assumption 2.2, converts that bound into a geometric contraction of the distance to the KKT set. The paper verifies Assumption 2.2 by decomposing the smoothed gap into primal and dual error bounds, proving the primal bound through a rotated second-order-cone epigraph lifting of $Q = B^*B$ combined with complementarity error bounds under primal strict complementarity, and proving the dual bound through slack-set linear regularity and normal-cone calmness under dual strict complementarity. Strict complementarity makes the relevant complementary faces constant along the local KKT stratum, which supplies the uniform constants the convergence theorem needs.

What would settle it

Run PDHCG-CQP on a family of small conic QPs whose optimal solution moves continuously from a strictly complementary interior-face point to a non-strictly-complementary boundary point, such as an SOCP where the optimal slack's smallest nonzero eigenvalue tends to zero. If the per-epoch distance-to-KKT residual stays geometric throughout the boundary family, the strict-complementarity regime is too narrow; if decay degrades to sublinear exactly at the transition, the central claim is corroborated. A direct algebraic check is to track the constants in the slack-regularity and normal-cone calmness assumptions along the family, since the smallest nonzero eigenvalue or boundary-ray distance should approach zero precisely at the transition.

Watch

Extended reading notes

Core claim

The central claim is Theorem 2.5: under uniform local quadratic growth of the smoothed gap, each epoch of restarted averaged PDHG contracts the distance to the KKT set by a fixed factor, $d_n \le q_\eta^n d_0$, even when the primal proximal subproblems are solved only inexactly within a relative error budget. Corollary 3.13 verifies the required quadratic growth: if every local KKT center in a neighborhood is strictly complementary and the cone is a finite product of nonnegative, Lorentz (including rotated Lorentz), and positive-semidefinite cones, then the smoothed gap is bounded below by a constant times the squared distance to the KKT set. Together these statements extend the principle of global convergence followed by strict-complementarity-driven local linear convergence, previously established for semidefinite programming, to conic quadratic programs with a native quadratic objective.

Load-bearing premise

The linear rate relies on the assumption that every KKT point near the solution is strictly complementary and that the resulting regularity constants stay bounded uniformly; if the iterates approach a solution on a face-transition boundary where strict complementarity fails, the uniformity breaks and the contraction proof no longer applies.

Editorial extensions

If this is right

  • The method is a matrix-free, GPU-resident conic QP solver with a proven local linear rate, so users get the scalability of PDHG without giving up a convergence guarantee near strictly complementary solutions.
  • Quadratic objectives are kept natively, avoiding the rotated-second-order-cone epigraph reformulation that linear-objective conic solvers need; the paper's comparisons show that reformulation roughly triples the outer iteration count and adds per-iteration lifted projections.
  • Inexact proximal solves preserve the geometric rate: a fixed number of warm-started projected-gradient steps per subproblem, logarithmic in the restart length, is enough to satisfy the error budget.
  • The theory covers products of nonnegative, second-order, rotated second-order, and positive-semidefinite cones, while the implementation additionally supports exponential and power cones with the same algorithm.
  • On the tested benchmarks the solver solves more standard QP instances than the other tested first-order solvers and is the only solver reported as reaching optimality on the largest market-equilibrium instances, which have over 4.4×10^8 stored primal coordinates.

Reading between the lines

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

  • A testable prediction is that on instances where the limiting KKT point sits at a face-transition boundary and strict complementarity fails, the residual decay should slow from geometric to sublinear, revealing exactly where the local regularity assumptions break.
  • The smoothed-gap quadratic-growth certificate is solver-independent, so the same Assumption 2.2 could be checked for other first-order conic methods to give them the same local rate whenever their epoch averages satisfy an analogous gap bound.
  • The paper's explicit relation between inner work and the condition number of the proximal subproblem suggests a practical diagnostic: measuring proximal error decay as a function of projected-gradient steps should match the predicted geometric factor, letting users choose inner iterations without tuning.
  • Because the convergence guarantee is local, the practical outcome depends on whether global PDHG dynamics drive iterates into a strictly complementary stratum; warm-starting from a cheap first-order run could be the principled way to reach that regime.
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 / 4 minor

Summary. The paper proposes PDHCG-CQP, a matrix-free GPU solver for large-scale conic convex quadratic programs, and analyzes a restarted averaged primal-dual hybrid gradient method applied to the saddle formulation. The central theoretical claim is that, under a uniform local quadratic-growth condition on the smoothed duality gap, the restarted averaged method with exact or inexact primal proximal solves contracts the distance to the KKT set geometrically (Theorem 2.5). The paper then verifies the quadratic-growth condition for products of nonnegative, second-order, rotated second-order, and positive-semidefinite cones under blockwise strict complementarity, using a rotated-SOC epigraph lifting, a primal error bound, and a dual error bound derived from slack regularity and normal-cone calmness (Corollary 3.13). The practical solver adds reflected-Halpern acceleration, adaptive restarts, adaptive inner tolerances, Jacobi preconditioning, and a multi-GPU implementation, and the paper reports extensive experiments on QP, QCQP, SOCP, Lasso, and Fisher-equilibrium benchmarks, including instances with up to 4.4e8 stored primal coordinates.

Significance. If the theory is correct, the paper makes a valuable contribution: it extends the recent strict-complementarity-driven local linear convergence results from semidefinite programming to a broad class of conic quadratic programs, and it ships an open-source, matrix-free, single- and multi-GPU solver that is competitive with or better than existing first-order solvers on several large-scale benchmarks. The experiment section is unusually thorough, with public benchmarks, large synthetic instances, ablations, and distributed scaling results. The theoretical sections are structured around a clean sufficient condition (Assumption 2.2), and the appendices provide derivations for the main results. However, the paper currently contains a concrete quantitative error in the proof of the dual error bound, and the implemented algorithm differs from the analyzed one in ways that are not covered by the convergence theorems. These issues are repairable, and the qualitative local convergence claim appears defensible after correction.

major comments (3)
  1. [Appendix B.7 / Proposition 3.12 / Eq. (37)] The proof of Proposition 3.12 contains an invalid inequality. The text bounds dist(s*(y), F_x*) by ||M_xi r_y|| + kappa_B ||r_y|| and then claims this is at most (L_xi + kappa_B sqrt(lambda_xi)) ||r_y||_{M_xi}. Since ||r_y|| <= lambda_xi^{-1/2} ||r_y||_{M_xi}, a valid uniform bound from the preceding line is (L_xi + kappa_B)/sqrt(lambda_xi) ||r_y||_{M_xi}; the displayed coefficient L_xi + kappa_B sqrt(lambda_xi) can be smaller when lambda_xi < 1 and the inequality is false. For example, with Q=0, xi=0.1, M_xi=0.1I, L_xi=0.1, lambda_xi=0.1, and kappa_B=0, the claimed inequality would assert 0.1||r|| <= 0.0316||r||, which fails for every nonzero r. Consequently, the explicit constant kappa_D in Proposition 3.12 and the formula for alpha_xi in Eq. (37), which feed the contraction ratio in Theorem 2.5, are not established as written. The qualitative existence of a finite kappa_D is easily repaired with the corrected coefficient, so the central theorem is not void, but the displayed quantitative claims must be corrected.
  2. [Section 4.2.1 / Theorem 2.5] The convergence analysis applies to the restarted averaged scheme of Algorithm 1, but the implemented solver uses the reflected-Halpern recursion (46), the adaptive restart rule (61), the PID primal-weight update (58)-(59), and the adaptive inner tolerance (52)-(53). No theorem in Section 2 or Appendix A covers these recursions. The statement that the reflected-Halpern recursion is 'an implementation enhancement built on the same PDHG operator' does not transfer the local linear convergence guarantee. In particular, the relative proximal-error budget (18) is never shown to hold for the adaptive projected-BB inner loop; Proposition 2.6 analyzes fixed projected-gradient work only. The title and abstract promise local linear convergence of PDHCG-CQP, but the proved statement is for the simplified restarted averaged method. Please either extend the analysis to the implemented scheme or explicitly delimit the theoretical guarantee to the averaged method and present the enhanced solver as an empirical variant.
  3. [Appendix B.6 / Proposition 3.11] The verification of uniform normal-cone calmness is presented as a sketch rather than a complete proof. For the PSD block, the argument introduces an unspecified absolute constant C, and the SOC boundary case is treated by saying it is 'the same computation' with lambda_min replaced by the distance from the cone vertex. Since Assumption 3.10 is one of the two regularity conditions needed for the dual error bound, and since Corollary 3.13 relies on the uniformity over the local KKT stratum, the proof should spell out the blockwise neighborhoods and moduli, including the boundary-ray case for SOC blocks and the product-cone assembly. This is a completeness issue rather than a demonstrated error, but it needs to be resolved before the quantitative verification of quadratic growth is complete.
minor comments (4)
  1. [Section 3.2.2 / Eq. (36)] The statement of Assumption 3.10 uses a neighborhood W_B of (bar x, -bar s) but the paper does not explicitly note that the pairs (x*, -s*(y)) used in the dual error bound lie in that neighborhood after shrinking V_D and V_y; adding this sentence would make the uniformity argument easier to follow.
  2. [Section 5.1 / Experimental setup] For reproducibility, please report the exact versions or commits of the baseline solvers (especially SCS, OSQP, PDCS, and the interior-point solvers) and the precise feasibility and optimality tolerances used by each solver, since first-order solver comparisons are sensitive to termination criteria.
  3. [Section 4.1 / Eq. (40)-(42)] The projected Barzilai-Borwein method is described as the practical inner solver for general Q, but Proposition 2.6 analyzes projected gradient with a fixed stepsize and fixed number of steps. The paper should clarify that the BB variant and the adaptive stopping rule are empirical enhancements whose convergence properties are not covered by the theoretical results.
  4. [Section 5.4 / Table 7] The SOCP benchmark comparison is reported at two tolerances only; reporting a third tolerance (for example 1e-8, as in the QCQP table) would give a more complete picture of the accuracy behavior on SOCP instances.

Circularity Check

0 steps flagged · score 1.0 of 10

No significant circularity: the convergence proof is a conditional derivation from a stated quadratic-growth assumption verified through external error-bound results, and the self-citations appear only as baselines or implementation components.

full rationale

The central claim, Theorem 2.5, is explicitly conditional: under Assumption 2.2 (uniform local quadratic growth of the smoothed gap), restarted averaged PDHG with exact or inexact proximal solves contracts the distance to the KKT set geometrically. Assumption 2.2 is not silently identified with the conclusion; Section 3 independently characterizes it (Theorem 3.4) as equivalent to a primal and a dual error bound, and then verifies those bounds under strict complementarity using the lifted residual error bound of Ding and Udell [15], slack regularity, and normal-cone calmness. The algorithmic and implementation components, such as reflected-Halpern acceleration, Ruiz/Pock-Chambolle rescaling, and the two-dimensional distributed partition, are supported by external references ([32], [39], [51], [49]) or by the paper's own empirical comparisons, not by the convergence theorem. Citations to the authors' own PDHCG [25], D-PDLP [28], PDCS [30], and COPT [21] are used as historical context, baselines, or implementation references; none carries the proof of either the contraction result or the quadratic-growth verification. No fitted parameter is relabeled as a prediction, and the numerical claims are benchmarked against external solvers and instance sets. A separate review concern about the explicit constant in Proposition 3.12 is a quantitative correctness issue, not a circularity: it does not show that any prediction reduces by construction to an input, and the qualitative existence of a finite dual-error-bound constant is repairable independently of the central derivation structure. Overall, the paper's derivation chain is self-contained apart from normal external citations, and there is no load-bearing self-citation or definitional circularity.

Assumptions & free parameters 8 free parameters · 7 assumptions · 0 invented entities

The central mathematical claim rests on standard convex analysis, a strong strict-complementarity condition, and two uniformity assumptions on the local solution stratum. The practical solver adds a set of hand-tuned hyperparameters that are not part of the convergence proof. No new physical or mathematical entities are postulated.

free parameters (8)
  • eta = 0.998 / ||A||_2
    Primal-dual stepsize factor chosen as in cuPDLPx; not derived from theory, affects convergence speed.
  • inner tolerance initial eps_in0 = 1e-3
    Starting tolerance for adaptive inner solve; tuned for benchmark performance.
  • inner tolerance decay gamma_in = 5e-4
    Decay factor in adaptive inner tolerance; heuristic.
  • inner tolerance floor eps_min = 1e-9
    Lower bound on inner tolerance; chosen for high accuracy.
  • restart thresholds (beta_s, beta_n, beta_a) = 0.20, 0.80, 0.36
    Adaptive restart conditions; hand-tuned.
  • PID gains (beta_I, KP, KI, KD) = 0.30, 0.99, 0.01, 0.00
    Primal weight update gains; heuristic from control analogy.
  • reflection coefficient rho = 1.00
    Reflected-Halpern coefficient; chosen for empirical acceleration.
  • epoch length T = adaptive, not fixed
    The theory requires T >= max(2 lambda_+/xi, e^2 lambda_+/alpha_xi) with unknown constants; the implementation uses adaptive restart instead.
assumptions (7)
  • standard math Z* nonempty and KKT conditions (3) characterize saddle points
    Assumed throughout; standard for convex cones with constraint qualification, stated in Section 1.2.
  • standard math tau*sigma*||A||^2 < 1
    Stepsize condition (7) for PDHG stability.
  • domain assumption K is a finite product of nonnegative, SOC, RSOC, and PSD cones in the theory (Corollary 3.13)
    Section 3.3 Corollary 3.13 states the cone classes; Section 4 supports exponential/power cones without convergence guarantee.
  • domain assumption Strict complementarity along the local KKT stratum: every z* in Z* cap V_SC satisfies x*+s* in int K
    Corollary 3.13, Section 3.3; this is the central sufficient condition for quadratic growth.
  • domain assumption Uniform local slack regularity (Assumption 3.8) and uniform normal-cone calmness (Assumption 3.10) hold on the stratum
    These are extra regularity conditions needed for the dual error bound; verified for common cones under D-SC via Corollary 3.9 and Proposition 3.11.
  • domain assumption Error bound [15] applies to the lifted problem (Assumption 3.5)
    Proposition 3.6 relies on [15, Corollary 1] for the lifted product cone; this is an external theorem.
  • ad hoc to paper Inner solver satisfies relative error budget (18) with epsilon_n <= eta d_n
    Theorem 2.5 requires this condition; Proposition 2.6 shows a fixed number of PG steps satisfies it with unknown local constants.

how reviews work

0 comments
Cite this review

Pith. "Pith review of GPU-Accelerated Conic Quadratic Programming with Local Linear Convergence under Strict Complementarity." pith.science (2026). https://pith.science/paper/WPDDIBTG

@misc{pith2026260809159,
  author       = {Pith},
  title        = {Pith review of: GPU-Accelerated Conic Quadratic Programming with Local Linear Convergence under Strict Complementarity},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/WPDDIBTG}},
  note         = {Machine review of arXiv:2608.09159}
}
abstract

We present PDHCG-CQP, a GPU-accelerated first-order solver for large-scale conic convex quadratic programming. PDHCG-CQP supports affine constraints and Cartesian products of nonnegative, second-order, rotated second-order, exponential, and three-dimensional power cones. At its core is a restarted averaged primal-dual hybrid gradient (PDHG) method, whose primal update is computed inexactly by solving a conic quadratic proximal subproblem with projected gradient iterations. We establish local linear convergence of the restarted averaged scheme with both exact and inexact primal proximal evaluations under a uniform local quadratic-growth condition on the smoothed primal-dual gap. We further show that this condition holds under strict complementarity by exploiting a rotated second-order-cone lifting together with local primal and dual regularity conditions. Our C/CUDA implementation combines matrix-free linear algebra, batched cone projections, adaptive inner solves, reflected-Halpern acceleration, and fully device-resident KKT residual computations. It also supports multi-GPU execution through a two-dimensional partitioning of the problem data. Extensive experiments on standard and large-scale quadratic programming (QP), convex quadratically constrained quadratic programming (QCQP), second-order cone programming (SOCP), and quasilinear Fisher equilibrium benchmarks demonstrate that PDHCG-CQP achieves state-of-the-art robustness among first-order solvers while scaling efficiently to 8 GPUs and instances with up to $4.4\times10^8$ stored primal coordinates. PDHCG-CQP is open source and available at https://github.com/Lhongpei/PDHCG.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

58 extracted references · 39 canonical work pages

  1. [1]

    Haeberly, and Michael L

    Farid Alizadeh, Jean-Pierre A. Haeberly, and Michael L. Overton. Complementarity and nondegeneracy in semidefinite programming.Mathematical Programming, 77(1):111–128, 1997. doi: 10.1007/BF02614432

    work page doi:10.1007/bf02614432 1997

  2. [2]

    Practical large-scale linear programming using primal-dual hybrid gradient.Advances in Neural Information Processing Systems, 34:20243–20257, 2021

    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:20243–20257, 2021

    2021

  3. [3]

    Bauschke, Jonathan M

    Heinz H. Bauschke, Jonathan M. Borwein, and Wu Li. Strong conical hull intersection property, bounded linear regularity, Jameson’s property (G), and error bounds in convex optimization.Mathematical Programming, 86(1): 135–160, 1999. doi: 10.1007/s101079900086

    work page doi:10.1007/s101079900086 1999

  4. [4]

    A scaled gradient projection method for constrained image deblurring.Inverse Problems, 25(1):015002, 2009

    Silvia Bonettini, Riccardo Zanella, and Luca Zanni. A scaled gradient projection method for constrained image deblurring.Inverse Problems, 25(1):015002, 2009

    work page 2009

  5. [5]

    A first-order primal-dual algorithm for convex problems with applications to imaging.Journal of Mathematical Imaging and Vision, 40:120–145, 2011

    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:120–145, 2011. 24 PREPRINT. UNDER REVIEW

    work page 2011

  6. [6]

    On the ergodic convergence rates of a first-order primal-dual algorithm

    Antonin Chambolle and Thomas Pock. On the ergodic convergence rates of a first-order primal-dual algorithm. Mathematical Programming, 159(1):253–287, 2016

    work page 2016

  7. [7]

    LIBSVM: a library for support vector machines.ACM Transactions on Intelligent Systems and Technology (TIST), 2(3):1–27, 2011

    Chih-Chung Chang and Chih-Jen Lin. LIBSVM: a library for support vector machines.ACM Transactions on Intelligent Systems and Technology (TIST), 2(3):1–27, 2011

    work page 2011

  8. [8]

    Chari and Behçet Açıkme¸ se

    Govind M. Chari and Behçet Açıkme¸ se. QOCO-GPU: A quadratic objective conic optimizer with GPU accelera- tion.arXiv preprint arXiv:2603.29197, 2026

    work page arXiv 2026

Show all 58 references
  1. [9]

    Hpr-qp: A dual halpern peaceman-rachford method for solving large-scale convex composite quadratic programming.arXiv preprint arXiv:2507.02470, 2025

    Kaihuang Chen, Defeng Sun, Yancheng Yuan, Guojun Zhang, and Xinyuan Zhao. Hpr-qp: A dual halpern peaceman-rachford method for solving large-scale convex composite quadratic programming.arXiv preprint arXiv:2507.02470, 2025

    2025 arXiv

  2. [10]

    CuClarabel: GPU acceleration for a conic optimization solver.arXiv preprint arXiv:2412.19027, 2024

    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

  3. [11]

    Invariance and efficiency of convex representations.Mathematical Programming, 111(1–2):113–140, 2008

    Chek Beng Chua and Levent Tunçel. Invariance and efficiency of convex representations.Mathematical Programming, 111(1–2):113–140, 2008. doi: 10.1007/s10107-006-0072-6

    2008 doi

  4. [12]

    Projected Barzilai-Borwein methods for large-scale box-constrained quadratic programming.Numerische Mathematik, 100(1):21–47, 2005

    Yu-Hong Dai and Roger Fletcher. Projected Barzilai-Borwein methods for large-scale box-constrained quadratic programming.Numerische Mathematik, 100(1):21–47, 2005

    2005

  5. [13]

    The university of florida sparse matrix collection.ACM Transactions on Mathematical Software (TOMS), 38(1):1–25, 2011

    Timothy A Davis and Yifan Hu. The university of florida sparse matrix collection.ACM Transactions on Mathematical Software (TOMS), 38(1):1–25, 2011

    2011

  6. [14]

    An enhanced alternating direction method of multipliers-based interior point method for linear and conic optimization.INFORMS Journal on Computing, 37(2):338–359, 2025

    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, 37(...

    2025

  7. [15]

    A strict complementarity approach to error bound and sensitivity of solution of conic programs.Optimization Letters, 17(7):1551–1574, 2023

    Lin Ding and Madeleine Udell. A strict complementarity approach to error bound and sensitivity of solution of conic programs.Optimization Letters, 17(7):1551–1574, 2023

    2023

  8. [16]

    Consensus of subjective probabilities: The pari-mutuel method.The Annals of Mathematical Statistics, 30(1):165–168, 1959

    Edmund Eisenberg and David Gale. Consensus of subjective probabilities: The pari-mutuel method.The Annals of Mathematical Statistics, 30(1):165–168, 1959

    1959

  9. [17]

    Oxford Mathematical Monographs

    Jacques Faraut and Adam Korányi.Analysis on Symmetric Cones. Oxford Mathematical Monographs. Clarendon Press, Oxford, 1994

    1994

  10. [18]

    Quadratic error bound of the smoothed gap and the restarted averaged primal-dual hybrid gradient

    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

  11. [19]

    QPLIB: a library of quadratic programming instances

    Fabio Furini, Emiliano Traversi, Pietro Belotti, Antonio Frangioni, Ambros Gleixner, Nick Gould, Leo Liberti, Andrea Lodi, Ruth Misener, Hans Mittelmann, et al. QPLIB: a library of quadratic programming instances. Mathematical Programming Computation, 11:237–265, 2019

    2019

  12. [20]

    Infinite-dimensional fisher markets and tractable fair division.Operations Research, 71(2):688–707, 2023

    Yuan Gao and Christian Kroer. Infinite-dimensional fisher markets and tractable fair division.Operations Research, 71(2):688–707, 2023. doi: 10.1287/opre.2022.2344

    2023

  13. [21]

    Cardinal optimizer (copt) user guide.arXiv preprint arXiv:2208.14314, 2022

    Dongdong Ge, Qi Huangfu, Zizhuo Wang, Jian Wu, and Yinyu Ye. Cardinal optimizer (copt) user guide.arXiv preprint arXiv:2208.14314, 2022

    2022

  14. [22]

    Goldman and Albert W

    Alan J. Goldman and Albert W. Tucker. Theory of linear programming. In Harold W. Kuhn and Albert W. Tucker, editors,Linear Inequalities and Related Systems, number 38 in Annals of Mathematics Studies, pages 53–97. Princeton University Press, Princeton, NJ, 1956

    1956

  15. [23]

    Clarabel: An interior-point solver for conic programs with quadratic objectives

    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

  16. [24]

    https://www.gurobi.com

    Gurobi Optimization, LLC.Gurobi Optimizer Reference Manual, Version 12.0, 2024. https://www.gurobi.com. 25 PREPRINT. UNDER REVIEW

    2024

  17. [25]

    A restarted primal-dual hybrid conjugate gradient method for large-scale quadratic programming.INFORMS Journal on Computing, 2025

    Yicheng Huang, Wanyu Zhang, Hongpei Li, Dongdong Ge, Huikang Liu, and Yinyu Ye. A restarted primal-dual hybrid conjugate gradient method for large-scale quadratic programming.INFORMS Journal on Computing, 2025

    2025

  18. [26]

    Local linear convergence of the primal-dual hybrid gradient method for semidefinite programming

    Xin Jiang. Local linear convergence of the primal-dual hybrid gradient method for semidefinite programming. arXiv preprint arXiv:2607.08035, 2026

    2026 arXiv

  19. [27]

    Local linear convergence of the alternating direction method of multipliers for semidefinite programming under strict complementarity.arXiv preprint arXiv:2503.20142, 2025

    Shucheng Kang, Xin Jiang, and Heng Yang. Local linear convergence of the alternating direction method of multipliers for semidefinite programming under strict complementarity.arXiv preprint arXiv:2503.20142, 2025

    2025 arXiv

  20. [28]

    D-PDLP: Scaling PDLP to distributed multi-GPU systems.arXiv preprint arXiv:2601.07628, 2026

    Hongpei Li, Yicheng Huang, Huikang Liu, Dongdong Ge, and Yinyu Ye. D-PDLP: Scaling PDLP to distributed multi-GPU systems.arXiv preprint arXiv:2601.07628, 2026

    2026 arXiv

  21. [29]

    An ADMM-based interior-point method for large-scale linear programming.Optimization Methods and Software, 36(2-3):389–424, 2021

    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(2-3):389–424, 2021

    2021

  22. [30]

    A practical GPU-enhanced matrix-free primal-dual method for large-scale conic programs.arXiv preprint arXiv:2505.00311, 2025

    Zhenwei Lin, Zikai Xiong, Dongdong Ge, and Yinyu Ye. A practical GPU-enhanced matrix-free primal-dual method for large-scale conic programs.arXiv preprint arXiv:2505.00311, 2025

    2025

  23. [31]

    Lindstrom, Bruno F

    Scott B. Lindstrom, Bruno F. Lourenço, and Ting Kei Pong. Error bounds, facial residual functions and applications to the exponential cone.Mathematical Programming, 200(1):229–278, 2023. doi: 10.1007/s10107-022-01883-8

    2023 doi

  24. [32]

    Restarted reflected halpern acceleration for augmented primal- dual methods.arXiv preprint arXiv:2606.16552, 2026

    Benqi Liu, Ju Cao, Wotao Yin, and Zaiwen Wen. Restarted reflected halpern acceleration for augmented primal- dual methods.arXiv preprint arXiv:2606.16552, 2026

    2026

  25. [33]

    Computation of graphical derivatives of normal cone maps to a class of conic constraint sets.Set-Valued and Variational Analysis, 27(3):783–806, 2019

    Yulan Liu, Ying Sun, and Shaohua Pan. Computation of graphical derivatives of normal cone maps to a class of conic constraint sets.Set-Valued and Variational Analysis, 27(3):783–806, 2019. doi: 10.1007/s11228-018-0494-3

    2019 doi

  26. [34]

    Applications of second-order cone programming.Linear Algebra and its Applications, 284(1-3):193–228, 1998

    Miguel Sousa Lobo, Lieven Vandenberghe, Stephen Boyd, and Hervé Lebret. Applications of second-order cone programming.Linear Algebra and its Applications, 284(1-3):193–228, 1998

    1998

  27. [35]

    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

    2023 arXiv

  28. [36]

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

    Haihao Lu and Jinwen Yang. A practical and optimal first-order method for large-scale convex quadratic programming.arXiv preprint arXiv:2311.07710, 2023

    2023 arXiv

  29. [37]

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

    Haihao Lu and Jinwen Yang. Restarted halpern pdhg for linear programming.arXiv preprint arXiv:2407.16144, 2024

    2024 arXiv

  30. [38]

    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

    2023 arXiv

  31. [39]

    cupdlpx: A further enhanced gpu-based first-order solver for linear programming.arXiv preprint arXiv:2507.14051, 2025

    Haihao Lu, Zedong Peng, and Jinwen Yang. cupdlpx: A further enhanced gpu-based first-order solver for linear programming.arXiv preprint arXiv:2507.14051, 2025

    2025

  32. [40]

    Portfolio selection*.The Journal of Finance, 7(1):77–91, 1952

    Harry Markowitz. Portfolio selection*.The Journal of Finance, 7(1):77–91, 1952. doi: https://doi.org/10.1111/j. 1540-6261.1952.tb01525.x. URL https://onlinelibrary.wiley.com/doi/abs/10.1111/j.1540-6261.1952.tb01525.x

    1952

  33. [41]

    A repository of convex quadratic programming problems.Optimization Methods and Software, 11(1-4):671–681, 1999

    István Maros and Csaba Mészáros. A repository of convex quadratic programming problems.Optimization Methods and Software, 11(1-4):671–681, 1999

    1999

  34. [42]

    Mayne, James B

    David Q. Mayne, James B. Rawlings, Christopher V . Rao, and Pierre O. M. Scokaert. Constrained model predictive control: Stability and optimality.Automatica, 36(6):789–814, 2000

    2000

  35. [43]

    Decision tree for optimization software

    Hans Mittelmann. Decision tree for optimization software. http://plato.asu.edu/guide.html, 2021

    2021

  36. [44]

    Benchmark of second-order cone programming solvers

    Hans Mittelmann. Benchmark of second-order cone programming solvers. https://plato.asu.edu/ftp/socp.html, 2024

    2024

  37. [45]

    https://docs.mosek.com

    MOSEK ApS.The MOSEK Optimizer API for C Manual, Version 11.2, 2025. https://docs.mosek.com. 26 PREPRINT. UNDER REVIEW

    2025

  38. [46]

    https://github.com/ NVIDIA/cuopt

    NVIDIA Corporation.NVIDIA cuOpt: GPU-Accelerated Decision Optimization, 2025. https://github.com/ NVIDIA/cuopt

    2025

  39. [47]

    SCS: Splitting conic solver, version 3.2.4

    Brendan O’Donoghue, Eric Chu, Neal Parikh, and Stephen Boyd. SCS: Splitting conic solver, version 3.2.4. https://github.com/cvxgrp/scs, November 2023

    2023

  40. [48]

    Conic optimization via operator splitting and homogeneous self-dual embedding.Journal of Optimization Theory and Applications, 169:1042–1068, 2016

    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:1042–1068, 2016

    2016

  41. [49]

    Diagonal preconditioning for first order primal-dual algorithms in convex optimization

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

    2011

  42. [50]

    Robinson

    Stephen M. Robinson. Some continuity properties of polyhedral multifunctions.Mathematical Programming Study, 14:206–214, 1981

    1981

  43. [51]

    A scaling algorithm to equilibrate both rows and columns norms in matrices

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

    2001

  44. [52]

    Osqp: An operator splitting solver for quadratic programs.Mathematical Programming Computation, 12(4):637–672, 2020

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

    2020

  45. [53]

    Regression shrinkage and selection via the lasso.Journal of the Royal Statistical Society: Series B (Methodological), 58(1):267–288, 1996

    Robert Tibshirani. Regression shrinkage and selection via the lasso.Journal of the Royal Statistical Society: Series B (Methodological), 58(1):267–288, 1996. 27 PREPRINT. UNDER REVIEW. A Proof in Section 2 A.1 Proof of Theorem 2.3 The exact contraction is obtained in four step...

    1996

  46. [54]

    The second directional derivative off along this segment is ⟨d, Qd⟩, and hence ⟨d, Qd⟩= 0

    Since the feasible set is convex and both points are optimal, the objective is constant on the segment joining them. The second directional derivative off along this segment is ⟨d, Qd⟩, and hence ⟨d, Qd⟩= 0. BecauseQ⪰0, one hasQ 1/2d= 0and thereforeQd= 0, proving thatQx ⋆ 1 =Q...

  47. [55]

    Letd=x ⋆ 2 −x ⋆

    =Qx ⋆ 2 +c−A ∗y⋆ 1 =s(x ⋆ 1, y⋆ 1)∈K ∗. Letd=x ⋆ 2 −x ⋆

  48. [56]

    Feasibility givesAd= 0, while equality of the two objective values andQd= 0give 0 =f(x ⋆ 2)−f(x ⋆

  49. [57]

    Together with complementarity at x⋆ 1, this proves complementarity at x⋆

    =⟨Qx ⋆ 1 +c, d⟩=⟨s(x ⋆ 1, y⋆ 1), d⟩. Together with complementarity at x⋆ 1, this proves complementarity at x⋆

  50. [58]

    ms −2ξ −2ξ m t #

    is also a KKT pair. Cross- pairing follows, and the distance identity follows from the Euclidean product norm. The same invariance makes DQ independent of x⋆. Every optimal slack belongs to the intersection in (26). Conversely, if s=Qx ⋆ +c−A ∗y belongs to this intersection, t...

Pith tools

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