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

Xiaojun Chen; Philippe Toint

doi:10.1007/s10107-020-01470-9

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

Xiaojun Chen, Philippe Toint

Namur Institute for Complex Systems

Résultats de recherche: Contribution à un journal/une revue › Article › Revue par des pairs

13 Téléchargements (Pure)

Résumé

This paper studies high-order evaluation complexity for partially separable
convexly-constrained optimization involving non-Lipschitzian group sparsity
terms in a nonconvex objective function. We propose a partially separable
adaptive regularization algorithm using a p-th order Taylor model and show
that the algorithm can produce an (epsilon,delta)-approximate q-th-order
stationary point at most O(epsilon^{-(p+1)/(p-q+1)}) evaluations of the
objective function and its first p derivatives (whenever they exist). Our
model uses the underlying rotational symmetry of the Euclidean norm function
to build a Lipschitzian approximation for the non-Lipschitzian group sparsity
terms, which are defined by the group \ell_2-\ell_a norm with a in (0,1). The
new result shows that the partially-separable structure and non-Lipschitzian
group sparsity terms in the objective function may not affect the worst-case
evaluation complexity order.

langue originale	Anglais
Pages (de - à)	47-78
Nombre de pages	32
journal	Mathematical Programming
Volume	187
Numéro de publication	1-2
Date de mise en ligne précoce	28 janv. 2020
Les DOIs	https://doi.org/10.1007/s10107-020-01470-9
Etat de la publication	Publié - mai 2021

Accès au document

10.1007/s10107-020-01470-9

ctMP_FinalAccepted author manuscript, 315 KB

Autres fichiers et liens

Link to publication in Scopus

4 Citations
3 Article
1 Livre
1 Article de travail

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/Revue › Livre
Sharp worst-case evaluation complexity bounds for arbitrary-order nonconvex optimization with inexpensive constraints
Toint, P., Cartis, C. & Gould, N. I. M., janv. 2020, Dans: SIAM Journal on Optimization. 30, 1, p. 513-541 29 p.
Résultats de recherche: Contribution à un journal/une revue › Article › Revue par des pairs

Accès ouvert
File
22 Téléchargements (Pure)
Strong Evaluation Complexity Bounds for Arbitrary-Order Optimization of Nonconvex Nonsmooth Composite Functions
Cartis, C., Gould, N. & Toint, P., 30 janv. 2020, Arxiv.
Résultats de recherche: Papier de travail › Article de travail

File

1 Actif

Complexity in nonlinear optimization
TOINT, P., Gould, N. I. M. & Cartis, C.
1/11/08 → …
Projet: Recherche

1 Discours invité
1 Visite à une institution académique externe

Recent results in worst-case evaluation complexity for smooth and non-smooth, exact and inexact, nonconvex optimization
Philippe TOINT (Orateur)
8 mai 2020
Activité: Types de discours ou de présentation › Discours invité
Departement of Applied Mathematics, Polytechnic University of Hong Kong
Philippe Toint (Chercheur visiteur)
15 nov. 2018 → 15 déc. 2018
Activité: Types de Visite d'une organisation externe › Visite à une institution académique externe

Contient cette citation

@article{88de5c3caf9644ec88443f79f04f2691,

title = "High-Order Evaluation Complexity for Convexly-Constrained Optimization with Non-Lipschitzian Group Sparsity Terms",

abstract = "This paper studies high-order evaluation complexity for partially separableconvexly-constrained optimization involving non-Lipschitzian group sparsityterms in a nonconvex objective function. We propose a partially separableadaptive regularization algorithm using a p-th order Taylor model and showthat the algorithm can produce an (epsilon,delta)-approximate q-th-orderstationary point at most O(epsilon^{-(p+1)/(p-q+1)}) evaluations of theobjective function and its first p derivatives (whenever they exist). Ourmodel uses the underlying rotational symmetry of the Euclidean norm functionto build a Lipschitzian approximation for the non-Lipschitzian group sparsityterms, which are defined by the group \ell_2-\ell_a norm with a in (0,1). Thenew result shows that the partially-separable structure and non-Lipschitziangroup sparsity terms in the objective function may not affect the worst-caseevaluation complexity order.",

keywords = "complexity theory, nonlinear optimization, non-Lipschitz functions, partially-separable problems, group sparsity, isotropic model, nonlinear optimization, non-Lipschitz functions, partially-separable problems, group sparsity, isotropic model",

author = "Xiaojun Chen and Philippe Toint",

note = "Funding Information: Xiaojun Chen would like to thank Hong Kong Research Grant Council for Grant PolyU153001/18P. Philippe Toint would like to thank the Hong Kong Polytechnic University for its support while this research was being conducted. We would like to thank the editor and two referees for their helpful comments. Publisher Copyright: {\textcopyright} 2020, Springer-Verlag GmbH Germany, part of Springer Nature and Mathematical Optimization Society.",

year = "2021",

month = may,

doi = "10.1007/s10107-020-01470-9",

language = "English",

volume = "187",

pages = "47--78",

journal = "Mathematical Programming",

issn = "0025-5610",

publisher = "Springer-Verlag GmbH and Co. KG",

number = "1-2",

}

TY - JOUR

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

AU - Chen, Xiaojun

AU - Toint, Philippe

N1 - Funding Information: Xiaojun Chen would like to thank Hong Kong Research Grant Council for Grant PolyU153001/18P. Philippe Toint would like to thank the Hong Kong Polytechnic University for its support while this research was being conducted. We would like to thank the editor and two referees for their helpful comments. Publisher Copyright: © 2020, Springer-Verlag GmbH Germany, part of Springer Nature and Mathematical Optimization Society.

PY - 2021/5

Y1 - 2021/5

N2 - This paper studies high-order evaluation complexity for partially separableconvexly-constrained optimization involving non-Lipschitzian group sparsityterms in a nonconvex objective function. We propose a partially separableadaptive regularization algorithm using a p-th order Taylor model and showthat the algorithm can produce an (epsilon,delta)-approximate q-th-orderstationary point at most O(epsilon^{-(p+1)/(p-q+1)}) evaluations of theobjective function and its first p derivatives (whenever they exist). Ourmodel uses the underlying rotational symmetry of the Euclidean norm functionto build a Lipschitzian approximation for the non-Lipschitzian group sparsityterms, which are defined by the group \ell_2-\ell_a norm with a in (0,1). Thenew result shows that the partially-separable structure and non-Lipschitziangroup sparsity terms in the objective function may not affect the worst-caseevaluation complexity order.

AB - This paper studies high-order evaluation complexity for partially separableconvexly-constrained optimization involving non-Lipschitzian group sparsityterms in a nonconvex objective function. We propose a partially separableadaptive regularization algorithm using a p-th order Taylor model and showthat the algorithm can produce an (epsilon,delta)-approximate q-th-orderstationary point at most O(epsilon^{-(p+1)/(p-q+1)}) evaluations of theobjective function and its first p derivatives (whenever they exist). Ourmodel uses the underlying rotational symmetry of the Euclidean norm functionto build a Lipschitzian approximation for the non-Lipschitzian group sparsityterms, which are defined by the group \ell_2-\ell_a norm with a in (0,1). Thenew result shows that the partially-separable structure and non-Lipschitziangroup sparsity terms in the objective function may not affect the worst-caseevaluation complexity order.

KW - complexity theory, nonlinear optimization, non-Lipschitz functions, partially-separable problems, group sparsity, isotropic model

KW - nonlinear optimization

KW - non-Lipschitz functions

KW - partially-separable problems

KW - group sparsity

KW - isotropic model

UR - http://www.scopus.com/inward/record.url?scp=85078436836&partnerID=8YFLogxK

U2 - 10.1007/s10107-020-01470-9

DO - 10.1007/s10107-020-01470-9

M3 - Article

AN - SCOPUS:85078436836

VL - 187

SP - 47

EP - 78

JO - Mathematical Programming

JF - Mathematical Programming

SN - 0025-5610

IS - 1-2

ER -

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

Résumé

Accès au document

Autres fichiers et liens

Empreinte digitale

Résultat de recherche

Evaluation complexity of algorithms for nonconvex optimization

Sharp worst-case evaluation complexity bounds for arbitrary-order nonconvex optimization with inexpensive constraints

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

Projets

Complexity in nonlinear optimization

Activités

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

Departement of Applied Mathematics, Polytechnic University of Hong Kong

Contient cette citation