A concise second-order complexity analysis for unconstrained optimization using high-order regularized models
A concise second-order complexity analysis for unconstrained optimization using high-order regularized models
复制标题
DOI：
10.1080/10556788.2019.1678033
复制
发表时间：
2019-10
影响因子：
2.2
通讯作者：
C. Cartis;N. Gould;P. Toint
中科院分区：
文献类型：
--
作者：
C. Cartis;N. Gould;P. Toint
摘要 提出了一种自适应正则化算法，该算法使用无约束目标函数的 p 阶目标的泰勒模型，并且保证在大多数函数和导数评估中找到一阶和二阶临界点，其中 和 被规定一阶和二阶最优性容差。与 Cartis 等人中更通用的方法相比，这是一个简单的算法和相关分析。 [具有廉价约束的任意阶非凸优化的尖锐最坏情况评估复杂性界限，arXiv:1811.01220, 2018]解决了高于 2 的关键性的复杂性；在这里，我们使用标准最优性条件和实际子问题求解来显示二阶临界性的同阶尖锐复杂度界限。我们的方法还扩展了 Birgin 等人的方法。 [使用高阶正则化模型的无约束非线性优化的最坏情况评估复杂度，Math.程序。 A 163(1) (2017), pp. 359–368] 在与一阶复杂性所需的相同问题平滑度假设下寻找二阶临界点。
ABSTRACT An adaptive regularization algorithm is proposed that uses Taylor models of the objective of order p, , of the unconstrained objective function, and that is guaranteed to find a first- and second-order critical point in at most function and derivatives evaluations, where and are prescribed first- and second-order optimality tolerances. This is a simple algorithm and associated analysis compared to the much more general approach in Cartis et al. [Sharp worst-case evaluation complexity bounds for arbitrary-order nonconvex optimization with inexpensive constraints, arXiv:1811.01220, 2018] that addresses the complexity of criticality higher-than two; here, we use standard optimality conditions and practical subproblem solves to show a same-order sharp complexity bound for second-order criticality. Our approach also extends the method in Birgin et al. [Worst-case evaluation complexity for unconstrained nonlinear optimization using high-order regularized models, Math. Prog. A 163(1) (2017), pp. 359–368] to finding second-order critical points, under the same problem smoothness assumptions as were needed for first-order complexity.