  In a common formulation of semi-infinite programs, the infinite constraint
set is a requirement that a function parametrized by the decision variables is
nonnegative over an interval. If this function is sufficiently closely
approximable by a polynomial or a rational function, then the semi-infinite
program can be reformulated as an equivalent semidefinite program. Solving this
semidefinite program is challenging if the polynomials involved are of high
degree, due to numerical difficulties and bad scaling arising both from the
polynomial approximations and from the fact that the semidefinite programming
constraints coming from the sum-of-squares representation of nonnegative
polynomials are badly scaled. We combine rational function approximation
techniques and polynomial programming to overcome these numerical difficulties,
using sum-of-squares interpolants. Specifically, it is shown that the
conditioning of the reformulations using sum-of-squares interpolants does not
deteriorate with increasing degrees, and problems involving sum-of-squares
interpolants of hundreds of degrees can be handled without difficulty. The
proposed reformulations are sufficiently well scaled that they can be solved
easily with every commonly used semidefinite programming solver, such as
SeDuMi, SDPT3, and CSDP. Motivating applications include convex optimization
problems with semi-infinite constraints and semidefinite conic inequalities,
such as those arising in the optimal design of experiments. Numerical results
align with the theoretical predictions; in the problems considered, available
memory was the only factor limiting the degrees of polynomials, to
approximately 1000.
