Title | ||
---|---|---|
Improved second-order evaluation complexity for unconstrained nonlinear optimization using high-order regularized models. |
Abstract | ||
---|---|---|
The unconstrained minimization of a sufficiently smooth objective function $f(x)$ is considered, for which derivatives up to order $p$, $pgeq 2$, are assumed to be available. An adaptive regularization algorithm is proposed that uses Taylor models of the objective of order $p$ and that is guaranteed to find a first- and second-order critical point in at most $O left(maxleft( epsilon_1^{-frac{p+1}{p}}, epsilon_2^{-frac{p+1}{p-1}} right) right)$ function and derivatives evaluations, where $epsilon_1$ and $epsilon_2 u003e0$ are prescribed first- and second-order optimality tolerances. Our approach extends the method in Birgin et al. (2016) to finding second-order critical points, and establishes the novel complexity bound for second-order criticality under identical problem assumptions as for first-order, namely, that the $p$-th derivative tensor is Lipschitz continuous and that $f(x)$ is bounded from below. The evaluation-complexity bound for second-order criticality improves on all such known existing results. |
Year | Venue | Field |
---|---|---|
2017 | Optimization Methods & Software | Discrete mathematics,Mathematical optimization,Combinatorics,Tensor,Nonlinear programming,Critical point (thermodynamics),Minification,Lipschitz continuity,Criticality,Critical point (mathematics),Mathematics,Bounded function |
DocType | Volume | Citations |
Journal | abs/1708.04044 | 3 |
PageRank | References | Authors |
0.42 | 9 | 3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Coralia Cartis | 1 | 451 | 28.74 |
Nicholas I. M. Gould | 2 | 1445 | 123.86 |
Philippe L. Toint | 3 | 1397 | 127.90 |