Sharp worst-case evaluation complexity bounds for arbitrary-order nonconvex optimization with inexpensive constraints

Coralia Cartis, Nicholas I M Gould, Philippe Toint

Résultats de recherche: Papier de travailArticle de travail

Résumé

We provide sharp worst-case evaluation complexity bounds for nonconvex
minimization problems with general inexpensive constraints, i.e.\ problems
where the cost of evaluating/enforcing of the (possibly nonconvex or even
disconnected) constraints, if any, is negligible compared to that of evaluating the objective function. These bounds unify, extend or improve all known upper and lower complexity bounds for unconstrained and convexly-constrained problems. It is shown that, given an accuracy level epsilon, a degree of highest available Lipschitz continuous derivatives p and a desired optimality order q between one and p, a conceptual regularization algorithm requires no more than O(epsilon^{-(p+1)/(p-q+1)}$ evaluations of the objective function and its derivatives to compute a suitably approximate q-th order minimizer. With an appropriate choice of the regularization, a similar result also holds if the $p$-th derivative is merely Hölder rather than Lipschitz continuous. We provide an example that shows that the above complexity bound is sharp for unconstrained and a wide class of constrained problems; we also give reasons for the optimality of regularization methods from a worst-case complexity point of view, within a large class of algorithms that use the same derivative information.
langue originaleAnglais
EditeurArxiv
Nombre de pages30
Volume1811-01220
étatPublié - 3 nov. 2018

Empreinte digitale

Derivatives
Costs

Citer ceci

@techreport{a24885b9e168475c9e39b6a498e46db5,
title = "Sharp worst-case evaluation complexity bounds for arbitrary-order nonconvex optimization with inexpensive constraints",
abstract = "We provide sharp worst-case evaluation complexity bounds for nonconvexminimization problems with general inexpensive constraints, i.e.\ problemswhere the cost of evaluating/enforcing of the (possibly nonconvex or evendisconnected) constraints, if any, is negligible compared to that of evaluating the objective function. These bounds unify, extend or improve all known upper and lower complexity bounds for unconstrained and convexly-constrained problems. It is shown that, given an accuracy level epsilon, a degree of highest available Lipschitz continuous derivatives p and a desired optimality order q between one and p, a conceptual regularization algorithm requires no more than O(epsilon^{-(p+1)/(p-q+1)}$ evaluations of the objective function and its derivatives to compute a suitably approximate q-th order minimizer. With an appropriate choice of the regularization, a similar result also holds if the $p$-th derivative is merely H{\"o}lder rather than Lipschitz continuous. We provide an example that shows that the above complexity bound is sharp for unconstrained and a wide class of constrained problems; we also give reasons for the optimality of regularization methods from a worst-case complexity point of view, within a large class of algorithms that use the same derivative information.",
author = "Coralia Cartis and Gould, {Nicholas I M} and Philippe Toint",
year = "2018",
month = "11",
day = "3",
language = "English",
volume = "1811-01220",
publisher = "Arxiv",
type = "WorkingPaper",
institution = "Arxiv",

}

Sharp worst-case evaluation complexity bounds for arbitrary-order nonconvex optimization with inexpensive constraints. / Cartis, Coralia; Gould, Nicholas I M; Toint, Philippe.

Arxiv, 2018.

Résultats de recherche: Papier de travailArticle de travail

TY - UNPB

T1 - Sharp worst-case evaluation complexity bounds for arbitrary-order nonconvex optimization with inexpensive constraints

AU - Cartis, Coralia

AU - Gould, Nicholas I M

AU - Toint, Philippe

PY - 2018/11/3

Y1 - 2018/11/3

N2 - We provide sharp worst-case evaluation complexity bounds for nonconvexminimization problems with general inexpensive constraints, i.e.\ problemswhere the cost of evaluating/enforcing of the (possibly nonconvex or evendisconnected) constraints, if any, is negligible compared to that of evaluating the objective function. These bounds unify, extend or improve all known upper and lower complexity bounds for unconstrained and convexly-constrained problems. It is shown that, given an accuracy level epsilon, a degree of highest available Lipschitz continuous derivatives p and a desired optimality order q between one and p, a conceptual regularization algorithm requires no more than O(epsilon^{-(p+1)/(p-q+1)}$ evaluations of the objective function and its derivatives to compute a suitably approximate q-th order minimizer. With an appropriate choice of the regularization, a similar result also holds if the $p$-th derivative is merely Hölder rather than Lipschitz continuous. We provide an example that shows that the above complexity bound is sharp for unconstrained and a wide class of constrained problems; we also give reasons for the optimality of regularization methods from a worst-case complexity point of view, within a large class of algorithms that use the same derivative information.

AB - We provide sharp worst-case evaluation complexity bounds for nonconvexminimization problems with general inexpensive constraints, i.e.\ problemswhere the cost of evaluating/enforcing of the (possibly nonconvex or evendisconnected) constraints, if any, is negligible compared to that of evaluating the objective function. These bounds unify, extend or improve all known upper and lower complexity bounds for unconstrained and convexly-constrained problems. It is shown that, given an accuracy level epsilon, a degree of highest available Lipschitz continuous derivatives p and a desired optimality order q between one and p, a conceptual regularization algorithm requires no more than O(epsilon^{-(p+1)/(p-q+1)}$ evaluations of the objective function and its derivatives to compute a suitably approximate q-th order minimizer. With an appropriate choice of the regularization, a similar result also holds if the $p$-th derivative is merely Hölder rather than Lipschitz continuous. We provide an example that shows that the above complexity bound is sharp for unconstrained and a wide class of constrained problems; we also give reasons for the optimality of regularization methods from a worst-case complexity point of view, within a large class of algorithms that use the same derivative information.

M3 - Working paper

VL - 1811-01220

BT - Sharp worst-case evaluation complexity bounds for arbitrary-order nonconvex optimization with inexpensive constraints

PB - Arxiv

ER -