High-order evaluation complexity for convexly-constrained optimization with non-Lipschitzian group sparsity terms

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.