  In this paper, we consider an SDP relaxation of the quadratic knapsack
problem (QKP). After using the Burer-Monteiro factorization, we get a
non-convex optimization problem, whose feasible region is an algebraic variety.
Although there might be non-regular points on the algebraic variety, we prove
that the algebraic variety is a smooth manifold except for a trivial point for
a generic input data. We also analyze the local geometric properties of
non-regular points on this algebraic variety. In order to maintain the
equivalence between the SDP problem and its non-convex formulation, we derive a
new rank condition under which these two problems are equivalent. This new rank
condition can be much weaker than the classical rank condition if the
coefficient matrix has certain special structures. We also prove that under an
appropriate rank condition, any second order stationary point of the non-convex
problem is also a global optimal solution without any regularity assumption.
This result is distinguished from previous results based on LICQ-like
smoothness assumption. With all these theoretical properties, we design an
algorithm that equip a manifold optimization method with a strategy to escape
from non-optimal non-regular points. Our algorithm can also be used as a
heuristic for solving the quadratic knapsack problem. Numerical experiments are
conducted to verify the high efficiency and robustness of our algorithm as
compared to other SDP solvers and a heuristic method based on dynamic
programming. In particular, our algorithm is able to solve the SDP relaxation
of a one-million dimensional QKP with a sparse cost matrix very accurately in
about 20 minutes on a modest desktop computer.
