Browsing by Subject "optimointi"
Now showing items 1-4 of 4
-
(2024)Tutkielma käsittelee BFGS-menetelmää, joka on iteratiivinen optimointimenetelmä. Se on eräs kvasi-Newton-menetelmistä, ja sitä käytetään rajoittamattomassa epälineaarisessa optimoinnissa. Kvasi-Newton-menetelmissä approksimoidaan Newtonin menetelmässä esiintyvää Hessen matriisia, jonka laskeminen on usein vaikeaa tai liian kallista. Tutkielman luvussa 2 käydään läpi perustietoja optimoinnista ja lisäksi joitain muita esitietoja. Luvussa 3 käsitellään viivahakumenetelmiä. Ne ovat optimointimenetelmiä, joissa määritetään ensin hakusuunta ja sen jälkeen askelpituus. Ensin käydään läpi sopivan askelpituuden valintaa ja tutustutaan Wolfen ehtoihin, minkä jälkeen käsitellään viivahakumenetelmien suppenemista yleisesti. Lopuksi käsitellään Newtonin menetelmää ja Kvasi-Newton-menetelmiä sekä todistetaan, että Newtonin menetelmässä suppeneminen on neliöllistä ja kvasi-Newton-menetelmissä superlineaarista. Luvussa 4 käsitellään BFGS-menetelmää, jossa approksimoidaan Hessen matriisin käänteismatriisia. Ensin johdetaan BFGS-kaava, jonka jälkeen käydään läpi BFGS-algoritmin toteutusta. Tämän jälkeen todistetaan, että menetelmä suppenee, jos kohdefunktio on sileä ja aidosti konveksi, ja että suppeneminen on superlineaarista. Lisäksi tutkitaan menetelmän toimintaa käytännössä esimerkkien avulla. Lopuksi luvussa 5 tutustutaan rajatun muistin BFGS-menetelmään, joka ei vaadi kokonaisen matriisin tallentamista ja sopii täten erityisesti suurten ongelmien ratkaisuun.
-
(2022)Etuuspohjaisen eläkejärjestelyn laskennan tavoitteena on selvittää eläkevakuutuksen ottajan säästö- ja eläkesuunnitelmien yhteensopivuus ottaen samalla huomioon sopimukseen kuuluvat turvat ja muut kulut. Vapaaehtoisiin eläkesopimuksiin tehtyjen lakimuutosten seurauksena tällainen laskenta on monimutkaistunut huomattavasti 2000-luvun aikana ja vanhoille järjestelmille luodut laskentamallit eivät aina suoriudu toivotulla nopeudella. Tämän tutkielman aiheena on Profit Software Oy:n Profit Life & Pension -vakuutustenhallintajärjestelmän optimointi edellä kuvatun laskennan osalta.
-
(2024)In this thesis we study how to implement the one-dimensional fast Fourier transform (FFT) as a computer program in such a way that it works fast on inputs of all sizes. First we walk through the mathematical theory behind the continuous and the discrete Fourier transform (DFT), and study the motivation behind them. We explore both the one-dimensional and the multi-dimensional versions of the DFT. We also study the discrete cosine transform (DCT) and explore its differences to the Fourier transform. After that, we explore various known methods for implementing the fast Fourier transform. We focus especially on the Cooley-Tukey algorithm and its different forms in enough detail, that one can understand both how it works and how it was conceived. We also explore Rader’s and Bluestein’s FFT algorithms. After the theory we implement the DFT and the FFTs using the C++ programming language. We also devise and implement a combined algorithm, which seeks to provide the fastest possible transformation by choosing the optimal combination of algorithms in each case. We use C++20, which is the most recent standard version of C++ at the time of writing. We analyze the speed of the implemented methods, comparing them against each others and also compared to a famous FFT library, FFTW. In addition, we analyze the numeric accuracy of the implementations. Then we analyze the accuracy and applicability of the analysis methods and study the shortcomings and possible approaches for improving the implementations. We also present a simple example application of FFT, where the program attempts to identify the vowel sounds present in a voice sample. The purpose of this thesis is to offer the reader a clear example implementation of all the presented transforms and to thoroughly explore their limitations, weaknesses and strengths. For best value, the reader is expected to understand the basics of calculus and the basics of complex numbers. Especially the sum notation, ∑, and Euler’s formula are vital for understanding the mathematical theory. The computer source code is designed in such way that the reader does not need to know the details of the C++20 standard, or indeed even the C++ language, but experience in C programming will help.
-
(2022)Tässä tutkielmassa esitellään lyhyesti PCP-teoreema, minkä jälkeen tutkielmassa pala palalta käydään läpi teoreeman todistamiseen tarvittavia työkaluja. Tutkielman lopussa todistetaan PCP-teoreema. Vaativuusluokka PCP[O(log n), O(1)] sisältää ne ongelmat, joilla on olemassa todistus, josta vakio määrän bittejä lukien probabilistinen Turingin kone kykenee ratkaisemaan ongelman käyttäen samalla vain logaritmisen määrän satunnaisuutta suhteessa syötteen kokoon. PCP-teoreema väittää vaativuusluokan NP kuuluvan vaativuusluokkaan PCP[O(log n), O(1)]. Väritys on funktio, joka yhdistää kuhunkin joukon muuttujaan jonkin symbolin. Rajoite joillekin muuttujille on lista symboleista, joita rajoite sallii asetettavan muuttujille. Jos väritys asettaa muuttujille vain rajoitteen sallimia symboleja, rajoite on tyytyväinen väritykseen. Optimointi-ongelmat koskevat sellaisten väritysten etsimistä, että mahdollisimman moni rajoite joukosta rajoitteita on tyytyväinen väritykseen. PCP-teoreemalla on yhteys optimointi-ongelmiin, ja tätä yhteyttä hyödyntäen tutkielmassa todistetaan PCP-teoreema. Tutkielma seuraa I. Dinurin vastaavaa todistusta vuoden 2007 artikkelista The PCP Theorem by Gap Amplification. Rajoiteverkko on verkko, jonka kuhunkin kaareen liittyy jokin rajoite. Rajoiteverkkoon liittyy lisäksi aakkosto, joka sisältää ne symbolit, joita voi esiintyä verkon rajoitteissa ja värityksissä. Tutkielman päälauseen avulla kyetään kasvattamaan rajoiteverkossa olevien värityksiin tyytymättömien rajoitteiden suhteellista osuutta. Päälause takaa, että verkon koko säilyy samassa kokoluokassa, ja että verkon aakkoston koko ei muutu. Lisäksi jos verkon kaikki rajoitteet ovat tyytyväisiä johonkin väritykseen, päälauseen tuottaman verkon kaikki rajoitteet ovat edelleen tyytyväisiä johonkin väritykseen. Päälause koostetaan kolmessa vaiheessa, joita kutakin vastaa tutkielmassa yksi osio. Näistä ensimmäisessä, tutkielman osiossa 4, verkon rakenteesta muovataan sovelias seuraavia osioita varten. Toisessa vaiheessa, jota vastaa osio 6, verkon kävelyitä hyödyntäen kasvatetaan tyytymättömien rajoitteiden lukumäärää, mutta samalla verkon aakkosto kasvaa. Kolmannessa vaiheessa, osiossa 5, aakkoston koko saadaan pudotettua kolmeen sopivan algoritmin avulla. Osiossa 7 kootaan päälause ja todistetaan lausetta toistaen PCP-teoreema.
Now showing items 1-4 of 4