Adaptive regularization minimization algorithms with nonsmooth norms

International audienceAbstract An adaptive regularization algorithm (AR$1p$GN) for unconstrained nonlinear minimization is considered, which uses a model consisting of a Taylor expansion of arbitrary degree and regularization term involving a possibly nonsmooth norm. It is shown that the nonsmoothness of the norm does not affect the ${\mathcal {O}}(\epsilon _1^{-(p+1)/p})$ upper bound on evaluation complexity for finding first-order $\epsilon _1$-approximate minimizers using $p$ derivatives, and that this result does not hinge on the equivalence of norms in $\mathbb {R}^n$. It is also shown that, if $p=2$, the bound of ${\mathcal {O}}(\epsilon _2^{-3})$ evaluations for finding second-order $\epsilon _2$-approximate minimizers still holds for a variant of AR$1p$GN named AR2GN, despite the possibly nonsmooth nature of the regularization term. Moreover, the adaptation of the existing theory for handling the nonsmoothness results is an interesting modification of the subproblem termination rules, leading to an even more compact complexity analysis. In particular, it is shown when the Newton’s step is acceptable for an adaptive regularization method. The approximate minimization of quadratic polynomials regularized with nonsmooth norms is then discussed, and a new approximate second-order necessary optimality condition is derived for this case. A specialized algorithm is then proposed to enforce first- and second-order conditions that are strong enough to ensure the existence of a suitable step in AR$1p$GN (when $p=2$) and in AR2GN, and its iteration complexity is analyzed. A final section discusses how practical approximate curvature measures may lead to weaker second-order optimality guarantees