Projects per year

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

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 |

DOIs | |

Publication status | Accepted/In press - 1 Jan 2020 |

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

## Fingerprint Dive into the research topics of 'High-Order Evaluation Complexity for Convexly-Constrained Optimization with Non-Lipschitzian Group Sparsity Terms'. Together they form a unique fingerprint.

## Projects

- 1 Active

## Complexity in nonlinear optimization

TOINT, P., Gould, N. I. M. & Cartis, C.

1/11/08 → …

Project: Research

## Activities

## Recent results in worst-case evaluation complexity for smooth and non-smooth, exact and inexact, nonconvex optimization

Philippe TOINT (Speaker)

8 May 2020

Activity: Talk or presentation types › Invited talk

## Departement of Applied Mathematics, Polytechnic University of Hong Kong

Philippe Toint (Visiting researcher)

15 Nov 2018 → 15 Dec 2018

Activity: Visiting an external institution types › Visiting an external academic institution

## Cite this

Chen, X., & Toint, P. (Accepted/In press). High-Order Evaluation Complexity for Convexly-Constrained Optimization with Non-Lipschitzian Group Sparsity Terms.

*Mathematical Programming*,*1902.10767*, 1-27. https://doi.org/10.1007/s10107-020-01470-9