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

Contact: sturm@cauchy.crl.mcmaster.ca