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

• 成果类型: Article
• 署名作者: Chen, X.; Toint, Ph L.
• 署名单位: Hong Kong Polytechnic University; University of Namur
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-020-01470-9
• 发表日期: 2021
• 页码: 47-78
• 关键词: algorithms; RECOVERY; minimization; signals; unary

摘要

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 (d)-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.