A Feasible Method for Solving an SDP Relaxation of the Quadratic Knapsack Problem

References

• [1] Absil PA, Malick J (2012) Projection-like retractions on matrix manifolds. SIAM J. Optim. 22(1):135–158.Crossref, Google Scholar
• [2] Barvinok AI (1995) Problems of distance geometry and convex properties of quadratic maps. Discrete Comput. Geometry 13(2):189–202.Crossref, Google Scholar
• [3] Barzilai J, Borwein JM (1988) Two-point step size gradient methods. IMA J. Numerical Anal. 8(1):141–148.Crossref, Google Scholar
• [4] Bhojanapalli S, Boumal N, Jain P, Netrapalli P (2018) Smoothed analysis for low-rank solutions to semidefinite programs in quadratic penalty form. Conf. Learn. Theory (PMLR, Stockholm), 3243–3270.Google Scholar
• [5] 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
• [6] Bonnans JF, Shapiro A (2013) Perturbation Analysis of Optimization Problems (Springer Science & Business Media, New York).Google Scholar
• [7] Boumal N (2020) An introduction to optimization on smooth manifolds.Google Scholar
• [8] Boumal N, Voroninski V, Bandeira A (2016) The non-convex Burer-Monteiro approach works on smooth semidefinite programs. Proc. 30th Internat. Conf. Neural Inform. Processing Systems (NIPS, Barcelona), 2765–2773.Google Scholar
• [9] Boumal N, Voroninski V, Bandeira AS (2020) Deterministic guarantees for Burer-Monteiro factorizations of smooth semidefinite programs. Comm. Pure Appl. Math. 73(3):581–608.Crossref, Google Scholar
• [10] Boumal N, Mishra B, Absil PA, Sepulchre R (2014) Manopt, a Matlab toolbox for optimization on manifolds. J. Machine Learn. Res. 15(1):1455–1459.Google Scholar
• [11] Burer S, Monteiro RD (2001) A projected gradient algorithm for solving the maxcut sdp relaxation. Optim. Methods Software 15(3–4):175–200.Crossref, Google Scholar
• [12] 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
• [13] Burer S, Monteiro RD (2005) Local minima and convergence in low-rank semidefinite programming. Math. Programming 103(3):427–444.Crossref, Google Scholar
• [14] Caprara A, Pisinger D, Toth P (1999) Exact solution of the quadratic knapsack problem. INFORMS J. Comput. 11(2):125–137.Link, Google Scholar
• [15] Fallat SM, Hogben L (2007) The minimum rank of symmetric matrices described by a graph: A survey. Linear Algebra Appl. 426(2–3):558–582.Crossref, Google Scholar
• [16] Ferreira CE, Martin A, de Souza CC, Weismantel R, Wolsey LA (1996) Formulations and valid inequalities for the node capacitated graph partitioning problem. Math. Programming 74(3):247–266.Crossref, Google Scholar
• [17] Fomeni FD, Letchford AN (2014) A dynamic programming heuristic for the quadratic knapsack problem. INFORMS J. Comput. 26(1):173–182.Link, Google Scholar
• [18] Friedland S, Loewy R (1976) Subspaces of symmetric matrices containing matrices with a multiple first eigenvalue. Pacific J. Math. 62(2):389–399.Crossref, Google Scholar
• [19] Gallo G, Hammer PL, Simeone B (1980) Quadratic knapsack problems. Combinatorial Optimization (Springer, Berlin, Heidelberg), 132–149.Crossref, Google Scholar
• [20] Gao B, Absil PA (2022) A Riemannian rank-adaptive method for low-rank matrix completion. Comput. Optim. Appl. 81(1):67–90.Crossref, Google Scholar
• [21] Goemans MX, Williamson DP (1995) Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. J. ACM 42(6):1115–1145.Crossref, Google Scholar
• [22] Helmberg C, Rendl F, Weismantel R (2000) A semidefinite programming approach to the quadratic knapsack problem. J. Combin. Optim. 4(2):197–215.Crossref, Google Scholar
• [23] Hogben L (2010) Minimum rank problems. Linear Algebra Appl. 432(8):1961–1974.Crossref, Google Scholar
• [24] Hogben L, Van Der Holst H (2007) Forbidden minors for the class of graphs g with ξ (g) ≤ 2. Linear Algebra Appl. 423(1):42–52.Crossref, Google Scholar
• [25] Iannazzo B, Porcelli M (2018) The Riemannian Barzilai–Borwein method with nonmonotone line search and the matrix geometric mean computation. IMA J. Numerical Anal. 38(1):495–517.Crossref, Google Scholar
• [26] Johnson EL, Mehrotra A, Nemhauser GL (1993) Min-cut clustering. Math. Programming 62(1):133–151.Crossref, Google Scholar
• [27] Knyazev AV (2001) Toward the optimal preconditioned eigensolver: Locally optimal block preconditioned conjugate gradient method. SIAM J. Sci. Comput. 23(2):517–541.Crossref, Google Scholar
• [28] Mosek ApS (2019) The MOSEK optimization toolbox for MATLAB manual, version 9.0. Accessed January 10, 2022, http://docs.mosek.com/9.0/toolbox/index.html.Google Scholar
• [29] Nocedal J, Wright S (1999) Numerical Optimization (Springer Science, New York).Crossref, Google Scholar
• [30] Pataki G (1998) On the rank of extreme matrices in semidefinite programs and the multiplicity of optimal eigenvalues. Math. Oper. Res. 23(2):339–358.Link, Google Scholar
• [31] Petersen KB, Pedersen MS (2008) The matrix cookbook. Technical manual, Technical University of Denmark, Lyngby.Google Scholar
• [32] Pisinger D (2005) Where are the hard knapsack problems? Comput. Oper. Res. 32(9):2271–2284.Crossref, Google Scholar
• [33] Pisinger D (2007) The quadratic knapsack problem—A survey. Discrete Appl. Math. 155(5):623–648.Crossref, Google Scholar
• [34] Raydan M (1997) The Barzilai and Borwein gradient method for the large scale unconstrained minimization problem. SIAM J. Optim. 7(1):26–33.Crossref, Google Scholar
• [35] Tang T, Toh KC (2021) Solving graph equipartition SDPs on an algebraic variety. Preprint, submitted December 8, https://arxiv.org/abs/2112.04256.Google Scholar
• [36] 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
• [37] Tütüncü RH, Toh KC, Todd MJ (2003) Solving semidefinite-quadratic-linear programs using sdpt3. Math. Programming 95(2):189–217.Crossref, Google Scholar
• [38] Wang H, Kochenberger G, Glover F (2012) A computational study on the quadratic knapsack problem with multiple constraints. Comput. Oper. Res. 39(1):3–11.Crossref, Google Scholar
• [39] Wen Z, Yin W (2013) A feasible method for optimization with orthogonality constraints. Math. Programming 142(1):397–434.Crossref, Google Scholar
• [40] 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
• [41] 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
• [42] Zhang R (2020) Newton retraction as approximate geodesics on submanifolds. Preprint, submitted June 26, https://arxiv.org/abs/2006.14751.Google Scholar
• [43] 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