Sparse polynomial systems in optimization

Systems of polynomial equations appear both in mathematics, as well as in many applications in the sciences, economics and engineering. Solving these systems is at the heart of computational algebraic geometry, a field which is often associated with symbolic computations based on Gr¨obner bases. Over the last thirty years, increasing performance and versatility made numerical algebraic geometry emerge as an alternative. It enables us to solve problems which are infeasible with symbolic methods. The focus of this thesis is the rich interplay between algebraic geometry, numerical computation and optimization in various instances. As a first application of algebraic geometry, we investigate global optimization problems whose objective function and constraints are all described by multivariate polynomials. One of the most important, and also most common, features of real world data is sparsity. We explore the effects of sparsity in global optimization, when exhibited by constraints and objective functions. Exploiting this property can lead to dramatic improvements of computational performance of algorithms. As a second application of geometry we study a particularly structured class of polynomial programs which stems from the optimization of sequencial decision rules. In the framework of partially observable Markov decision rules, an agent manipulates a system in a sequence of events. It selects an action at every time step, which in turn influences the state of the system at the next time step, and depending on the state it receives an instantaneous reward. Optimizing the long term reward has a long-standing history in computer science, economics and statistics. The ability to incorporate nondeterministic effects makes the framework particularly well suited for real world applications. We initiate a novel, geometric perspective on the underlying optimization problem and explore algorithmic consequences. As a third application of geometry we present the usage of tropical geometry in order to numerically compute ...