Change detection (CD), enabled by multitemporal multispectral satellite imagery, has many important Earth observation missions such as land cover/use monitoring, for which we observe that change regions are relatively smaller than those caused by disaster (e.g., forest fire) with patterns typically composed of a number of smooth regions. These observations are considered in our new CD criterion, which can effectively mitigate the artifacts and speckle noise suffered by existing statistic-based and difference image (DI) analysis based methods. The proposed CD criterion amounts to a large-scale non-convex optimization, which is first reformulated using the convex relaxation trick with associated change map interpreted in the probability sense, followed by adopting an efficient convex solver known as alternating direction method of multipliers (ADMM). The resulted probabilistic change map would be more practical, and can be thresholded at 0.5 to yield the conventional binary-valued one. We also reveal a link between the proposed criterion and the DI-based criterion, and demonstrate the outstanding performance of our fully unsupervised CD algorithm qualitatively and quantitatively.