Polynomial Approximations for Infinite-Dimensional Optimization Problems
Creators: name: Bampou, Dimitra
Publisher: name: Imperial College London
Year: 2012

description: Many real-life decision problems in management science and engineering involve decisions that are functions of time and/or uncertainty. The resulting optimization models are therefore naturally formulated on infinite-dimensional function spaces. However, such infinite-dimensional optimization problems are notoriously difficult, and to solve them one usually has to resort to approximation methods. The objective of this thesis is to devise polynomial approximations for solving continuous linear programs and multi-stage stochastic programs, both of which constitute important classes of infinite-dimensional optimization problems with manifold practical applications. Approximating the functional decision variables by polynomials allows us to apply sum-of-squares techniques from algebraic geometry to reformulate the resulting problems as tractable semidefinite programs, which can be solved efficiently with interior point algorithms. Continuous linear programs represent deterministic optimization problems whose decision variables are functions of time subject to pointwise and dynamic linear constraints. They have attracted considerable interest due to their potential for modelling manufacturing, scheduling and routing problems. While efficient simplex-type algorithms have been developed for separated continuous linear programs, crude time discretization remains the method of choice for solving general (non-separated) problem instances. In this thesis we propose a more generic approximation scheme for non-separated continuous linear programs, which are believed to be NP-hard. We approximate the functional decision variables (policies) by polynomial and piecewise polynomial decision rules. To estimate the approximation error, we also compute a lower bound by solving a dual continuous linear program in (piecewise) polynomial decision rules. Multi-stage stochastic programming provides a versatile framework for optimal decision making under uncertainty, but it gives rise to hard functional optimization problems since the adaptive recourse decisions must be modelled as functions of some or all uncertain parameters. We propose to approximate these recourse decisions by polynomial decision rules and show that the best polynomial decision rule of a fixed degree can be computed efficiently. Again, we show that the suboptimality of the best polynomial decision rule can be estimated efficiently by solving a dual version of the stochastic program in polynomial decision rules. Recent progress in the theory of dynamic risk measures has found a strong echo in stochastic programming, where the time-consistency of dynamic decision making under uncertainty is currently under scrutiny. We extend the concepts of coherence and time consistency to stochastic programming models subject to distributional ambiguity, which motivates us to introduce robust dynamic risk measures. We discuss conditions under which these robust risk measures inherit coherence and time-consistency from their nominal counterparts. We also propose an approximation scheme based on polynomial decision rules for solving linear multi-stage stochastic programs involving robust dynamic risk measures.