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

4 Citations (Scopus)


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)1-32
Number of pages32
JournalMathematical Programming
Publication statusAccepted/In press - 28 Jan 2020


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

ASJC Scopus subject areas

  • Software
  • Mathematics(all)

Cite this