### Résumé

partially separable convexly constrained nonlinear optimization problems

whose objective function contains non-Lipschitzian $\ell_q$-norm

regularization terms for $q\in (0,1)$. It is shown that the algorithm using

an $p$-th order Taylor model for $p$ odd needs in general at most

$O(\epsilon^{-(p+1)/p})$ evaluations of the objective function and its

derivatives (at points where they are defined) to produce an

$\epsilon$-approximate first-order critical point. This result is obtained

either with Taylor models at the price of requiring the feasible set to

be 'kernel-centered' (which includes bound constraints and many other cases of

interest), or for non-Lipschitz models, at the price of passing the

difficulty to the computation of the step. Since this complexity bound

is identical in order to that already known for purely Lipschitzian

minimization subject to convex constraints [Cartis et al, 2016], the new

result shows that introducing non-Lipschitzian singularities in the objective

function may not affect the worst-case evaluation complexity order. The

result also shows that using the problem's partially separable structure (if present)

does not affect complexity order either. A final (worse) complexity bound is derived

for the case where Taylor models are used with a general convex feasible set.

langue | Anglais |
---|---|

Editeur | Arxiv |

Volume | 1704.06919 |

état | Publié - 24 avr. 2017 |

### Empreinte digitale

### mots-clés

### Citer ceci

*Partially separable convexly-constrained optimization with non-Lipschitzian singularities and its complexity*. Arxiv.

}

**Partially separable convexly-constrained optimization with non-Lipschitzian singularities and its complexity.** / Chen, Xiaojun; Toint, Philippe; Wang, Hong.

Résultats de recherche: Papier de travail › Article de travail

TY - UNPB

T1 - Partially separable convexly-constrained optimization with non-Lipschitzian singularities and its complexity

AU - Chen,Xiaojun

AU - Toint,Philippe

AU - Wang,Hong

PY - 2017/4/24

Y1 - 2017/4/24

N2 - An adaptive regularization algorithm using high-order models is proposed forpartially separable convexly constrained nonlinear optimization problemswhose objective function contains non-Lipschitzian $\ell_q$-normregularization terms for $q\in (0,1)$. It is shown that the algorithm usingan $p$-th order Taylor model for $p$ odd needs in general at most$O(\epsilon^{-(p+1)/p})$ evaluations of the objective function and itsderivatives (at points where they are defined) to produce an$\epsilon$-approximate first-order critical point. This result is obtainedeither with Taylor models at the price of requiring the feasible set tobe 'kernel-centered' (which includes bound constraints and many other cases ofinterest), or for non-Lipschitz models, at the price of passing thedifficulty to the computation of the step. Since this complexity boundis identical in order to that already known for purely Lipschitzianminimization subject to convex constraints [Cartis et al, 2016], the newresult shows that introducing non-Lipschitzian singularities in the objectivefunction may not affect the worst-case evaluation complexity order. Theresult also shows that using the problem's partially separable structure (if present)does not affect complexity order either. A final (worse) complexity bound is derivedfor the case where Taylor models are used with a general convex feasible set.

AB - An adaptive regularization algorithm using high-order models is proposed forpartially separable convexly constrained nonlinear optimization problemswhose objective function contains non-Lipschitzian $\ell_q$-normregularization terms for $q\in (0,1)$. It is shown that the algorithm usingan $p$-th order Taylor model for $p$ odd needs in general at most$O(\epsilon^{-(p+1)/p})$ evaluations of the objective function and itsderivatives (at points where they are defined) to produce an$\epsilon$-approximate first-order critical point. This result is obtainedeither with Taylor models at the price of requiring the feasible set tobe 'kernel-centered' (which includes bound constraints and many other cases ofinterest), or for non-Lipschitz models, at the price of passing thedifficulty to the computation of the step. Since this complexity boundis identical in order to that already known for purely Lipschitzianminimization subject to convex constraints [Cartis et al, 2016], the newresult shows that introducing non-Lipschitzian singularities in the objectivefunction may not affect the worst-case evaluation complexity order. Theresult also shows that using the problem's partially separable structure (if present)does not affect complexity order either. A final (worse) complexity bound is derivedfor the case where Taylor models are used with a general convex feasible set.

KW - Non_Lipschitz optimization

KW - Complexity theory

KW - partial separability

M3 - Working paper

VL - 1704.06919

BT - Partially separable convexly-constrained optimization with non-Lipschitzian singularities and its complexity

PB - Arxiv

ER -