A Low-Rank Augmented Lagrangian Method for Doubly Nonnegative Relaxations of Mixed-Binary Quadratic Programs

References

• Absil PA, Mahony R, Sepulchre R (2009) Optimization Algorithms on Matrix Manifolds (Princeton University Press, Princeton, NJ).Google Scholar
• Beasley JE (1998) Heuristic algorithms for the unconstrained binary quadratic programming problem. Working paper, The Management School, Imperial College London, London.Google Scholar
• Beck A, Sabach S (2015) Weiszfeld’s method: Old and new results. J. Optim. Theory Appl. 164(1):1–40.Crossref, Google Scholar
• Benson SJ, Ye Y (2008) Algorithm 875: DSDP5—Software for semidefinite programming. ACM Trans. Math. Software 34(3):1–20.Crossref, Google Scholar
• Billionnet A, Soutif É (2004) An exact method based on Lagrangian decomposition for the 0–1 quadratic knapsack problem. Eur. J. Oper. Res. 157(3):565–575.Crossref, Google Scholar
• Bomze IM, De Klerk E (2002) Solving standard quadratic optimization problems via linear, semidefinite and copositive programming. J. Global Optim. 24(2):163–185.Crossref, Google Scholar
• Bomze IM, Cheng J, Dickinson PJ, Lisser A (2017) A fresh CP look at mixed-binary QPs: New formulations and relaxations. Math. Programming 166(3):159–184.Crossref, Google Scholar
• Bomze IM, Cheng J, Dickinson PJ, Lisser A, Liu J (2019) Notoriously hard (mixed-)binary QPs: Empirical evidence on new completely positive approaches. Comput. Management Sci. 16(4):593–619.Crossref, Google Scholar
• Bonnans JF, Shapiro A (2013) Perturbation Analysis of Optimization Problems (Springer Science & Business Media, New York).Google Scholar
• Borwein J, Wolkowicz H (1981a) Regularizing the abstract convex program. J. Math. Anal. Appl. 83(2):495–530.Crossref, Google Scholar
• Borwein JM, Wolkowicz H (1981b) Facial reduction for a cone-convex programming problem. J. Australian Math. Soc. 30(3):369–380.Crossref, Google Scholar
• Boumal N (2023) An Introduction to Optimization on Smooth Manifolds (Cambridge University Press, Cambridge, UK).Crossref, Google Scholar
• Bronstein AM, Bronstein MM, Kimmel R (2008) Numerical Geometry of Non-Rigid Shapes (Springer Science & Business Media, New York).Google Scholar
• Bundfuss S, Dür M (2009) An adaptive linear approximation algorithm for copositive programs. SIAM J. Optim. 20(1):30–53.Crossref, Google Scholar
• Burer S (2009) On the copositive representation of binary and continuous nonconvex quadratic programs. Math. Programming 120(2):479–495.Crossref, Google Scholar
• Burer S (2010) Optimizing a polyhedral-semidefinite relaxation of completely positive programs. Math. Programming Comput. 2(1):1–19.Crossref, Google Scholar
• Burer S, Monteiro RD (2003) A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization. Math. Programming 95(2):329–357.Crossref, Google Scholar
• Burer S, Monteiro RD (2005) Local minima and convergence in low-rank semidefinite programming. Math. Programming 103(3):427–444.Crossref, Google Scholar
• Burkard RE, Karisch SE, Rendl F (1997) QAPLIB–A quadratic assignment problem library. J. Global Optim. 10(4):391–403.Crossref, Google Scholar
• Caprara A, Pisinger D, Toth P (1999) Exact solution of the quadratic knapsack problem. INFORMS J. Comput. 11(2):125–137.Link, Google Scholar
• Chen J, Nguyen BT, Soh YS (2023) Semidefinite relaxations of the Gromov-Wasserstein distance. Preprint, submitted December 22, https://arxiv.org/abs/2312.14572.Google Scholar
• Chen L, Sun D, Toh KC (2017) An efficient inexact symmetric Gauss–Seidel based majorized ADMM for high-dimensional convex composite conic programming. Math. Programming 161(1):237–270.Crossref, Google Scholar
• Cui Y, Sun D, Toh KC (2019) On the R-superlinear convergence of the KKT residuals generated by the augmented Lagrangian method for convex composite conic programming. Math. Programming 178(1):381–415.Crossref, Google Scholar
• Dickinson PJ, Gijben L (2014) On the computational complexity of membership problems for the completely positive cone and its dual. Comput. Optim. Appl. 57(2):403–415.Crossref, Google Scholar
• Drusvyatskiy D, Wolkowicz H (2017) The many faces of degeneracy in conic optimization. Foundations Trends Optim. 3(2):77–170.Crossref, Google Scholar
• Gallo G, Hammer PL, Simeone B (1980) Quadratic knapsack problems. Math. Programming 12:132–149.Crossref, Google Scholar
• Gao B, Son NT, Absil PA, Stykel T (2021) Riemannian optimization on the symplectic Stiefel manifold. SIAM J. Optim. 31(2):1546–1575.Crossref, Google Scholar
• Han Q, Li C, Lin Z, Chen C, Deng Q, Ge D, Liu H, Ye Y (2024) A low-rank ADMM splitting approach for semidefinite programming. Preprint, submitted March 14, https://arxiv.org/abs/2403.09133.Google Scholar
• Hestenes MR (1969) Multiplier and gradient methods. J. Optim. Theory Appl. 4(5):303–320.Crossref, Google Scholar
• Iannazzo B, Porcelli M (2018) The Riemannian Barzilai–Borwein method with nonmonotone line search and the matrix geometric mean computation. IMA J. Numer. Anal. 38(1):495–517.Crossref, Google Scholar
• Ito N, Kim S, Kojima M, Takeda A, Toh KC (2019) Algorithm 996: BBCPOP: A sparse doubly nonnegative relaxation of polynomial optimization problems with binary, box, and complementarity constraints. ACM Trans. Math. Software 45(3):1–26.Crossref, Google Scholar
• Journée M, Bach F, Absil PA, Sepulchre R (2010) Low-rank optimization on the cone of positive semidefinite matrices. SIAM J. Optim. 20(5):2327–2351.Crossref, Google Scholar
• Kim S, Kojima M, Toh KC (2016) A Lagrangian–DNN relaxation: A fast method for computing tight lower bounds for a class of quadratic optimization problems. Math. Programming 156(1):161–187.Crossref, Google Scholar
• Liu C, Boumal N (2020) Simple algorithms for optimization on Riemannian manifolds with constraints. Appl. Math. Optim. 82(3):949–981.Crossref, Google Scholar
• Monteiro RD, Sujanani A, Cifuentes D (2024) A low-rank augmented Lagrangian method for large-scale semidefinite programming based on a hybrid convex-nonconvex approach. Preprint, submitted January 23, https://arxiv.org/abs/2401.12490.Google Scholar
• Moreau JJ (1962) Décomposition orthogonale d’un espace hilbertien selon deux cônes mutuellement polaires. Comptes Rendus Hebdomadaires Séances Acad. Sci. 255:238–240.Google Scholar
• Ostresh LM Jr (1978) On the convergence of a class of iterative methods for solving the Weber location problem. Oper. Res. 26(4):597–609.Link, Google Scholar
• Pataki G (2013) Strong duality in conic linear programming: Facial reduction and extended duals. Bailey DH, Bauschke HH, Borwein P, Garvan F, Théra M, Vanderwerff JD, Wolkowicz H, eds. Computational and Analytical Mathematics: In Honor of Jonathan Borwein’s 60th Birthday (Springer, New York), 613–634.Crossref, Google Scholar
• Permenter F, Parrilo P (2018) Partial facial reduction: Simplified, equivalent SDPs via approximations of the PSD cone. Math. Programming 171(1):1–54.Crossref, Google Scholar
• Pisinger D (2007) The quadratic knapsack problem—A survey. Discrete Appl. Math. 155(5):623–648.Crossref, Google Scholar
• Powell MJ (1969) A method for nonlinear constraints in minimization problems. Fletcher R, ed. Optimization (Academic Press, New York), 283–298.Google Scholar
• Ramana MV (1997) An exact duality theory for semidefinite programming and its complexity implications. Math. Programming 77(1):129–162.Crossref, Google Scholar
• Rockafellar RT (1976) Augmented Lagrangians and applications of the proximal point algorithm in convex programming. Math. Oper. Res. 1(2):97–116.Link, Google Scholar
• Sturm JF (1999) Using SeDuMi 1.02, a toolbox for optimization over symmetric cones. Optim. Methods Software 11(1–4):625–653.Crossref, Google Scholar
• Sun D, Toh KC, Yuan Y, Zhao XY (2020) SDPNAL+: A Matlab software for semidefinite programming with bound constraints (version 1.0). Optim. Methods Software 35(1):87–115.Crossref, Google Scholar
• Tanaka M, Nakata K, Waki H (2012) Application of a facial reduction algorithm and an inexact primal-dual path-following method for doubly nonnegative relaxation for mixed binary nonconvex quadratic optimization problems. Pacific J. Optim. 8(4):699–724.Google Scholar
• Tang T, Toh KC (2024a) A feasible method for general convex low-rank SDP problems. SIAM J. Optim. 34(3):2169–2200.Crossref, Google Scholar
• Tang T, Toh KC (2024b) A feasible method for solving an SDP relaxation of the quadratic knapsack problem. Math. Oper. Res. 49(1):19–39.Link, Google Scholar
• Tang T, Toh KC (2024c) Solving graph equipartition SDPs on an algebraic variety. Math. Programming 204(1):299–347.Crossref, Google Scholar
• Toh KC, Todd MJ, Tütüncü RH (1999) SDPT3—A Matlab software package for semidefinite programming, version 1.3. Optim. Methods Software 11(1–4):545–581.Crossref, Google Scholar
• Vardi Y, Zhang CH (2001) A modified Weiszfeld algorithm for the Fermat-Weber location problem. Math. Programming 90(3):559–566.Crossref, Google Scholar
• Wang J, Hu L (2023) Solving low-rank semidefinite programs via manifold optimization. Preprint, submitted March 3, https://arxiv.org/abs/2303.01722.Google Scholar
• Wang Y, Deng K, Liu H, Wen Z (2023) A decomposition augmented Lagrangian method for low-rank semidefinite programming. SIAM J. Optim. 33(3):1361–1390.Crossref, Google Scholar
• Weiszfeld E (1937) Sur le point pour lequel la somme des distances de n points donnés est minimum. Tohoku Math. J. 43:355–386.Google Scholar
• Weiszfeld E, Plastria F (2009) On the point for which the sum of the distances to n given points is minimum. Ann. Oper. Res. 167(1):7–41.Crossref, Google Scholar
• Wen Z, Yin W (2013) A feasible method for optimization with orthogonality constraints. Math. Programming 142(1):397–434.Crossref, Google Scholar
• Xiao N, Liu X, Toh KC (2024) Dissolving constraints for Riemannian optimization. Math. Oper. Res. 49(1):366–397.Link, Google Scholar
• Yang L, Sun D, Toh KC (2015) SDPNAL+: A majorized semismooth Newton-CG augmented Lagrangian method for semidefinite programming with nonnegative constraints. Math. Programming Comput. 7(3):331–366.Crossref, Google Scholar
• Yoshise A, Matsukawa Y (2010) On optimization over the doubly nonnegative cone. 2010 IEEE Internat. Symp. Comput. Aided Control System Design (IEEE, New York), 13–18.Google Scholar
• Yurtsever A, Tropp JA, Fercoq O, Udell M, Cevher V (2021) Scalable semidefinite programming. SIAM J. Math. Data Sci. 3(1):171–200.Crossref, Google Scholar
• Zhao XY, Sun D, Toh KC (2010) A Newton-CG augmented Lagrangian method for semidefinite programming. SIAM J. Optim. 20(4):1737–1765.Crossref, Google Scholar
• Zhou Y, Bao C, Ding C, Zhu J (2023) A semismooth Newton based augmented Lagrangian method for nonsmooth optimization on matrix manifolds. Math. Programming 201(1):1–61.Crossref, Google Scholar
• Zhu Y, Pataki G, Tran-Dinh Q (2019) Sieve-SDP: A simple facial reduction algorithm to preprocess semidefinite programs. Math. Programming Comput. 11(3):503–586.Crossref, Google Scholar