Abstract
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 language | English |
|---|---|
| Pages (from-to) | 1-27 |
| Number of pages | 27 |
| Journal | Mathematical Programming |
| Volume | 1902.10767 |
| Publication status | Accepted/In press - 2020 |
Fingerprint
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
}
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 journal › Article
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 -