论文标题
关于光滑非凸盒最小化的高阶坐标下降算法的复杂性和收敛性
On complexity and convergence of high-order coordinate descent algorithms for smooth nonconvex box-constrained minimization
论文作者
论文摘要
坐标下降方法对全球优化具有相当大的影响，因为全球（或至少几乎全球）最小化对于低维问题是可负担的。在这项工作中引入了具有高阶正规化模型的坐标下降方法，用于平滑的非凸盒受限的最小化。建立了高阶平稳性渐变性收敛和一阶平稳性最差评估复杂性界限。对于每个坐标块的变量，获得一阶$ \ VAREPSILON $ -STATIONITY所必需的计算机工作是$ O（\ varepsilon^{ - （p+1）/p}）$ $ O（\ Varepsilon^{ - （P+1）}）$。提出了涉及多维缩放问题的数值示例。通过选择初始点的坐标策略，可以增强该方法的数值性能。
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.
