Domain adaptation is important for practical applications of supervised learning, as the distribution of inputs can differ significantly between available sources of training data and the test data in a particular target domain. Many domain adaptation methods have been proposed, yet very few of them deal with the case of more than one training domain; methods that do incorporate multiple domains assume that the separation into domains is known a priori, which is not always the case in practice. In this paper, we introduce a method for multi-domain adaptation with unknown domain labels, based on learning nonlinear crossdomain transforms, and apply it to image classification. Our key contribution is a novel version of constrained clustering; unlike many existing constrained clustering algorithms, ours can be shown to provably converge locally while satisfying all constraints. We present experiments on a commonly available image dataset.