# Complexity of partially separable convexly constrained optimization with non-Lipschitzian singularities

Xiaojun Chen, Philippe Toint, Hong Wang

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

14 Téléchargements (Pure)

## Résumé

An adaptive regularization algorithm using high-order models is proposed for solving partially separable convexly constrained nonlinear optimization problems whose objective function contains non-Lipschitzian 'q-norm regularization terms for q ϵ (0; 1). It is shown that the algorithm using a pth-order Taylor model for p odd needs in general at most O(ϵ -(p+1)=p) evaluations of the objective function and its derivatives (at points where they are defined) to produce an ϵ-approximate first-order critical point. This result is obtained either with Taylor models, at the price of requiring the feasible set to be kernel centered" (which includes bound constraints and many other cases of interest), or with non-Lipschitz models, at the price of passing the difficulty to the computation of the step. Since this complexity bound is identical in order to that already known for purely Lipschitzian minimization subject to convex constraints [C. Cartis, N. I. M. Gould, and Ph. L. Toint, IMA J. Numer. Anal., 32 (2012), pp. 1662-1695], the new result shows that introducing non-Lipschitzian singularities in the objective function may not affect the worst-case evaluation complexity order. The result also shows that using the problem's partially separable structure (if present) does not affect the complexity order either. A final (worse) complexity bound is derived for the case where Taylor models are used with a general convex feasible set.

langue originale Anglais 874-903 30 SIAM Journal on Optimization 29 1 https://doi.org/10.1137/18m1166511 Publié - 15 avr. 2019

## Empreinte digitale

Examiner les sujets de recherche de « Complexity of partially separable convexly constrained optimization with non-Lipschitzian singularities ». Ensemble, ils forment une empreinte digitale unique.
• ### 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 progress in evaluation complexity for nonlinear optimization

Philippe Toint (Orateur)

4 oct. 2019

Activité: Types de discours ou de présentationDiscours invité

• ### Departement of Applied Mathematics, Polytechnic University of Hong Kong

Philippe Toint (Chercheur visiteur)

15 nov. 201815 déc. 2018

Activité: Types de Visite d'une organisation externeVisite à une institution académique externe

• ### A path and some adventures in the jungle of high-order nonlinear optimization

Philippe Toint (Orateur)

23 oct. 2017

Activité: Types de discours ou de présentationDiscours invité