Exploiting sparsity in the matrix-dilation approach to robust semidefinite programming

A computationally improved approach is proposed for a robust semidefinite programming problem whose constraint is polynomially dependent on uncertain parameters. By exploiting sparsity, the proposed approach gives an approximate problem smaller in size than the matrix-dilation approach formerly proposed by the group of the first author. Here, the sparsity means that the constraint of a given problem has only a small number of nonzero terms when it is expressed as a polynomial in the uncertain parameters.This sparsity is extracted with a special graph called a rectilinear Steiner arborescence, based on which a reduced-size approximate problem is constructed. The accuracy of the approximation can be analyzed quantitatively. In particular, it is shown that the accuracy can be improved to any level by dividing the parameter region into small subregions.