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

Xiaojun Chen, Philippe Toint

Résultats de recherche: Contribution à un journal/une revueArticleRevue par des pairs

1 Téléchargements (Pure)

Résumé

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.
langue originaleAnglais
Pages (de - à)47-78
Nombre de pages27
journalMathematical Programming
Volume187
Numéro de publication1-2
Les DOIs
Etat de la publicationE-pub ahead of print - 28 janv. 2020

Empreinte digitale Examiner les sujets de recherche de « High-Order Evaluation Complexity for Convexly-Constrained Optimization with Non-Lipschitzian Group Sparsity Terms ». Ensemble, ils forment une empreinte digitale unique.

Contient cette citation