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: [email protected]