This thesis evaluates how the evolutionary algorithm CMA-ES (Covariance Matrix Adaption Evolution Strategy) can be used for optimizing the total initial margin for a network of banks trading bilateral OTC derivatives. The algorithm is a stochastic method for optimization of non-linear and, but not limited to, non-convex functions. The algorithm searches for an optimum by generating normally distributed samples and iteratively updating the mean and covariance matrix of the search distribution using the best candidate solutions in the sampled population. In this thesis, feasible solutions are represented by the null space obtained from the constraint of keeping all banks' market exposure unchanged throughout the optimization, and the generated samples for each iteration correspond to linear combinations of the base vectors spanning this null space. In particular, this thesis investigates how different representations of this null space affect the convergence speed of the algorithm. By applying the algorithm to problems of varying sizes, using several different null space representations coming from different matrix decomposition methods, it is found that as long as an orthonormal representation is used it does not matter which matrix decomposition method it comes from. This is found to be because, given any orthonormal null space representation, the algorithm will at start generate a rotationally invariant sample space in its search for the optimal solution, independent of the specific null space representation. If the representation is not orthogonal, the initial sample will in contrast be in the shape of an ellipsoid and thus biased in certain directions, which in general affects the performance negatively. A non-orthonormal representation can converge faster in specific optimization problems, if the direction of the solution is known in advance and the sample space is pointed towards that direction. However, the benefit of this aspect is limited in a realistic scenario and an orthonormal representation is recommended. Furthermore, as it is shown that different orthonormal representations perform equally, it is implied that other characteristics can be considered when deciding which matrix decomposition method to use; such as the importance of fast computation or desire for a sparse representation. / Denna avhandling utvärderar hur CMA-ES (Covariance Matrix Adaption Evolution Strategy) kan användas för att optimera en total "initial margin" för ett nätverk av banker som handlar bilaterala OTC derivat. Algoritmen är en stokastisk metod för optimering av icke-linjära och, men inte enbart, icke-konvexa funktioner. Algoritmen söker efter ett optimum genom att generera normalfördelade utfall och iterativt uppdatera medelvärdet och kovariansmatrisen för sök-fördelningen med hjälp av de bästa lösningarna i varje iteration. I detta arbete representeras tillåtna lösningar till problemet av nollrummet från bivillkoret att alla bankers marknadsexponering ska vara oförändrade genom optimeringen och de genererade utfallen består av slumpade linjärkombinationer av nollrummets basvektorer. I synnerhet undersöks hur olika representationer av nollrummet påverkar konvergenshastigheten för algoritmen. Algoritmen har applicerats med flera olika nollrumsrepresentationer, framtagna genom olika matrisfaktoriseringsmetoder, och det kan konstateras att så länge nollrummsrepresentationen är ortonormal är valet av faktoreringsmetod obetydlig. Detta då användande av orthornormala nollrumsrpresentationer i algoritmen leder till en initialt symmetrisk, rotationsmässigt invariant, sökning efter den optimala lösningen. Om representationen inte är ortogonal kommer det resulterande sökområdet i varje iteration att ha formen av en ellipsoid och sålunda viktas i vissa riktningar, vilket i allmänhet påverkar prestandan negativt. Emellertid kan en icke-ortonormal representation konvergera snabbare i specifika scenarier, givet att lösningens riktning är känd i förväg och sökområdet kan pekas mot den riktningen. Vidare, eftersom det har visats att olika ortonormala representationer konvergerar lika fort, innebär resultatet att andra egenskaper kan beaktas vid val av matrisfaktoriseringsmetod, såsom vikten av snabb beräkning eller önskan om en gles representation.
| Identifer | oai:union.ndltd.org:UPSALLA1/oai:DiVA.org:kth-273628 |
| Date | January 2020 |
| Creators | Barnholdt, Jacob, Carlsson, Filip |
| Publisher | KTH, Matematisk statistik |
| Source Sets | DiVA Archive at Upsalla University |
| Language | English |
| Detected Language | English |
| Type | Student thesis, info:eu-repo/semantics/bachelorThesis, text |
| Format | application/pdf |
| Rights | info:eu-repo/semantics/openAccess |
| Relation | TRITA-SCI-GRU ; 2020:057 |
Page generated in 0.002 seconds