The medical image registration problem can be formulated as a nonlinear programming problem. To identify appropriate algorithms to solve it, it is critical to analyze the properties of the problem. In this paper, we consider the image registration problem based on maximization of mutual information when the partial volume (PV) interpolation is used to update the joint histogram. We identify pathological cases which may happen in practice, and which may lead to discontinuous instances of the objective function. We show that the objective function is not differentiable and that the set of non- differentiability is of null measure. Then, we propose a derivative- free algorithm specially designed for this application. Derivative- free optimization involves all the methods used to minimize an objective function when its derivatives are not available and when the function is expensive. We present here, a trust-region algorithm based on radial basis functions instead of the classical second-order polynomials. Actually, our surrogate of the objective function is a mixed radial and polynomial model. On the instances of the medical image registration problem, our method surpasses all the tested state-of-the-art derivative-free algorithms.