Nicholas I. M. Gould – Optimization Online

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

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

On monotonic estimates of the norm of the minimizers of regularized quadratic functions in Krylov spaces

Published: 2019/04/05, Updated: 2019/04/09

Unconstrained Optimization krylov spaces, regularized quadratic functions

Marius Lange

We show that the minimizers of regularized quadratic functions restricted to their natural Krylov spaces increase in Euclidean norm as the spaces expand. CitationTechnical Report RAL-TR-2019-005, STFC-Rutherford Appleton Laboratory, Oxfordshire, England, April 5th 2019ArticleDownload View PDF

Error estimates for iterative algorithms for minimizing regularized quadratic subproblems

Published: 2019/03/30, Updated: 2019/04/01

Nonlinear Optimization cubic regularization subproblem, error estimates, krylov methods, trust-region methods

Valeria Simoncini

We derive bounds for the objective errors and gradient residuals when finding approximations to the solution of common regularized quadratic optimization problems within evolving Krylov spaces. These provide upper bounds on the number of iterations required to achieve a given stated accuracy. We illustrate the quality of our bounds on given test examples. CitationTechnical Report … 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

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

Unconstrained Optimization evaluation complexity, nonconvex optimization, second-order methods

We establish or refute the optimality of inexact second-order methods for unconstrained nonconvex optimization from the point of view of worst-case evaluation complexity, improving and generalizing the results of Cartis, Gould and Toint (2010,2011). To this aim, we consider a new general class of inexact second-order algorithms for unconstrained optimization that includes regularization and trust-region … Read more

Improved second-order evaluation complexity for unconstrained nonlinear optimization using high-order regularized models

Published: 2017/08/13

Nonlinear Optimization complexity, regularisation methods

The unconstrained minimization of a sufficiently smooth objective function $f(x)$ is considered, for which derivatives up to order $p$, $p\geq 2$, are assumed to be available. An adaptive regularization algorithm is proposed that uses Taylor models of the objective of order $p$ and that is guaranteed to find a first- and second-order critical point in … Read more

Optimality of orders one to three and beyond: characterization and evaluation complexity in constrained nonconvex optimization

Published: 2017/05/20