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

Xiaojun Chen, Philippe Toint

Research output: Contribution to journalArticle

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 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.
Original languageEnglish
Pages (from-to)1-27
Number of pages27
JournalMathematical Programming
Volume1902.10767
Publication statusAccepted/In press - 2020

Fingerprint

Constrained optimization
Constrained Optimization
Sparsity
Higher Order
Evaluation
Term
Objective function
Euclidean norm
Rotational symmetry
Regularization
Derivatives
Norm
Derivative
Approximation
Model

Keywords

  • complexity theory, nonlinear optimization, non-Lipschitz functions, partially-separable problems, group sparsity, isotropic model
  • nonlinear optimization
  • non-Lipschitz functions
  • partially-separable problems
  • group sparsity
  • isotropic model

Cite this

@article{88de5c3caf9644ec88443f79f04f2691,
title = "High-Order Evaluation Complexity for Convexly-Constrained Optimization with Non-Lipschitzian Group Sparsity Terms",
abstract = "This paper studies high-order evaluation complexity for partially separableconvexly-constrained optimization involving non-Lipschitzian group sparsityterms in a nonconvex objective function. We propose a partially separableadaptive regularization algorithm using a p-th order Taylor model and showthat the algorithm can produce an (epsilon,delta)-approximate q-th-orderstationary point at most O(epsilon^{-(p+1)/(p-q+1)}) evaluations of theobjective function and its first p derivatives (whenever they exist). Ourmodel uses the underlying rotational symmetry of the Euclidean norm functionto build a Lipschitzian approximation for the non-Lipschitzian group sparsityterms, which are defined by the group \ell_2-\ell_a norm with a in (0,1). Thenew result shows that the partially-separable structure and non-Lipschitziangroup sparsity terms in the objective function may not affect the worst-caseevaluation complexity order.",
keywords = "complexity theory, nonlinear optimization, non-Lipschitz functions, partially-separable problems, group sparsity, isotropic model, nonlinear optimization, non-Lipschitz functions, partially-separable problems, group sparsity, isotropic model",
author = "Xiaojun Chen and Philippe Toint",
year = "2020",
language = "English",
volume = "1902.10767",
pages = "1--27",
journal = "Mathematical Programming",
issn = "0025-5610",
publisher = "Springer-Verlag GmbH and Co. KG",

}

High-Order Evaluation Complexity for Convexly-Constrained Optimization with Non-Lipschitzian Group Sparsity Terms. / Chen, Xiaojun; Toint, Philippe.

In: Mathematical Programming, Vol. 1902.10767, 2020, p. 1-27.

Research output: Contribution to journalArticle

TY - JOUR

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

AU - Chen, Xiaojun

AU - Toint, Philippe

PY - 2020

Y1 - 2020

N2 - This paper studies high-order evaluation complexity for partially separableconvexly-constrained optimization involving non-Lipschitzian group sparsityterms in a nonconvex objective function. We propose a partially separableadaptive regularization algorithm using a p-th order Taylor model and showthat the algorithm can produce an (epsilon,delta)-approximate q-th-orderstationary point at most O(epsilon^{-(p+1)/(p-q+1)}) evaluations of theobjective function and its first p derivatives (whenever they exist). Ourmodel uses the underlying rotational symmetry of the Euclidean norm functionto build a Lipschitzian approximation for the non-Lipschitzian group sparsityterms, which are defined by the group \ell_2-\ell_a norm with a in (0,1). Thenew result shows that the partially-separable structure and non-Lipschitziangroup sparsity terms in the objective function may not affect the worst-caseevaluation complexity order.

AB - This paper studies high-order evaluation complexity for partially separableconvexly-constrained optimization involving non-Lipschitzian group sparsityterms in a nonconvex objective function. We propose a partially separableadaptive regularization algorithm using a p-th order Taylor model and showthat the algorithm can produce an (epsilon,delta)-approximate q-th-orderstationary point at most O(epsilon^{-(p+1)/(p-q+1)}) evaluations of theobjective function and its first p derivatives (whenever they exist). Ourmodel uses the underlying rotational symmetry of the Euclidean norm functionto build a Lipschitzian approximation for the non-Lipschitzian group sparsityterms, which are defined by the group \ell_2-\ell_a norm with a in (0,1). Thenew result shows that the partially-separable structure and non-Lipschitziangroup sparsity terms in the objective function may not affect the worst-caseevaluation complexity order.

KW - complexity theory, nonlinear optimization, non-Lipschitz functions, partially-separable problems, group sparsity, isotropic model

KW - nonlinear optimization

KW - non-Lipschitz functions

KW - partially-separable problems

KW - group sparsity

KW - isotropic model

M3 - Article

VL - 1902.10767

SP - 1

EP - 27

JO - Mathematical Programming

JF - Mathematical Programming

SN - 0025-5610

ER -