论文标题
强大的评估复杂性范围，用于非convex非平滑复合函数的任意阶段优化
Strong Evaluation Complexity Bounds for Arbitrary-Order Optimization of Nonconvex Nonsmooth Composite Functions
论文作者
论文摘要
我们介绍了对于非凸优化问题的强高阶近似最小化器的概念。这些都适用于标准的平滑和复合非平滑设置，并允许凸或廉价的约束。然后提出一种自适应正则化算法，以找到这种近似的最小化器。在合适的Lipschitz连续性假设下，每当可行的集合是凸面时，都表明使用$ p $的模型，该算法最多可以在$ {\ cal o} \ left（\ max_ {1 \ leq j \ leq j \ leq j \ leq j \ leq j \ leq j \ leq j \ leq j \ leq j \ leq j \ leq j \ leq j \ leq j \ leq j \ leq j \ leq j \ leq j \ leq j \ leq q}ε_j^{ - （p+1）/（p-j+1）} \ right）$评估问题功能及其衍生物，其中$ε_j$是$ j $ th订单准确度；当$ q = 1 $或问题与$ q \ leq 2 $相结合时，此限制将适用。对于一般的非复合问题，即使可行的集合是非convex，界限也将变为$ {\ cal o} \ left（\ max_ {1 \ leq j \ leq q}ε_j^{ - q（p+1）/p}/p} \ right）$评估。如果问题是复合的，并且$ q> 1 $或可行的集合不是凸，则限制为$ {\ cal o} \ left（\ max_ {1 \ leq j \ leq j \ leq q}ε_j^{ - （q+1）}} \ right）$评估。据我们所知，这些结果不仅为（不受约束或廉价地约束）复合问题提供了超过一个的最佳订单的第一个已知界限，而且还为高阶强级$ q $ q $ q $ q $ q $ q $ q的最低限制的标准（不受约束和便宜的约束）的平稳问题提供了第一个急剧界限，从而对弱小的微型量互补的互补的结果进行了匹配。
We introduce the concept of strong high-order approximate minimizers for nonconvex optimization problems. These apply in both standard smooth and composite non-smooth settings, and additionally allow convex or inexpensive constraints. An adaptive regularization algorithm is then proposed to find such approximate minimizers. Under suitable Lipschitz continuity assumptions, whenever the feasible set is convex, it is shown that using a model of degree $p$, this algorithm will find a strong approximate q-th-order minimizer in at most ${\cal O}\left(\max_{1\leq j\leq q}ε_j^{-(p+1)/(p-j+1)}\right)$ evaluations of the problem's functions and their derivatives, where $ε_j$ is the $j$-th order accuracy tolerance; this bound applies when either $q=1$ or the problem is not composite with $q \leq 2$. For general non-composite problems, even when the feasible set is nonconvex, the bound becomes ${\cal O}\left(\max_{1\leq j\leq q}ε_j^{-q(p+1)/p}\right)$ evaluations. If the problem is composite, and either $q > 1$ or the feasible set is not convex, the bound is then ${\cal O}\left(\max_{1\leq j\leq q}ε_j^{-(q+1)}\right)$ evaluations. These results not only provide, to our knowledge, the first known bound for (unconstrained or inexpensively-constrained) composite problems for optimality orders exceeding one, but also give the first sharp bounds for high-order strong approximate $q$-th order minimizers of standard (unconstrained and inexpensively constrained) smooth problems, thereby complementing known results for weak minimizers.
