  The freeze-out of dark matter (DM) depends on the evolution of the DM
temperature. The DM temperature does not have to follow the standard model one,
when the elastic scattering is not sufficient to maintain the kinetic
equilibrium. We study the temperature evolution of the semi-annihilating DM,
where a pair of the DM particles annihilate into one DM particle and another
particle coupled to the standard model sector. We find that the kinetic
equilibrium is maintained solely via semi-annihilation until the last stage of
the freeze-out. After the freeze-out, semi-annihilation converts the mass
deficit to the kinetic energy of DM, which leads to non-trivial evolution of
the DM temperature. We argue that the DM temperature redshifts like radiation
as long as the DM self-interaction is efficient. We dub this novel temperature
evolution as self-heating. Notably, the structure formation is suppressed at
subgalactic scales like keV-scale warm DM but with GeV-scale self-heating DM if
the self-heating lasts roughly until the matter-radiation equality. The long
duration of the self-heating requires the large self-scattering cross section,
which in turn flattens the DM density profile in inner halos. Consequently,
self-heating DM can be a unified solution to apparent failures of cold DM to
reproduce the observed subgalactic scale structure of the Universe.
