Graph matching is a NP-Hard problem. In this paper, we relax the admissible set of permutation matrices and meantime incorporate a barrier function into the objective function. The resulted model is equivalent to the original model. Alternate iteration algorithm is designed to solve it. It is proven that the algorithm proposed is locally convergent. Our experimental results reveal that the proposed algorithm outperforms the algorithm in .