## 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 language | English |
---|---|

Pages (from-to) | 1-32 |

Number of pages | 32 |

Journal | Mathematical Programming |

DOIs | |

Publication status | Accepted/In press - 28 Jan 2020 |

## Keywords

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

## ASJC Scopus subject areas

- Software
- Mathematics(all)