In this letter, received signal strength (RSS)- based target localization with uncertainty in transmit power (UTP) is studied. First, the localization-based alternating nonnegative constrained least squares (ANCLS) framework is conducted. A two-phase optimization method, i.e., a matrix factorization-based min-max strategy (MFMM), is then presented to figure out the solution. The first phase of optimization is based on a matrix factorization approach, i.e., active set method (ASM). However, ASM may drop to a local minimum. Therefore, a min-max strategy based on a Taylor linearization approximation is involved in the second phase, where the objective is split into a convex quadratic and a concave term. The target position and UTP are refined simultaneously in the iteration via solving a sequence of convex problems, in which the solution obtained by ASM is to be the initiation. Additionally, to evaluate the effectiveness of MFMM, both the computational complexity and the Cramer-Rao lower bound (CRLB) are analyzed. Simulations are carried out to illustrate the outperformance, compared with other state-of-the-art methods in different scenarios.