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

Xiaojun Chen, Philippe Toint, Hong Wang

Résultats de recherche: Papier de travailArticle de travail

### Résumé

An adaptive regularization algorithm using high-order models is proposed for
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 Arxiv 1704.06919 Publié - 24 avr. 2017

### Empreinte digitale

Constrained Optimization
Singularity
Model
Constrained optimization
Objective function
Regularization
Evaluation
Bound Constraints
Non-Lipschitz
Convex Constraints
Nonlinear Optimization
Nonlinear Problem
Critical point
Odd
Higher Order
kernel
Optimization Problem
First-order
Norm
Derivative

### Citer ceci

@techreport{fb433d3900264f1a8c2c31ba9c05df1b,
title = "Partially separable convexly-constrained optimization with non-Lipschitzian singularities and its complexity",
abstract = "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 \{textquoteleft}kernel-centered\{textquoteleft} (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\{textquoteleft}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.",
keywords = "Non_Lipschitz optimization, Complexity theory, partial separability",
author = "Xiaojun Chen and Philippe Toint and Hong Wang",
year = "2017",
month = "4",
day = "24",
language = "English",
volume = "1704.06919",
publisher = "Arxiv",
type = "WorkingPaper",
institution = "Arxiv",

}

Arxiv, 2017.

Résultats de recherche: Papier de travailArticle 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 -