Verifying exactness of relaxations for robust semi-definite programs by solving polynomial systems
The general robust semidefinite programming (SDP) problem addressed in this paper covers a multitude of robust optimization problems arising in various fields of engineering (signal processing, systems and control, structural optimization). The linear matrix inequality (LMI) techniques are suitable for solve such challenging problems. The typical form of an SDP problem is to minimize, for a given vector and some Hermitian matrices (satisfying a linear inequality), a functional over the entire \(n\)-dimensional real space. The matrices involved depend on a parameter. When the parameter is considered as a random variable, the family of LMI constraints is sampled on a finite grid of parameter values, at the risk of possibly missing crucial parameter values. The question arises: for what set of parameter values, the optimal value of the genuine robust SDP problem coincides with its sampled version? Relaxations are constructed which guarantee that the constraint is robustly feasible. The authors discuss two different approximations of the robust SDP that lead to upper and lower bounds of the genuine optimal value. Also a condition for verifying whether a computed relaxation is exact, is derived. Another problem in connection with the exactness test discussed by the authors is the problem of finding all common zeros for given polynomials in many variables. Two algorithms are proposed in this case. The theoretical presentation is illustrated by one performed numerical example.
scientific article; zbMATH DE number 5349149