# Strong Evaluation Complexity Bounds for Arbitrary-Order Optimization of Nonconvex Nonsmooth Composite Functions

Coralia Cartis, Nick Gould, Philippe Toint

Résultats de recherche: Papier de travail

34 Téléchargements (Pure)

## Résumé

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 O(max_{1 \leq j \leq q}\epsilon_j^{-(p+1)/(p-j+1)}) evaluations of the problem’s functions and their derivatives, where \epsilon_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 O(max_{1 \leq j \leq q}\epsilon_j^{-q(p+1)/p}) evaluations. If the problem is composite, and either q > 1 or the feasible set is not convex, the bound is then O(max_{1 \leq j \leq q}\epsilon_j^{-(q+1)}) 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.
langue originale Anglais Arxiv 2001-10802 Publié - 30 janv. 2020

## Empreinte digitale

Examiner les sujets de recherche de « Strong Evaluation Complexity Bounds for Arbitrary-Order Optimization of Nonconvex Nonsmooth Composite Functions ». Ensemble, ils forment une empreinte digitale unique.
• ### Evaluation complexity of algorithms for nonconvex optimization

Cartis, C., Gould, N. I. M. & TOINT, P., juil. 2022, SIAM. 600 p. (SIAM-MOS Series on Optimization)

Résultats de recherche: Livre/Rapport/RevueLivre

• ### High-Order Evaluation Complexity for Convexly-Constrained Optimization with Non-Lipschitzian Group Sparsity Terms

Chen, X. & Toint, P., mai 2021, 187, 1-2, p. 47-78 32 p.

Résultats de recherche: Contribution à un journal/une revueArticleRevue par des pairs

Accès ouvert
File
40 Téléchargements (Pure)
• ### A concise second-order complexity analysis for unconstrained optimization using high-order regularized models

Cartis, C., Gould, N. I. M. & Toint, P. L., 3 mars 2020, 35, 2, p. 243-256 14 p.

Résultats de recherche: Contribution à un journal/une revueArticleRevue par des pairs

• ### Complexity in nonlinear optimization

Toint, P., Gould, N. I. M. & Cartis, C.

1/11/08 → …

Projet: Recherche

1/01/87 → …

Projet: Axe de recherche

• ### Recent results in worst-case evaluation complexity for smooth and non-smooth, exact and inexact, nonconvex optimization

Philippe TOINT (Orateur)

8 mai 2020

Activité: Discours ou présentation Discours invité