Worst-case complexity analysis of derivative-free nonmonotone methods for solving nonlinear systems of equations

Abstract

Resumo: Nesta dissertação estudam os u m a classe geral de m étodos não-m onótonos sem derivadas p a ra soluçao de sistem as de equações não-lineares, incluindo o m etodo N -D F-SA N E proposto em (IMA J. Num er. Anal. 29: 814-825, 2009). Esses m etodos correspondem a m etodos de otim izacao sem derivadas aplicados a m inim izacao de um a funçao m erito conveniente. O com portam ento nao-m onotono e controlado por duas sequencias de param etros que definem os procedim entos de busca linear. Supondo que a funcao que define as equacães não-lineares possui Jacobiana Lipschitz, m ostram os que os m etodos da referida classe precisam de no m axim o O (| log(e)|e_2) avaliaçães da funçao p ara gerarem um po nto estacionario da funcao m erito com precisao t > 0. A generalidade da nossa analise perm ite m ais liberdade p ara o desenvolvim ento de novos m etodos em term os das escolhas p a ra as sequencias que controlam o com portam ento não-m onotono dos valores da funcao m erito. E ssa característica e ilu strad a por experim entos num ericos prelim inares incluindo novas variantes do m etodo N-DF-SANE. P a la v ra s -c h a v e : sistemas não-lineares de grande porte, métodos não-monótonos, métodos sem derivadas, complexidade de pior caso

Abstract: In this dissertatio n we study a wide class of derivative-free nonm onotone m ethods for solving nonlinear system s of equations, covering th e m eth od N -D F-SA N E proposed in (IMA J. N um er. Anal. 29: 814-825, 2009). These m ethods correspond to derivative-free optim ization m ethods applied to th e m inim ization of a suitable m erit function. T he nonm onotonicity is controlled by two sequences of p aram eters th a t define th e line-search procedure. A ssum ing th a t th e m apping defining th e nonlinear equations has Lipschitz continuous Jacobian, we show th a t th e m ethods in th e referred class need a t m ost O (| log(e)|e_2) function evaluations to generate an e-approxim ate statio n ary point of th e m erit function. T he generality of our analysis allows m ore freedom for th e design of new m ethods in term s of th e choices for th e sequences th a t control th e nonm onotone behavior of th e m erit functio n values. This feature is illu strated by prelim inary num erical experim ents including new variants of th e m eth od N-DF-SAN E. K e y w o rd s : large scale nonlinear systems, nonmonotone methods, derivative-free m eth ods, worst-case complexity