Adaptive regularization for nonconvex optimization using inexact function values and randomly perturbed derivatives

被引：10

作者：

Bellavia, S. ^{[1
]}

Gurioli, G. ^{[2
]}

Morini, B. ^{[1
]}

Toint, Ph. L. ^{[3
]}

机构：

[1] Univ Firenze, Dipartimento Ingn Ind, Florence, Italy

[2] Univ Firenze, Dipartimento Matemat & Informat Ulisse Dini, Florence, Italy

[3] Univ Namur, Namur Ctr Complex Syst naXys, 61 Rue Bruxelles, B-5000 Namur, Belgium

来源：

JOURNAL OF COMPLEXITY | 2022年 / 68卷

关键词：

Evaluation complexity; Regularization methods; Inexact functions and derivatives; Stochastic analysis; CASE EVALUATION COMPLEXITY; CUBIC REGULARIZATION; ALGORITHM; DESCENT;

D O I：

10.1016/j.jco.2021.101591

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

A regularization algorithm allowing random noise in derivatives and inexact function values is proposed for computing approximate local critical points of any order for smooth unconstrained optimization problems. For an objective function with Lipschitz continuous p-th derivative and given an arbitrary optimality order q < p, an upper bound on the number of function and derivatives evaluations is established for this algorithm. This bound is in expectation, and in terms of a power of the required tolerances, this power depending on whether q 2 or q 2. Moreover these bounds are sharp in the order of the accuracy tolerances. An extension to convexly constrained problems is also outlined. (c) 2021 Elsevier Inc. All rights reserved.

引用

页数：25

共 37 条

[21] Convergence analysis of a Lasserre hierarchy of upper bounds for polynomial minimization on the sphere [J].