### 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 |
---|---|

Publisher | Arxiv |

Pages | 1-27 |

Number of pages | 27 |

Volume | 1902.10767 |

Publication status | Published - 28 Feb 2019 |

### 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*. (pp. 1-27). Arxiv.

}

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

Research output: Working paper

TY - UNPB

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

AU - Chen, Xiaojun

AU - Toint, Philippe

PY - 2019/2/28

Y1 - 2019/2/28

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 - Working paper

VL - 1902.10767

SP - 1

EP - 27

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

PB - Arxiv

ER -