Error Bounds for Linear Matrix Inequalities

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(ε ^{2⁻ᵈ}) \). The nonnegative integer d is the so-called degree of singularity of the linear matrix inequality, and ε denotes the amount of constraint violation in the iterate. For infeasible linear matrix inequalities, we show that the minimal norm of ε-approximate primal solutions is at least \( 1/O(ε ^{1/(2ᵈ-1)}) \), and the minimal norm of ε-approximate Farkas-type dual solutions is at most \( O(1/ ε ^{2ᵈ-1}) \). As an application of these error bounds, we show that for any bounded sequence of ε-approximate solutions to a semidefinite programming problem, the distance to the optimal solution set is at most \( O(ε ^{2⁻ᵏ}) \), where k is the degree of singularity of the optimal solution set.