Parametric Linear and Quadratic Optimization by Elimination

. We propose a new elimination method for linear and quadratic optimization involving parametric coefficients. In comparison to the classical Fourier-Motzkin method that is of doubly exponential worst-case complexity our method is singly exponential in the worst case. Moreover it applies also to the minimization of a quadratic objective functions without convexity hypothesis under linear constraints, and to objective functions with arbitrary parametric coefficients. For problems with additive parameters the method is worst-case optimal. Examples computed in a REDUCE-- implementation confirm the superiority of the method over Fourier-Motzkin and its applicability to problems of interesting size. 1 Introduction In 1826 Fourier found a method for solving systems of linear inequalities by successive elimination of variables (see [Fourier]). The method may be regarded as an extension of Gauss elimination for systems of linear equations. It was forgotten until rediscovered in this century..