A Restarted Primal-Dual Hybrid Conjugate Gradient Method for Large-Scale Quadratic Programming

References

• Applegate D, Hinder O, Lu H, Lubin M (2023) Faster first-order primal-dual methods for linear programming using restarts and sharpness. Math. Programming 201(1):133–184.Crossref, Google Scholar
• Applegate D, Díaz M, Hinder O, Lu H, Lubin M, O’Donoghue B, Schudy W (2021) Practical large-scale linear programming using primal-dual hybrid gradient. Adv. Neural Inform. Processing Systems, vol. 34 (PMLR, New York), 20243–20257.Google Scholar
• Boggs PT, Tolle JW (1995) Sequential quadratic programming. Acta Numerica 4:1–51.Crossref, Google Scholar
• Budish E, Cramton P, Kyle AS, Lee J, Malec D (2023) Flow trading. Technical report, National Bureau of Economic Research, Cambridge, MA.Google Scholar
• Chambolle A, Pock T (2011) A first-order primal-dual algorithm for convex problems with applications to imaging. J. Math. Imaging Vision 40:120–145.Crossref, Google Scholar
• Chambolle A, Pock T (2016) On the ergodic convergence rates of a first-order primal–dual algorithm. Math. Programming 159(1):253–287.Crossref, Google Scholar
• Chang CC, Lin CJ (2011) LIBSVM: A library for support vector machines. ACM Trans. Intelligent Systems Tech. 2(3):1–27.Crossref, Google Scholar
• Dai YH, Fletcher R (2005) Projected Barzilai-Borwein methods for large-scale box-constrained quadratic programming. Numerische Mathematik 100(1):21–47.Crossref, Google Scholar
• Davis TA, Hu Y (2011) The University of Florida sparse matrix collection. ACM Trans. Math. Software 38(1):1–25.Crossref, Google Scholar
• Deng Q, Feng Q, Gao W, Ge D, Jiang B, Jiang Y, Liu J, et al. (2022) New developments of ADMM-based interior point methods for linear programming and conic programming. Preprint, submitted September 5, https://arxiv.org/abs/2209.01793.Google Scholar
• di Serafino D, Hager WW, Toraldo G, Viola M (2024) On the stationarity for nonlinear optimization problems with polyhedral constraints. Math. Programming 205(1):107–134.Crossref, Google Scholar
• Dongarra JJ, Duff IS, Sorensen DC, Van der Vorst HA (1991) Solving Linear Systems on Vector and Shared Memory Computers (Society for Industrial and Applied Mathematics, Philadelphia).Google Scholar
• Fercoq O (2022) Quadratic error bound of the smoothed gap and the restarted averaged primal-dual hybrid gradient. Preprint, submitted June 7, https://arxiv.org/abs/2206.03041.Google Scholar
• Ferreau HJ, Kirches C, Potschka A, Bock HG, Diehl M (2014) qpOASES: A parametric active-set algorithm for quadratic programming. Math. Programming Comput. 6:327–363.Crossref, Google Scholar
• Furini F, Traversi E, Belotti P, Frangioni A, Gleixner A, Gould N, Liberti L, et al. (2019) QPLIB: A library of quadratic programming instances. Math. Programming Comput. 11:237–265.Crossref, Google Scholar
• Garcia CE, Prett DM, Morari M (1989) Model predictive control: Theory and practice—A survey. Automatica 25(3):335–348.Crossref, Google Scholar
• Ge D, Huangfu Q, Wang Z, Wu J, Ye Y (2022) Cardinal optimizer (COPT) user guide. Preprint, submitted August 30, https://arxiv.org/abs/2208.14314.Google Scholar
• Goldstein T, Li M, Yuan X (2015) Adaptive primal-dual splitting methods for statistical learning and image processing. Adv. Neural Inform. Processing Systems, vol. 28 (PMLR, New York).Google Scholar
• Goldstein T, Li M, Yuan X, Esser E, Baraniuk R (2013) Adaptive primal-dual hybrid gradient methods for saddle-point problems. Preprint, submitted May 2, https://arxiv.org/abs/1305.0546.Google Scholar
• Goulart PJ, Chen Y (2024) Clarabel: An interior-point solver for conic programs with quadratic objectives. Preprint, submitted May 21, https://arxiv.org/abs/2405.12762.Google Scholar
• Greenbaum A (1997) Iterative Methods for Solving Linear Systems (Society for Industrial and Applied Mathematics, Philadelphia).Crossref, Google Scholar
• Gurobi Optimization (2021) Gurobi optimizer reference manual.Google Scholar
• Hager WW, Zhang H (2016) An active set algorithm for nonlinear optimization with polyhedral constraints. Sci. China Math. 59:1525–1542.Crossref, Google Scholar
• Hager WW, Zhang H (2023) Algorithm 1035: A gradient-based implementation of the polyhedral active set algorithm. ACM Trans. Math. Software 49(2):1–13.Crossref, Google Scholar
• Hearst MA, Dumais ST, Osuna E, Platt J, Scholkopf B (1998) Support vector machines. IEEE Intelligent Systems Appl. 13(4):18–28.Crossref, Google Scholar
• Huang Y, Zhang W, Li H, Ge D, Liu H, Ye Y (2025) A restarted primal-dual hybrid conjugate gradient method for large-scale quadratic programming. https://doi.org/10.1287/ijoc.2024.0983.cd, https://github.com/INFORMSJoC/2024.0983.Google Scholar
• Lin T, Ma S, Ye Y, Zhang S (2021) An ADMM-based interior-point method for large-scale linear programming. Optim. Methods Software 36(2–3):389–424.Crossref, Google Scholar
• Lu H, Yang J (2023a) cuPDLP.jl: A GPU implementation of restarted primal-dual hybrid gradient for linear programming in Julia. Preprint, submitted November 20, https://arxiv.org/abs/2311.12180.Google Scholar
• Lu H, Yang J (2023b) A practical and optimal first-order method for large-scale convex quadratic programming. Preprint, submitted November 13, https://arxiv.org/abs/2311.07710.Google Scholar
• Lu H, Yang J, Hu H, Huangfu Q, Liu J, Liu T, Ye Y, Zhang C, Ge D (2023) cuPDLP-C: A strengthened implementation of cuPDLP for linear programming by c language. Preprint, submitted December 22, https://arxiv.org/abs/2312.14832.Google Scholar
• Markowitz H (1952) Portfolio selection. J. Finance 7(1):77–91.Google Scholar
• Maros I, Mészáros C (1999) A repository of convex quadratic programming problems. Optim. Methods Software 11(1–4):671–681.Crossref, Google Scholar
• Morari M, Lee JH (1999) Model predictive control: Past, present and future. Computers Chemical Engrg. 23(4–5):667–682.Crossref, Google Scholar
• Mosek ApS (2019) Mosek optimization toolbox for Matlab. User’s Guide and Reference Manual, Version 4(1).Google Scholar
• O’Donoghue B, Chu E, Parikh N, Boyd S (2016) Conic optimization via operator splitting and homogeneous self-dual embedding. J. Optim. Theory Appl. 169:1042–1068.Crossref, Google Scholar
• O’Donoghue B, Chu E, Parikh N, Boyd S (2023) SCS: Splitting conic solver, version 3.2.4. https://github.com/cvxgrp/scs.Google Scholar
• Pock T, Chambolle A (2011) Diagonal preconditioning for first order primal-dual algorithms in convex optimization. 2011 Internat. Conf. Comput. Vision (IEEE, Piscataway, NJ), 1762–1769.Google Scholar
• Ruiz D (2001) A scaling algorithm to equilibrate both rows and columns norms in matrices. ENSEEIHT-IRIT Technical Report RT/APO/01/4, Computational Science and Engineering Department, Atlas Centre, Rutherford Appleton Laboratory, Oxon, UK. Google Scholar
• Schubiger M, Banjac G, Lygeros J (2020) GPU acceleration of ADMM for large-scale quadratic programming. J. Parallel Distributed Comput. 144:55–67.Crossref, Google Scholar
• Stellato B, Banjac G, Goulart P, Bemporad A, Boyd S (2020) OSQP: An operator splitting solver for quadratic programs. Math. Programming Comput. 12(4):637–672.Crossref, Google Scholar
• Tharwat A (2016) Linear vs. quadratic discriminant analysis classifier: A tutorial. Internat. J. Appl. Pattern Recognition 3(2):145–180.Crossref, Google Scholar
• Vanderbei RJ (1999) LOQO: An interior point code for quadratic programming. Optim. Methods Software 11(1–4):451–484.Crossref, Google Scholar
• Wolfe P (1959) The simplex method for quadratic programming. Econometrica 27(3):382–398.Crossref, Google Scholar
• Zou H, Hastie T (2005) Regularization and variable selection via the elastic net. J. Roy. Statist. Soc. Ser. B Statist. Methodology 67(2):301–320.Crossref, Google Scholar