In this paper, we propose new design methods for linear phase FIR filters with signed power-of-two (SP2) coefficients based on a semi-definite programming (SDP) relaxation method. The proposed methods include a linear programming (LP) relaxation and a relaxation by adding triangle inequalities. Although such the design problems are known as one of the NP-hard problems, these methods can solve the design problems in a low computational cost in comparison with a traditional SDP relaxation method. It is shown by several numerical experiments that those method are superior to the simple SDP relaxation method.