Globally convergent modifications of the Newton method

U ovom radu predstavljena je osnovna Newtonova metoda za rješavanje problema bezuvjetne minimizacije i nelinearnih jednadžbi, njena konvergencija, nedostatci i neka bitna svojstva za daljni razvoj metode. Glavni problem metode je nedostatak globalne konvergencije što je razlog uvođenja globalnih metoda poput line search i trust region algoritama. Osnovna razlika line search i trust region pristupa je u tome što line search traži smjer napretka iteracije (smjer silaska) i odabire duljinu koraka u tom smjeru, dok trust region odabire područje regije povjerenja (područje maksimalne duljine koraka) i odabire točku napretka unutar te regije. Nadalje, iskazane su prednosti i nedostatci globalnih metoda, od kojih je glavni nedostatak brza konvergencija, zbog čega se uvodi kvazi-Newtonov algoritam. Glavni zadatak je inkorporiranje lokalno brze Newtonove metodu s globalno konvergentnim metodama kako bi se iskoristile prednosti, a izbjegli nedostatci, pojedine metode. Svi algoritmi se prvo formiraju za rješavanje problema bezuvjetne minimizacije, a zatim se preslikavaju na probleme nelinearnih jednadžbi. Naposljetku su definirani problemi skaliranja i potrebni kriteriji zaustavljanja kako bi se algoritmi mogli provesti u praksi. Na kraju rada je provedeno testiranje nekoliko jednostavnih problema bezuvjetne minimizacije, ali je pritom teško odgovoriti na pitanje koji je algoritam bolji jer, primjena određene metode, ovisi i o zadanim početnim uvjetima i parametrima, kao i o željenom rezultatu. Međutim, danas je razvijeno mnogo modificiranih oblika postavljenih algoritama i najčešće se kod rješavanja problema primjenjuju njihove kombinacije.In this thesis, we have introduced Newton’s method for unconstrained minimization and nonlinear equations, its convergence, shortcomings and basic properties for further development of methods. Main problem of Newton’s method is lack of global convergence and that is why we introduce global methods like line search and trust region algorithms. Difference between line search and trust region approach is that line search finds direction of improvement and then selects the step length in descent direction, and trust region first selects the trusted region of maximum allowed step and then finds a point of improvement in the region. Furthermore, the advantages and disadvantages of global methods are shown. Main defect is lack of fast convergence, which is a reason for development of quasi-Newton’s method. Main purpose is to incorporate locally fast convergent Newton’s method with globally convergent methods in order to take their advantages, and avoid their disadvantages. All algorithms are formed to solve problems of unconstrained optimization, and then discussed their modifications for nonlinear equations. Lastly, scaling and stopping criteria, important for real practice, are discussed. At the end, several examples of simple optimization problems are tested. It is not easy to say which method is better to apply, because its performance and execution depends on several reasons, like starting point or parameter setting. However, there are many different modified algorithms today, and its combinations are being used for solving the problems