  In this paper, we show that the quadratic assignment problem (QAP) can be
reformulated to an equivalent rank constrained doubly nonnegative (DNN)
problem. Under the framework of the difference of convex functions (DC)
approach, a semi-proximal DC algorithm (DCA) is proposed for solving the
relaxation of the rank constrained DNN problem whose subproblems can be solved
by the semi-proximal augmented Lagrangian method (sPALM). We show that the
generated sequence converges to a stationary point of the corresponding DC
problem, which is feasible to the rank constrained DNN problem. Moreover,
numerical experiments demonstrate that for most QAP instances, the proposed
approach can find the global optimal solutions efficiently, and for others, the
proposed algorithm is able to provide good feasible solutions in a reasonable
time.
