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

X. Chen, Ph L. Toint

Research output: Journal article publicationJournal articleAcademic researchpeer-review

8 Citations (Scopus)

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 pth order Taylor model and show that the algorithm needs at most O(ϵ- ( p + 1 ) / ( p - q + 1 )) evaluations of the objective function and its first p derivatives (whenever they exist) to produce an (ϵ, δ) -approximate qth-order stationary point. Our algorithm 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 ℓ2–ℓa norm with a∈ (0 , 1). The new result shows that the partially-separable structure and non-Lipschitzian group sparsity terms in the objective function do not affect the worst-case evaluation complexity order.

Original languageEnglish
Pages (from-to)47-78
Number of pages32
JournalMathematical Programming
Volume187
Issue number1-2
DOIs
Publication statusAccepted/In press - May 2021

Keywords

  • Complexity theory
  • Group sparsity
  • Isotropic model
  • Non-Lipschitz functions
  • Nonlinear optimization
  • Partially-separable problems

ASJC Scopus subject areas

  • Software
  • General Mathematics

Fingerprint

Dive into the research topics of 'High-Order Evaluation Complexity for Convexly-Constrained Optimization with Non-Lipschitzian Group Sparsity Terms'. Together they form a unique fingerprint.

Cite this