Original title:
Algoritmy pro vybrané geometrické problémy nad zonotopy a jejich aplikace v optimalizaci a v analýze dat
Translated title:
Algorithms for various geometric problems over zonotopes and their applications in optimization and data analysis
Authors:
Rada, Miroslav ; Černý, Michal (advisor) ; Vlach, Milan (referee) ; Kopa, Miloš (referee) Document type: Doctoral theses
Year:
2009
Language:
cze Publisher:
Vysoká škola ekonomická v Praze Abstract:
[cze][eng] 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.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:
arrangement of hyperplanes; interval regression model; Löwner-John's ellipsoid; nonconvex optimization; zonotope; arrangement nadrovin; intervalová lineární regrese; Löwner-Johnův elipsoid; nekonvexní optimalizace; zonotop
Institution: University of Economics, Prague
(web)
Document availability information: Available in the digital repository of the University of Economics, Prague. Original record: http://www.vse.cz/vskp/eid/44716