Error bounds for linear matrix inequalities

Jos F. Sturm

For iterative sequences that converge to the solution set of a linear matrix inequality, we show that the distance of the iterates to the solution set is at most \( O(\epsilon ^{2^{-d}}) \). The nonnegative integer $d$ is the so--called degree of singularity of the linear matrix inequality, and $\epsilon $ denotes the amount of constraint violation in the iterate. For infeasible linear matrix inequalities, we show that the minimal norm of $\epsilon $--approximate primal solutions is at least \( 1/O(\epsilon ^{1/(2^{d}-1)}) \), and the minimal norm of $\epsilon $--approximate Farkas--type dual solutions is at most \( O(1/ \epsilon ^{2^{d}-1}) \). As an application of these error bounds, we show that for any bounded sequence of $\epsilon $--approximate solutions to a semi-definite programming problem, the distance to the optimal solution set is at most \( O(\epsilon ^{2^{-k}}) \), where $k$ is the degree of singularity of the optimal solution set. Keywords: semi-definite programming, error bounds, linear matrix inequality, regularized duality.

Comunications Res. Lab., McMaster Univ, Hamilton, Ont, canada. May 1998.