  Coordinate descent methods have considerable impact in global optimization
because global (or, at least, almost global) minimization is affordable for
low-dimensional problems. Coordinate descent methods with high-order
regularized models for smooth nonconvex box-constrained minimization are
introduced in this work. High-order stationarity asymptotic convergence and
first-order stationarity worst-case evaluation complexity bounds are
established. The computer work that is necessary for obtaining first-order
$\varepsilon$-stationarity with respect to the variables of each
coordinate-descent block is $O(\varepsilon^{-(p+1)/p})$ whereas the computer
work for getting first-order $\varepsilon$-stationarity with respect to all the
variables simultaneously is $O(\varepsilon^{-(p+1)})$. Numerical examples
involving multidimensional scaling problems are presented. The numerical
performance of the methods is enhanced by means of coordinate-descent
strategies for choosing initial points.
