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)