On complexity and convergence of high-order coordinate descent algorithms for smooth nonconvex box-constrained minimization

Abstract

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 $\epsilon$-stationarity with respect to the variables of each coordinate-descent block is $O({\epsilon }^{-(p+1)/p})$ whereas the computer work for getting first-order $\epsilon$-stationarity with respect to all the variables simultaneously is $O({\epsilon }^{-(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.

References in corpus (4)

• Coordinate descent algorithms for nonconvex penalized regression, with applications to biological feature selection
• Complexity and performance of an Augmented Lagrangian algorithm
• Tensor Methods for Minimizing Convex Functions with Hölder Continuous Higher-Order Derivatives
• A Control-Theoretic Perspective on Optimal High-Order Optimization

Cited by in corpus (1)

• Worst case complexity bounds for linesearch-type derivative-free algorithms