Fuzzy$k$-Means with Entropy Regularization method (ERFKM) is an extension to Fuzzy$k$-Means (FKM) by introducing a maximum entropy term to FKM, whose purpose is trading off fuzziness and compactness. However, ERFKM often converges to a poor local minimum, which affects its performance. In this paper, we propose an effective optimization method to solve this problem, called IRW-ERFKM. First a new equivalent problem for ERFKM is proposed; then we solve it through Iteratively Re-Weighted (IRW) method. Since IRW-ERFKM optimizes the problem with$k\times 1$instead of$d\times k$intermediate variables, the space complexity of IRW-ERFKM is greatly reduced. Extensive experiments on clustering performance and objective function value show IRW-ERFKM can get a better local minimum than ERFKM with fewer iterations. Through time complexity analysis, it verifies IRW-ERFKM and ERFKM have the same linear time complexity. Moreover, IRW-ERFKM has advantages on evaluation metrics compared with other methods. What's more, there are two interesting findings. One is when we use IRW method to solve the equivalent problem of ERFKM with one factor$\mathbf{U}$, it is equivalent to ERFKM. The other is when the inner loop of IRW-ERFKM is executed only once, IRW-ERFKM and ERFKM are equivalent in this case.