Abstract: Graph matching is an NP-hard problem. In this paper, we relax the admissible set of permutation matrices based on a well known result that permutation matrix is a non-negative orthogonal matrix. Meantime, a barrier function is incorporated into the objective function. In theory, the solution of the proposed model is the same as the original model, which distinguishes from the traditional relaxation matching models. The proposed model is a binary optimization problem which is a linear optimization problem on orthogonal variable and a quadratic convex optimization problem on non-negative variable. So, a new matching algorithm, named alternate iteration algorithm, is designed to solve it. It is proved that the proposed algorithm is locally convergent. The numerical experiments show that the proposed algorithm is more accurate than linear programming algorithm and eigen-decomposition algorithm.