Error Bounds for Linear Matrix Inequalities

Abstract

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 semidefinite 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.