We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
A Feasible Method for Solving an SDP Relaxation of the Quadratic Knapsack Problem.
- Authors
Tang, Tianyun; Toh, Kim-Chuan
- Abstract
In this paper, we consider a semidefinite programming (SDP) relaxation of the quadratic knapsack problem. After applying low-rank factorization, we get a nonconvex problem, whose feasible region is an algebraic variety with certain good geometric properties, which we analyze. We derive a rank condition under which these two formulations are equivalent. This rank condition is much weaker than the classical rank condition if the coefficient matrix has certain special structures. We also prove that, under an appropriate rank condition, the nonconvex problem has no spurious local minima without assuming linearly independent constraint qualification. We design a feasible method that can escape from nonoptimal nonregular points. Numerical experiments are conducted to verify the high efficiency and robustness of our algorithm as compared with other solvers. In particular, our algorithm is able to solve a one-million-dimensional sparse SDP problem accurately in about 20 minutes on a modest computer. Funding: The research of K.-C. Toh is supported by the Ministry of Education, Singapore, under its Academic Research Fund Tier 3 grant call [Grant MOE-2019-T3-1-010].
- Subjects
KNAPSACK problems; SEMIDEFINITE programming; ALGEBRAIC varieties; UNIVERSITY research; FACTORIZATION
- Publication
Mathematics of Operations Research, 2024, Vol 49, Issue 1, p19
- ISSN
0364-765X
- Publication type
Article
- DOI
10.1287/moor.2022.1345