The thermodynamic definition of temperature is simply:
$$T=\left(\frac{\partial{U}}{\partial{S}} \right)_{V,\ n}$$
As you see there is no absolute value involved. This implies that the partial derivative can therefore be negative, and so the system would lose internal energy as it is increasing its entropy. Is this a purely theoretical exercise, or are there systems that behave this way?