Nonlinear parametric optimization using cylindrical algebraic decomposition

Abstract

In this paper, a new method is presented for optimization of parametric families of polynomial functions subject to polynomial constraints. The method is based on cylindrical algebraic decomposition (CAD). Given the polynomial objective and constraints, the method constructs the corresponding CAD offline, extracting in advance all the relevant structural information. Then, given the parameter value, an online procedure uses the precomputed information to efficiently evaluate the optimal solution of the original optimization problem. The method is very general and can be applied to a broad range of problems.