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

Research output: Contribution to journal › Article › peer-review

16 Downloads (Pure)

Abstract

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.

Original language	English
Pages (from-to)	47-78
Number of pages	32
Journal	Mathematical Programming
Volume	187
Issue number	1-2
Early online date	28 Jan 2020
DOIs	https://doi.org/10.1007/s10107-020-01470-9
Publication status	Published - May 2021

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

Access to Document

10.1007/s10107-020-01470-9

ctMP_FinalAccepted author manuscript, 315 KB

Cite this

@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

SN - 0025-5610

VL - 187

SP - 47

EP - 78

JO - Mathematical Programming

JF - Mathematical Programming

IS - 1-2

ER -

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

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

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

Complexity in nonlinear optimization

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

Cite this

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

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Research output

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

Projects

Complexity in nonlinear optimization

Activities

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

Cite this