Sharp worst-case evaluation complexity bounds for arbitrary-order nonconvex optimization with inexpensive constraints
Sharp worst-case evaluation complexity bounds for arbitrary-order nonconvex optimization with inexpensive constraints
复制标题
DOI：
10.1137/17m1144854
复制
发表时间：
2018-11
期刊：
影响因子：
--
通讯作者：
C. Cartis;N. Gould;P. Toint
中科院分区：
文献类型：
--
作者：
C. Cartis;N. Gould;P. Toint
我们为具有一般廉价约束的非凸最小化问题提供了尖锐的最坏情况评估复杂性界限，即评估/执行（可能是非凸的或什至断开的）约束（如果有）的成本与评估目标函数的成本相比可以忽略不计的问题。这些界限统一、扩展或改进了无约束和凸约束问题的所有已知复杂度上限和下限。结果表明，给定准确度 $\epsilon$、最高可用 Lipschitz 连续导数 $p$ 的程度以及介于 1 和 $p$ 之间的所需最优阶 $q$，概念正则化算法只需对目标函数及其导数进行 $O(\epsilon^{-\frac{p+1}{p-q+1}})$ 评估即可计算出适当近似的 $q$ 阶最小化器。通过适当选择正则化，如果 $p$-th 导数只是 H\"older 而不是 Lipschitz 连续，则类似的结果也成立。我们提供了一个例子，表明上述复杂性界限对于无约束和一大类约束问题来说是尖锐的，我们还从最坏情况复杂性的角度给出了在使用相同导数信息的一大类算法中正则化方法的最优性的原因。
We provide sharp worst-case evaluation complexity bounds for nonconvex minimization problems with general inexpensive constraints, i.e.\ problems where the cost of evaluating/enforcing of the (possibly nonconvex or even disconnected) constraints, if any, is negligible compared to that of evaluating the objective function. These bounds unify, extend or improve all known upper and lower complexity bounds for unconstrained and convexly-constrained problems. It is shown that, given an accuracy level $\epsilon$, a degree of highest available Lipschitz continuous derivatives $p$ and a desired optimality order $q$ between one and $p$, a conceptual regularization algorithm requires no more than $O(\epsilon^{-\frac{p+1}{p-q+1}})$ evaluations of the objective function and its derivatives to compute a suitably approximate $q$-th order minimizer. With an appropriate choice of the regularization, a similar result also holds if the $p$-th derivative is merely H\"older rather than Lipschitz continuous. We provide an example that shows that the above complexity bound is sharp for unconstrained and a wide class of constrained problems, we also give reasons for the optimality of regularization methods from a worst-case complexity point of view, within a large class of algorithms that use the same derivative information.