Idioma:

Adaptive cubic regularisation methods for unconstrained optimization. Part II: worst-case function- and derivative-evaluation complexity

Cartis, Coralia ; Gould, Nicholas I. M. ; Toint, Philippe L.

Mathematical programming, 2011-12, Vol.130 (2), p.295-319 [Periódico revisado por pares]

Berlin/Heidelberg: Springer-Verlag

Texto completo disponível

Citações Citado por

Enviar para

Título:
Adaptive cubic regularisation methods for unconstrained optimization. Part II: worst-case function- and derivative-evaluation complexity
Autor: Cartis, Coralia ; Gould, Nicholas I. M. ; Toint, Philippe L.
Assuntos: Algorithms ; Applied sciences ; Approximation ; Calculus of variations and optimal control ; Calculus of Variations and Optimal Control; Optimization ; Combinatorics ; Complexity ; Curvature ; Exact sciences and technology ; Full Length Paper ; Iterative methods ; Laboratories ; Mathematical analysis ; Mathematical and Computational Physics ; Mathematical Methods in Physics ; Mathematical models ; Mathematical programming ; Mathematics ; Mathematics and Statistics ; Mathematics of Computing ; Methods ; Norms ; Numerical Analysis ; Operational research and scientific management ; Operational research. Management science ; Optimization ; Sciences and techniques of general use ; Studies ; Theoretical
É parte de: Mathematical programming, 2011-12, Vol.130 (2), p.295-319
Notas: ObjectType-Article-1
SourceType-Scholarly Journals-1
ObjectType-Feature-2
content type line 23
Descrição: An Adaptive Regularisation framework using Cubics (ARC) was proposed for unconstrained optimization and analysed in Cartis, Gould and Toint (Part I, Math Program, doi: 10.1007/s10107-009-0286-5 , 2009), generalizing at the same time an unpublished method due to Griewank (Technical Report NA/12, 1981, DAMTP, University of Cambridge), an algorithm by Nesterov and Polyak (Math Program 108(1):177–205, 2006) and a proposal by Weiser, Deuflhard and Erdmann (Optim Methods Softw 22(3):413–431, 2007). In this companion paper, we further the analysis by providing worst-case global iteration complexity bounds for ARC and a second-order variant to achieve approximate first-order, and for the latter second-order, criticality of the iterates. In particular, the second-order ARC algorithm requires at most iterations, or equivalently, function- and gradient-evaluations, to drive the norm of the gradient of the objective below the desired accuracy , and iterations, to reach approximate nonnegative curvature in a subspace. The orders of these bounds match those proved for Algorithm 3.3 of Nesterov and Polyak which minimizes the cubic model globally on each iteration. Our approach is more general in that it allows the cubic model to be solved only approximately and may employ approximate Hessians.
Editor: Berlin/Heidelberg: Springer-Verlag
Idioma: Inglês

Links

View record in Pascal Francis

Voltar para lista de resultados

Anterior Resultado 8 Avançar Ir para próxima página

Realização: Logos de Redes Sociais:

Adaptive cubic regularisation methods for unconstrained optimization. Part II: worst-case function- and derivative-evaluation complexity

Cartis, Coralia ; Gould, Nicholas I. M. ; Toint, Philippe L.

Berlin/Heidelberg: Springer-Verlag

Buscando em bases de dados remotas. Favor aguardar.