In this paper, we study how to compute all real solutions of the tensor complimentary problem, if there are finite many ones. We formulate the problem as a sequence of polynomial optimization problems. The solutions can be computed sequentially. Each of them can be obtained by solving Lasserre’s hierarchy of semidefinite relaxations. A semidefinite algorithm is proposed and its convergence properties are discussed. Some numerical experiments are also presented.