Show simple item record

Optimization of problems with stochastic equality constraints – penaltyvariable sample size methods

dc.contributor.advisorKrklec-Jerinkić, Nataša
dc.contributor.otherKrejić, Nataša
dc.contributor.otherKrklec-Jerinkić, Nataša
dc.contributor.otherRapajić, Sanja
dc.contributor.otherOvcin, Zoran
dc.creatorRožnjik, Andrea
dc.date.accessioned2019-01-31T11:59:30Z
dc.date.available2019-01-31T11:59:30Z
dc.date.available2020-07-03T13:39:52Z
dc.date.issued2019-01-24
dc.identifier.urihttps://www.cris.uns.ac.rs/DownloadFileServlet/Disertacija153804843966981.pdf?controlNumber=(BISIS)107819&fileName=153804843966981.pdf&id=12029&source=NaRDuS&language=srsr
dc.identifier.urihttp://nardus.mpn.gov.rs/handle/123456789/10708
dc.identifier.urihttps://www.cris.uns.ac.rs/record.jsf?recordId=107819&source=NaRDuS&language=srsr
dc.identifier.urihttps://www.cris.uns.ac.rs/DownloadFileServlet/IzvestajKomisije153872286291658.pdf?controlNumber=(BISIS)107819&fileName=153872286291658.pdf&id=12089&source=NaRDuS&language=srsr
dc.description.abstractU disertaciji je razmatran problem stohastičkog programiranja s ograničenjima tipa jednakosti, odnosno problem minimizacije s ograničenjima koja su u obliku matematičkog očekivanja. Za rešavanje posmatranog problema kreirana su dva iterativna postupka u kojima se u svakoj iteraciji računa s uzoračkim očekivanjem kao aproksimacijom matematičkog očekivanja. Oba postupka koriste prednosti postupaka s promenljivom veličinom uzorka zasnovanih na adaptivnom ažuriranju veličine uzorka. To znači da se veličina uzorka određuje na osnovu informacija u tekućoj iteraciji. Konkretno, tekuće informacije o preciznosti aproksimacije očekivanja i tačnosti aproksimacije rešenja problema definišu veličinu uzorka za narednu iteraciju. Oba iterativna postupka su zasnovana na linijskom pretraživanju, a kako je u pitanju problem s ograničenjima, i na kvadratnom kaznenom postupku prilagođenom stohastičkom okruženju. Postupci su zasnovani na istim idejama, ali s različitim pristupom. Po prvom pristupu postupak je kreiran za rešavanje SAA reformulacije problema stohastičkog programiranja, dakle za rešavanje aproksimacije originalnog problema. To znači da je uzorak definisan pre iterativnog postupka, pa je analiza konvergencije algoritma deterministička. Pokazano je da se, pod standardnim pretpostavkama, navedenim algoritmom dobija podniz iteracija čija je tačka nagomilavanja KKT tačka SAA reformulacije. Po drugom pristupu je formiran algoritam za rešavanje samog problema stohastičkog programiranja, te je analiza konvergencije stohastička. Predstavljenim algoritmom se generiše podniz iteracija čija je tačka nagomilavanja, pod standardnim pretpostavkama za stohastičku optimizaciju, skoro sigurno KKT tačka originalnog problema. Predloženi algoritmi su implementirani na istim test problemima. Rezultati numeričkog testiranja prikazuju njihovu efikasnost u rešavanju posmatranih problema u poređenju s postupcima u kojima je ažuriranje veličine uzorka zasnovano na unapred definisanoj šemi. Za meru efikasnosti je upotrebljen broj izračunavanja funkcija. Dakle, na osnovu rezultata dobijenih na skupu testiranih problema može se zaključiti da se adaptivnim ažuriranjem veličine uzorka može uštedeti u broju evaluacija funkcija kada su u pitanju i problemi s ograničenjima. Kako je posmatrani problem deterministički, a formulisani postupci su stohastički, prva tri poglavlja disertacije sadrže osnovne pojmove determinističke i stohastiˇcke optimizacije, ali i kratak pregled definicija i teorema iz drugih oblasti potrebnih za lakše praćenje analize originalnih rezultata. Nastavak disertacije čini prikaz formiranih algoritama, analiza njihove konvergencije i numerička implementacija.  sr
dc.description.abstractStochastic programming problem with equality constraints is considered within thesis. More precisely, the problem is minimization problem with constraints in the form of mathematical expectation. We proposed two iterative methods for solving considered problem. Both procedures, in each iteration, use a sample average function instead of the mathematical expectation function, and employ the advantages of the variable sample size method based on adaptive updating the sample size. That means, the sample size is determined at every iteration using information from the current iteration. Concretely, the current precision of the approximation of expectation and the quality of the approximation of solution determine the sample size for the next iteration. Both iterative procedures are based on the line search technique as well as on the quadratic penalty method adapted to stochastic environment, since the considered problem has constraints. Procedures relies on same ideas, but the approach is different. By first approach, the algorithm is created for solving an SAA reformulation of the stochastic programming problem, i.e., for solving the approximation of the original problem. That means the sample size is determined before the iterative procedure, so the convergence analyses is deterministic. We show that, under the standard assumptions, the proposed algorithm generates a subsequence which accumulation point is the KKT point of the SAA problem. Algorithm formed by the second approach is for solving the stochastic programming problem, and therefore the convergence analyses is stochastic. It generates a subsequence with  accumulation point that is almost surely the KKT point of the original problem, under the standard assumptions for stochastic optimization.for sample size. The number of function evaluations is used as measure of efficiency. Results of the set of tested problems suggest that it is possible to make smaller number of function evaluations by adaptive sample size scheduling in the case of constrained problems, too. Since the considered problem is deterministic, but the formed procedures are stochastic, the first three chapters of thesis contain basic notations of deterministic and stochastic optimization, as well as a short sight of definitions and theorems from another fields necessary for easier tracking the original results analysis. The rest of thesis consists of the presented algorithms, their convergence analysis and numerical implementation.en
dc.languagesr (latin script)
dc.publisherУниверзитет у Новом Саду, Природно-математички факултетsr
dc.rightsopenAccessen
dc.sourceУниверзитет у Новом Садуsr
dc.subjectproblem stohasičkog programiranjasr
dc.subjectstochastic programming problemen
dc.subjectograničenja tipa jednakostisr
dc.subjectSAA aproksimacijasr
dc.subjectmetodi s promenljivom veličinom uzorkasr
dc.subjectkazneni postupcisr
dc.subjectequality constraintsen
dc.subjectsample average approximationen
dc.subjectvariable sample size methodsen
dc.subjectpenalty methodsen
dc.titleOptimizacija problema sa stohastičkim ograničenjima tipa jednakosti – kazneni metodi sa promenljivom veličinom uzorkasr
dc.title.alternativeOptimization of problems with stochastic equality constraints – penaltyvariable sample size methodsen
dc.typedoctoralThesissr
dc.rights.licenseBY-NC-ND
dc.identifier.fulltexthttp://nardus.mpn.gov.rs/bitstream/id/37228/IzvestajKomisije.pdf
dc.identifier.fulltexthttp://nardus.mpn.gov.rs/bitstream/id/37227/Disertacija.pdf


Files in this item

Thumbnail
Thumbnail

This item appears in the following Collection(s)

Show simple item record