<p>The problem under consideration is an unconstrained mini-mization problem in noisy environment. The common approach for solving the problem is Stochastic Approximation (SA) algorithm. We propose a class of adaptive step size schemes for the SA algorithm. The step size selection in the proposed schemes is based on the objective functionvalues. At each iterate, interval estimates of the optimal function value are constructed using the xed number of previously observed function values. If the observed function value in the current iterate is larger than the upper bound of the interval, we reject the current iterate. If the observed function value in the current iterate is smaller than the lower bound of the interval, we suggest a larger step size in the next iterate. Otherwise, if the function value lies in the interval, we propose a small safe step size in the next iterate. In this manner, a faster progress of the algorithm is ensured when it is expected that larger steps will improve the performance of the algorithm. We propose two main schemes which dier in the intervals that we construct at each iterate. In the rst scheme, we construct a symmetrical interval that can be viewed as a condence-like interval for the optimal function value. The bounds of the interval are shifted means of the xed number of previously observed function values. The generalization of this scheme using a convex combination instead of the mean is also presented. In the second scheme, we use the minimum and the maximum of previous noisy function values as the lower and upper bounds of the interval, respectively. The step size sequences generated by the proposed schemes satisfy the step size convergence conditions for the SA algorithm almost surely. Performance of SA algorithms with the new step size schemes is tested on a set of standard test problems. Numerical results support theoretical expectations and verify eciency of the algorithms in comparison to other relevant modications of SA algorithms. Application of the algorithms in LASSO regression models is also considered. The algorithms are applied for estimation of the regression parameters where the objective function contains L<sub>1</sub> penalty.</p> / <p>Predmet istraživanja doktorske disertacije su numerički postupci za rešavanje problema stohastičke optimizacije. Najpoznatiji numerički postupak za rešavanje pomenutog problema je algoritam stohastičke aproksimacije (SA). U disertaciji se predlaže nova klasa šema za prilagođavanje dužina koraka u svakoj iteraciji. Odabir dužina koraka u predloženim šemama se zasniva na vrednostima funkcije cilja. U svakoj iteraciji formira se intervalna ocena optimalne vrednosti funkcije cilja koristeći samo registrovane vrednosti funkcije cilja iz ksnog broja prethodnih iteracija. Ukoliko je vrednost funkcije cilja u trenutnoj iteraciji veća od gornje granice intervala, iteracija se odbacuje. Korak dužine 0 se koristi u narednoj iteraciji. Ako je trenutna vrednost funkcije cilja manja od donje granice intervala, predlaže se duži korak u narednoj iteraciji. Ukoliko vrednost funkcije leži u intervalu, u narednoj iteraciji se koristi korak dobijen harmonijskim pravilom. Na ovaj način se obezbeđuje brzi progres algoritma i izbegavaju mali koraci posebno kada se povećava broj iteracija. Šeme izbegavaju korake proporcionalne sa 1/k kada se očekuje da ce duži koraci poboljšati proces optimizacije. Predložene šeme se razlikuju u intervalima koji se formiraju u svakoj iteraciji. U prvoj predloženoj šemi se formira veštački interval poverenja za ocenu optimalne vrednosti funkcije cilja u svakoj iteraciji. Granice tog intervala se uzimaju za kriterijume dovoljnog smanjenja ili rasta funkcije cilja. Predlaže se i uopštenje ove šeme tako što se umesto srednje vrednosti koristi konveksna kombinacija prethodnih vrednosti funkcije cilja. U drugoj šemi, kriterijum po kom se prilagođavaju dužine koraka su minimum i maksimum prethodnih registrovanih vrednosti funkcije cilja. Nizovi koji se formiranju predloženim šemama zadovoljavaju uslove potrebne za konvergenciju SA algoritma skoro sigurno. SA algoritmi sa novim šemama za prilagođavanje dužina koraka su testirani na standardnim test problemima i upoređ eni sa SA algoritmom i njegovim postojećim modikacijama. Rezultati pokazuju napredak u odnosu na klasičan algoritam stohastičke aproksimacije sa determinističkim nizom dužine koraka kao i postojećim adaptivnim algoritmima. Takođe se razmatra primena novih algoritama na LASSO regresijske modele. Algoritmi su primenjeni za ocenjivanje parametara modela.</p>
| Identifer | oai:union.ndltd.org:uns.ac.rs/oai:CRISUNS:(BISIS)104786 |
| Date | 25 September 2017 |
| Creators | Kresoja Milena |
| Contributors | Lužanin Zorana, Krejić Nataša, Rapajić Sanja, Stojkovska Irena, Ovcin Zoran |
| Publisher | Univerzitet u Novom Sadu, Prirodno-matematički fakultet u Novom Sadu, University of Novi Sad, Faculty of Sciences at Novi Sad |
| Source Sets | University of Novi Sad |
| Language | English |
| Detected Language | English |
| Type | PhD thesis |
Page generated in 0.0022 seconds