evaluation complexity

Nonlinear Systems and Least-Squares, Unconstrained Optimization evaluation complexity, high-order, trust-region methods

A trust-region algorithm using inexact function and derivatives values is introduced for solving unconstrained smooth optimization problems. This algorithm uses high-order Taylor models and allows the search of strong approximate minimizers of arbitrary order. The evaluation complexity of finding a $q$-th approximate minimizer using this algorithm is then shown, under standard conditions, to be $\mathcal{O}\big(\min_{j\in\{1,\ldots,q\}}\epsilon_j^{-(q+1)}\big)$ … Read more

High-order Evaluation Complexity of a Stochastic Adaptive Regularization Algorithm for Nonconvex Optimization Using Inexact Function Evaluations and Randomly Perturbed Derivatives

Published: 2020/05/12

Bound-constrained Optimization, Constrained Nonlinear Optimization, Unconstrained Optimization evaluation complexity, inexact functions and derivatives, regularization, stochastic analysis

A stochastic adaptive regularization algorithm allowing random noise in derivatives and inexact function values is proposed for computing strong approximate minimizers of any order for inexpensively constrained smooth optimization problems. For an objective function with Lipschitz continuous p-th derivative in a convex neighbourhood of the feasible set and given an arbitrary optimality order q, it … Read more

Strong Evaluation Complexity Bounds for Arbitrary-Order Optimization of Nonconvex Nonsmooth Composite Functions

Published: 2020/01/29

Bound-constrained Optimization, Constrained Nonlinear Optimization, Unconstrained Optimization composite nonlinear optimization, evaluation complexity, high-order optimality

We introduce the concept of strong high-order approximate minimizers for nonconvex optimization problems. These apply in both standard smooth and composite non-smooth settings, and additionally allow convex or inexpensive constraints. An adaptive regularization algorithm is then proposed to find such approximate minimizers. Under suitable Lipschitz continuity assumptions, whenever the feasible set is convex, it is … Read more

Minimization of nonsmooth nonconvex functions using inexact evaluations and its worst-case complexity

Published: 2019/02/27

Serge Gratton

Constrained Nonlinear Optimization, Nonsmooth Optimization, Unconstrained Optimization composite functions, evaluation complexity, inexact evaluations, nonconvex optimization, nonsmooth problems

Ehouarn Simon

An adaptive regularization algorithm using inexact function and derivatives evaluations is proposed for the solution of composite nonsmooth nonconvex optimization. It is shown that this algorithm needs at most O(|log(epsilon)|.epsilon^{-2}) evaluations of the problem’s functions and their derivatives for finding an $\epsilon$-approximate first-order stationary point. This complexity bound therefore generalizes that provided by [Bellavia, Gurioli, … Read more

Convergence and evaluation-complexity analysis of a regularized tensor-Newton method for solving nonlinear least-squares problems subject to convex constraints

Published: 2019/01/17

Nonlinear Systems and Least-Squares convergence analysis, evaluation complexity, nonlinear least squares, tensor-newton methods

Tyrone Rees

Jennifer Scott

Given a twice-continuously differentiable vector-valued function $r(x)$, a local minimizer of $\|r(x)\|_2$ within a convex set is sought. We propose and analyse tensor-Newton methods, in which $r(x)$ is replaced locally by its second-order Taylor approximation. Convergence is controlled by regularization of various orders. We establish global convergence to a constrained first-order critical point of $\|r(x)\|_2$, … Read more

Adaptive regularization algorithms with inexact evaluations for nonconvex optimization

Published: 2018/11/09, Updated: 2019/04/19

Constrained Nonlinear Optimization, Data-Mining, Unconstrained Optimization evaluation complexity, inexact functions and derivatives, machine learning, regularization, subsampling methods

A regularization algorithm using inexact function values and inexact derivatives is proposed and its evaluation complexity analyzed. This algorithm is applicable to unconstrained problems and to problems with inexpensive constraints (that is constraints whose evaluation and enforcement has negligible cost) under the assumption that the derivative of highest degree is beta-H\”{o}lder continuous. It features a … Read more

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

Published: 2018/11/03

Constrained Nonlinear Optimization, Data-Mining, Nonlinear Systems and Least-Squares evaluation complexity, high-order optimization, nonconvex optimization, regularization, set-constrained problems, sharp bounds

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 … Read more

Worst-case evaluation complexity and optimality of second-order methods for nonconvex smooth optimization

Published: 2017/09/21