Quasi Newton Methods for Stochastic Programming Problems

Abstract

<p>Posmatra se problem minimizacije bez ograničenja. U determinističkom&nbsp;slučaju ti problemi se uspe&scaron;no re&scaron;avaju iterativnim Kvazi Njutnovim postupcima.&nbsp;Ovde se istražuje &nbsp;stohastički slučaj, kada su poznate vrednosti funkcije cilja i njenog gradijenta na koje je uticao &scaron;um. Koristi se novi način određivanja dužina koraka, koji kombinuje metod linijskog pretraživanja i metod stohastičke aproksimacije tako da zadrži dobre osobine oba pristupa i obezbedi veću efikasnost postupka. Metod je testiran u kombinaciji sa vi&scaron;e načina izbora pravca u iterativnom postupku. Dokazana je konvergencija novog postupka i testiranjem na velikom broju standardnih test problema pokazana njegova efikasnost. Takođe se za re&scaron;avanje problema ekvilibriuma u Neoklasičnoj ekonomiji predlaže i dokazuje konvergencija jednog Fiksnog Njutnovog postupka. U zadatku nalaženja re&scaron;enja za niz problema kojima se preciznije modelira slučajni sistem, ovaj Fiksni Njutnov postupak ostvaruje veliku u&scaron;tedu CPU vremena u odnosu na Njutnov metod. U prvom delu teze je dat op&scaron;ti teoretski uvod. U drugom delu je dat pregled relevantnih rezultata iz posmatranih oblasti zajedno sa dva originalna rezultata. U trećem &nbsp;delu su dati rezultati numeričkih testova.</p>

<p>The problem under consideration is unconstrained minimization pro-blem. The problem in deterministic case is often solved with Quasi Newton met-hods. In noisy environment, which is considered, new approach for step length along descent direction is used. The new approach combines line search and stoc-hastic&nbsp; approximation method using good characteristics of both enabling better efficiency. The convergence is proved. New step length is tested with three de-scent directions. Many standard test problems show the efficiency of the met-hod. Also, a new, affordable procedure based on application of the fixed Newton method for a sequence of equilibrium problems generated by simulation is intro-duced. The convergence conditions of the method are derived. The numerical results show a clear difference in the quality of information obtained by solving a sequence of problems if compared with the single equilibrium problem. In the first part general theoretical introduction is given. In the second part a survey of results from scientific community is given together with original results. The third part contains many numerical tests of new methods that show its efficiency.</p>