A Region-Dividing Technique for Constructing the Sum-of-Squares Approximations to Robust Semidefinite Programs

In this paper, we present a novel approach to robust semidefinite programs, whose coefficient matrices depend polynomially on uncertain parameters. The procedure to construct an approximate problem for a given robust semidefinite program is based on the sum-of-squares representation of a positive semidefinite polynomial matrix. In contrast to the conventional sum-of-squares approach, quality of the approximation is improved by dividing the parameter region into several subregions. The optimal value of the approximate problem converges to that of the original problem as the resolution of the division becomes finer. An advantage of this approach is that an upper bound on the approximation error can be explicitly obtained in terms of the resolution of the division. Numerical examples on polynomial optimizations are presented to show usefulness of the present approach. We also consider exploitation of sparsity of the given problem with respect to the uncertain parameters, in order to construct a reduced-size approximate problem.