Algorithms for various geometric problems over zonotopes and their applications in optimization and data analysis
| Thesis title: | Algoritmy pro vybrané geometrické problémy nad zonotopy a jejich aplikace v optimalizaci a v analýze dat |
|---|---|
| Author: | Rada, Miroslav |
| Thesis type: | Disertační práce |
| Supervisor: | Černý, Michal |
| Opponents: | Vlach, Milan; Kopa, Miloš |
| Thesis language: | Česky |
| Abstract: | Disertační práce sjednocuje nejvýznamnější výsledky disertanta v oblasti algoritmů pro práci se zonotopy a jejich aplikací v optimalizaci a statistice. Z oblasti výpočetní geometrie práce přináší zejména nový algoritmus pro enumeraci vrcholů zonotopu, který je kompaktní a polynomiální ve velikosti výstupu a který teoreticky i empiricky překonává dosavadní konkurenci v kategorii algoritmů se stejnými výpočetně-teoretickými vlastnostmi, a dále také polynomiální algoritmus pro libovolně přesnou aproximaci zonotopu Löwner-Johnovým elipsoidem. V aplikační oblasti práce propojuje lineární regresní model s intervalovými výstupy s problematikou zonotopů a diskutuje využití prezentovaných geometrických algoritmů pro řešení jistého nekonvexního optimalizačního problému. |
| Keywords: | nekonvexní optimalizace; intervalová lineární regrese; Löwner-Johnův elipsoid; arrangement nadrovin; zonotop |
| Thesis title: | Algorithms for various geometric problems over zonotopes and their applications in optimization and data analysis |
|---|---|
| Author: | Rada, Miroslav |
| Thesis type: | Dissertation thesis |
| Supervisor: | Černý, Michal |
| Opponents: | Vlach, Milan; Kopa, Miloš |
| Thesis language: | Česky |
| Abstract: | The thesis unifies the most important author's results in the field of algorithms concerning zonotopes and their applications in optimization and statistics. The computational-geometric results consist of a new compact output-sensitive algorithm for enumerating vertices of a zonotope, which outperforms the rival algorithm with the same complexity-theoretic properties both theoretically and empirically, and a polynomial algorithm for arbitrarily precise approximation of a zonotope with the Löwner-John ellipsoid. In the application area, the thesis presents a result, which connects linear regression model with interval outputs with the zonotope matters. The usage of presented geometric algorithms for solving a nonconvex optimisation problem is also discussed. |
| Keywords: | nonconvex optimization; interval regression model; Löwner-John's ellipsoid; arrangement of hyperplanes; zonotope |
Information about study
| Study programme: | Kvantitativní metody v ekonomice/Ekonometrie a operační výzkum |
|---|---|
| Type of study programme: | Doktorský studijní program |
| Assigned degree: | Ph.D. |
| Institutions assigning academic degree: | Vysoká škola ekonomická v Praze |
| Faculty: | Faculty of Informatics and Statistics |
| Department: | Department of Econometrics |
Information on submission and defense
| Date of assignment: | 24. 2. 2009 |
|---|---|
| Date of submission: | 1. 12. 2014 |
| Date of defense: | 18. 2. 2015 |
| Identifier in the InSIS system: | https://insis.vse.cz/zp/19143/podrobnosti |