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

Xiaojun Chen, Philippe Toint

Research output: Contribution to journalArticle


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 languageEnglish
Pages (from-to)1-27
Number of pages27
JournalMathematical Programming
Publication statusAccepted/In press - 1 Jan 2020



  • 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

Cite this