  In this paper we propose the Graduated NonConvexity and Graduated Concavity
Procedure (GNCGCP) as a general optimization framework to approximately solve
the combinatorial optimization problems on the set of partial permutation
matrices. GNCGCP comprises two sub-procedures, graduated nonconvexity (GNC)
which realizes a convex relaxation and graduated concavity (GC) which realizes
a concave relaxation. It is proved that GNCGCP realizes exactly a type of
convex-concave relaxation procedure (CCRP), but with a much simpler formulation
without needing convex or concave relaxation in an explicit way. Actually,
GNCGCP involves only the gradient of the objective function and is therefore
very easy to use in practical applications. Two typical NP-hard problems,
(sub)graph matching and quadratic assignment problem (QAP), are employed to
demonstrate its simplicity and state-of-the-art performance.
