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(\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.
Introduction
Linear matrix inequalities play an important role in system and control theory,
see the book by Boyd et al. [3]. Recently, considerable progress has been made
in optimization over linear matrix inequalities, i.e. semi-definite programming,
see [1, 6, 8, 9, 16, 19, 18, 23, 25] and the references cited therein.
We study the linear matrix inequality (LMI)
ae
means positive semi-definiteness, B is a given (real) symmetric
matrix and A is a linear subspace of symmetric matrices.
The LMI (1) is in conic form, see e.g. [17, 23]. Since we leave complete
freedom as to the formulation of A, it is in general not difficult to fit a given
LMI into conic form. Consider for instance a linear matrix inequality
are given symmetric matrices. This is a conic form LMI
and A is the span of fF g.
Recently developed interior point codes for semi-definite programming make
it possible to solve LMIs numerically. Such algorithms generate sequences of
increasingly good approximate solutions, provided that the LMI is solvable.
For a discussion of interior point methods for semi-definite programming, see
e.g. [8, 23]. A typical way to measure the quality of an approximate solution, is
by evaluating its constraint violation.
For instance, if we denote the smallest eigenvalue of an approximate solution
~
X), then we may say that ~
X violates the constraint 'X - 0' by an
amount of [\Gamma- min ( ~
X)]+ , where the operator [\Delta] + yields the positive part. In fact,
X)]+ is the distance, measured in the matrix 2-norm, of the approximate
solution ~
X to the cone of positive semi-definite matrices. The matrix 2-norm
is a convenient measure for the amount by which the positive semi-definiteness
constraint is violated, but other matrix norms can in principle be used as well.
Similarly, we say that ~
X violates the constraint 'X 2 B +A' by an amount
of dist( ~
denotes the distance function (for a given
norm). The total amount of constraint violation in ~
X, i.e.
is called the backward error of ~
X with respect to the LMI (1). The backward
error indicates how much we should perturb the data of the problem, such that
~
X is an exact solution to the perturbed problem.
However, the backward error does not (immediately) tell us the distance from
~
X to the solution set of the original LMI; this distance is called the forward error
of ~
X .
knowing any exact solution, there is no straightforward way to
estimate the forward error. For linear inequality and equation systems however,
the forward error and backward error are of the same order of magnitude, see
Hoffman [7]. The equivalence between forward and backward errors holds also
true for systems that are described by convex quadratic inequalities, if a Slater
condition holds, see Luo and Luo [12]. In these cases, we have a relation of the
which is called a Lipschitzian error bound. For systems of convex quadratic
inequalities without Slater's condition, an error bound of the form
was obtained by Wang and Pang [26]. They also showed that d -
where n is the dimension of the problem. Error bounds for systems with a
nonconvex quadratic inequality are given in Luo and Sturm [14], and references
cited therein.
An error bound of the form (3) is called a H-olderian error bound. A
H-olderian error bound has been demonstrated for analytic inequality and equation
systems, if the size of the approximate solutions is bounded by a fixed
constant, see Luo and Pang [13]. However, there are no known positive lower
bounds on the exponent fl, except in the linear and quadratic cases that are
mentioned above, or when a Slater condition holds [4], For a comprehensive
survey of error bounds, we refer to Pang [20].
Some issues on error bounds for LMIs and semi-definite programming were
recently addressed by Deng and Hu [4], Goldfarb and Scheinberg [5], Luo, Sturm
and Zhang [16] and Sturm and Zhang [24]. Deng and Hu [4] derived upper
bounds on the Lipschitz constant (or condition number) for LMIs, if Slater's
condition holds. Luo Sturm and Zhang [16] and Sturm and Zhang [24] prove
some Lipschitzian type error bounds for central solutions for semi-definite programs
under strict complementarity. Goldfarb and Scheinberg [5] prove Lipschitz
continuity of the optimal value function for semi-definite programs.
In this paper, we show for LMIs in n \Theta n matrices, that (3) holds for a certain
the so-called degree of singularity, provided that the size
of the approximate solutions is bounded. We interpret the degree of singularity
in the context of Ramana-type regularized duality. It is basically the number
of elementary regularizations that are needed to obtain a fully regularized dual.
Under Slater's constraint qualification, the irregularity level d is zero. (Notice
that this is also true for convex quadratic systems, see Wang and Pang [26].) The
degree of singularity of the optimal solution set of a semi-definite programming
problem is at most one, if strict complementarity holds. The concept of singularity
degrees thus embeds the Slater and strict complementarity conditions in
a hierarchy of singularity for LMIs.
This paper is organized as follows. In Section 2, we introduce the concept of
regularized backward errors, which is closely related to the concept of minimal
cones [2]. In this section, we also show that there is a close connection between
the regularized backward error and the forward error. We will then estimate
in Section 3 how the regularized backward error depends on the usual backward
error. In Section 4, we apply the error bound for LMIs to semi-definite
programming problems. The paper is concluded in Section 5.
Notation. Let S n\Thetan denote the space of n \Theta n real symmetric matrices.
The cone of all positive semi-definite matrices in S n\Thetan is denoted by S n\Thetan
we
. The interior of S n\Thetan
is the set of
positive definite matrices S n\Thetan
++ , and we write X - 0 if and only if X 2 S n\Thetan
++ .
We let N := n(n + 1)=2 denote the dimension of the real linear space S n\Thetan .
The standard inner product for two symmetric matrices X and Y is
tr XY . The matrix norm kXk 2 is the operator 2-norm that is associated with
the Euclidean norm for vectors, namely
For symmetric matrices, kXk 2 is the eigenvalue of X that has the largest absolute
value.
2 The regularized backward error
A denote the smallest linear subspace containing B +A, i.e.
We are naturally interested in the intersection of this linear subspace with the
cone of positive semi-definite matrices. It holds that
A " S n\Thetan
the above characterization is a special case of a duality theorem for convex
cones.
The general theorem states that given a linear subspace L and a convex cone
!+ g, it holds that
see Corollary 2 in Luo, Sturm and Zhang [15] and Corollary 2.2 in [23]. This
result generalizes a classical duality theorem of Gordon and Stiemke for linear
inequalities.
To see why (5) is a special case of (6), we must interpret S n\Thetan
as a convex
cone in ! N . This can be established by choosing an orthonormal basis of S n\Thetan ,
say an orthonormal set of symmetric matrices fS[1];
1)=2 is the dimension of S n\Thetan . We can then associate with any matrix
n\Thetan a coordinate vector x 2 ! N into this basis, and vice versa. Namely,
we let x
Due to the
orthonormality of the basis, we have y, for all matrices X;Y 2 S n\Thetan
with coordinate vectors x; y 2 ! N .
As a convention, we use upper-case symbols, like X and B, for symmetric
matrices, and we implicitly define the corresponding lower-case symbols, like x
and b, to be the associated coordinate vectors, as described above. Furthermore,
we use calligraphic letters, such as S n\Thetan
, to denote sets. With the established
one-to-one correspondence between S n\Thetan and ! N in mind, we do not only use
S n\Thetan
for the set of positive semi-definite matrices in S n\Thetan , but also for the set
of coordinate vectors of positive semi-definite matrices, which is a convex cone
in the Euclidean space ! N . We will also use such a convention for other sets of
symmetric matrices. In particular, we reformulate (4) as
where Img b ae ! N is the line of all multiples of b. The orthogonal complement
of -
A is
The all-zero matrix is obviously the only matrix that is both positive and
negative semi-definite, i.e. S n\Thetan
" \GammaS n\Thetan
f0g. Also, the cone of positive semi-definite
matrices is self-dual, i.e. (S n\Thetan
. Thus, taking
and
A ? in (6) yields (5).
Relation (5) states that if -
A and S n\Thetan
intersect only at the origin, then
there exists a positive definite matrix Z 2 -
A ? . Consider now a sequence of
increasingly accurate solutions fX(ffl)
notice that the parameter ffl measures the backward error in X(ffl). It follows
that since Z?(B + A), we must have jZ ffl O(ffl). Using the fact that
positive definite, this implies that O(ffl). The
above reasoning establishes the relation
A " S n\Thetan
which is an error bound for the case that -
A intersects the semi-definite cone
only at the origin.
Assume now that -
A " S n\Thetan
A " S n\Thetan
applying a basis transformation if necessary, we may assume without loss of
generality that we can partition X   as
Using this notation, we can partition an arbitrary matrix X 2 S n\Thetan as
U XN
A " S n\Thetan
suppose without loss of generality
that X   is of the form (9). Then it holds for all
A " S n\Thetan
and
Proof. Suppose to the contrary that XN is not the all-zero matrix, and let
\Theta 0 y T
be such that XN yN 6= 0. Then for any ff 2 !,
where we used the fact that X is positive semi-definite. Consequently, we have
for all ff ? 0 that
A " S n\Thetan
which contradicts the fact that by definition, X   is in the relative interior of
A " S n\Thetan
. We have now shown by contradiction that
positive semi-definite, it follows that also
A face of S n\Thetan
is by definition a cone of the form
n\Thetan
where Z is a given positive semi-definite matrix. In particular, if
then
n\Thetan
ae
oe
and X is in the relative interior of face(S n\Thetan
0). The facial structure of S n\Thetan
has been studied in detail by Lewis [11]
and Pataki [21].
A " S n\Thetan
suppose without loss of generality
that X   is of the form (9). Then
relint
S n\Thetan
I
Proof. The lemma holds trivially true if (B +A) " S n\Thetan
now
that there exists
A, there exists t 2 ! such
that X   \Gamma tB 2 A. However, for all ff ? 0 satisfying fft ? \Gamma1, we
S n\Thetan
I
where we used Lemma 1. This shows that
S n\Thetan
I
Using Lemma 1 once again, the lemma follows from the above relation. Q.E.D.
Due to the above result, the face
face
S n\Thetan
I
is sometimes called the minimal cone [2] or the regularized semi-definite cone [15]
for the affine space B +A.
The backward error of X(ffl) with respect to the regularized system
is naturally defined as
The following lemma states, among others, that if fX(ffl)
then the regularized backward error is of the same order as the forward error
A " S n\Thetan
suppose without loss of generality
that X   is of the form (9). If fX(ffl) is such that
for all ffl ? 0, then (B+A)"S n\Thetan
;. Moreover, there exists
such that
Proof. As is well known, the backward and forward error for a system of
linear equations are of the same order [7]. Therefore, the relations
imply that
This bound implies the existence of fY (ffl) 0g, such that
Using also the fact that X
B is positive definite, it follows that
with
Notice that
A, there must exist t 2 ! such that
be such that
and hence
dist
Under Slater's condition, i.e. if (B
Hoffman's error bound [7] for systems of linear inequalities and equations to
LMIs. Notice in particular that no boundedness assumptions are made, i.e. the
error bound holds globally over S n\Thetan . However, the lemma requires a scaling
which is not needed in case of linear inequalities and equations.
The following example shows that this scaling factor is essential in the case of
LMIs.
Example 1 Consider the LMI in S 2\Theta2 with
ae
oe
i.e. we want to find find x 11 and x 12 such that x 11 - jx 12 j 2 . This LMI obviously
has positive definite solutions (the identity matrix for instance). Therefore,
the regularized backward error is identical to the usual backward error. The
approximate solution
has backward error ffl ? 0. However, X(ffl)
if and only
if
y 22
which shows that the distance of X(ffl) to (B
is bounded from below
by a positive constant as ffl # 0. However, we have X(ffl)=(1+ ffl) 2 (B+A)"S 2\Theta2
which agrees with the statement of Lemma 3.
Below are more remarks on the regularized error bound of Lemma 3.
states that the mere existence of fX(ffl)
(12) for all ffl ? 0 implies that (B
even though X(ffl) is not
necessarily bounded for ffl # 0. In the case of weak infeasibility, i.e. if
dist(B +A;S n\Thetan
we can therefore conclude that if X(ffl) satisfies (7) then
lim inf
ffl#0
is a bounded sequence with
then also kX (k)
as follows from Lemma 1. Letting
it follows from Lemma 3 and the boundedness of the sequence fX
3 Regularization steps
In order to bound the regularized backward error (11) in terms of the original
backward error (2), we use a sequence of regularization steps.
In the preceding, we have partitioned n \Theta n matrices according to the structure
of X   , given by (9). In this section, we will also partition n \Theta n matrices
into blocks, but with respect to a possibly different eigenvector basis; the sizes of
the blocks can be different as well. We will denote the blocks by the subscripts
We will also encounter the dual cone of a face of S n\Thetan
face
S n\Thetan
I
ae -
oe
Obviously, we have
relint face
S n\Thetan
I
ae -
oe
In the following, we will allow the possibility that are X 22
are non-existent. For this case, we use the convention that kX 12
A be a linear subspace of S n\Thetan , and suppose that fX(ffl)
is such that
for all
S n\Thetan
I
It holds that
ffl Z 11 - 0 if and only if
S n\Thetan
I
only if
S n\Thetan
I
ffl For the remaining case that 0 6= Z 11 6- 0, let
\Theta

be an orthogonal
matrix such that Z 11
Proof. The first two cases, i.e. Z are immediate applications
of (6). It remains to consider the case that Z 11 is a nonzero but singular, positive
semi-definite matrix.
- ffl, there must exist Y (ffl), such that
for all ffl ? 0. This implies that Z?(X(ffl)+Y (ffl)) because Z 2 -
A ? , and therefore
Z
'-
where we used the Cauchy-Schwartz inequality. Recall now that
so that we further obtain
Z
Since Z 11 is positive semi-definite and - min (X(ffl)) - \Gammaffl, we have
where we used Z 11 in the first identity, and (15) in the last identity.
Recalling that Q T
easily follows from the above relation that
Finally, since - min (X(ffl)) - \Gammaffl, we know that X 11 (ffl) + fflI is positive semi-
definite, and hence
where we used (16). This completes the proof. Q.E.D.
For a given linear subspace -
A ' S n\Thetan , we define the level of singularity
by recursively applying the construction of Lemma 4. This procedure is
outlined below:
Procedure 1 Definition of the level of singularity of a linear subspace -
S n\Thetan .
Otherwise, proceed with Step 2.
be such that Z (0)
ae
\Theta

A
oe
A ?
S n\Thetan
I
If Z (d)
proceed with Step 4.
be such that Z (d)
I
Let
ae
\Theta -

A d
oe
return to Step 3.
In the above procedure, we start with the full dimensional cone S n\Thetan
, and in
the first iteration we determine a face of this cone. Next, we arrive at a face of
this face, and so on. We claim that this procedure finally arrives at the minimal
cone. To see this, notice that at any given step
above, we
perform a regularization step as described in Lemma 4. Recall from (5) that
A " S n\Thetan
f0g, and this case has already
been treated in Section 2. In any other case, we have Z (d( -
It is easily
seen from Lemma 4 that if X 2 -
A " S n\Thetan
This means that
all nonzeros of X must be contained in the (final) 11 block for -
A
. On the
other hand, since Z (d( -
in the above procedure, it follows from (6) that
there exists ~
A " S n\Thetan
such that ~
we just showed that X
A " S n\Thetan
, we must have
~
A " S n\Thetan
Hence, the face in the final iteration is the minimal
cone. For -
(9).
By applying a basis transformation if necessary, we may assume without loss
of generality that there is a (d( -
partition, such that
0:
Above, we used a Matlab-type 1 notation, thus means
denotes the block on the ith row and jth column in the (d( -
is symmetric, we only specified the upper
block triangular part of Z. The relation between the (d( -
partition in (18) and the 2 \Theta 2 partition in iteration
is that
The minimal cone is the set of matrices X for which
In iteration
of Procedure 1, we arrive at the face where
which indeed includes the minimal cone.
Remark that the 3rd row and column in the 3 \Theta 3 block form of (18) are
non-existent for
A), i.e. for
Based on Lemma 4, we can now estimate the regularized backward error.
A " S n\Thetan
loss of generality that X   is of the form (9). If
is such that for all
then
with
is the degree of singularity of -
A.
Proof. Applying Lemma 4 in iteration of Procedure 1, we have that
1 MATLAB is a registered trademark of The MathWorks, Inc.
where we used X ffl as a synonym for X(ffl). Suppose now that in iteration d 2
where
It then follows from Lemma 4 that (19) also holds for
By induction. we obtain that (19) holds for
(ffl), the lemma follows. Q.E.D.
We arrive now at the main result of this paper, namely an error bound for
LMIs.
Theorem 1 Let -
is such that kX(ffl)k is
bounded and
then
Proof. For the case that d( -
the theorem follows by combining Lemma 3
with Lemma 5. If
there are two cases, either -
A " S n\Thetan
A " S n\Thetan
In the former case, we have hence the error
bound holds, see Section 2. In the latter case, we have that X
the error bound follows from Lemma 3. Q.E.D.
An LMI is said to be weakly infeasible if
1. there is no solution to the LMI, i.e. (B +A) " S n\Thetan
2. dist(B +A;S n\Thetan
For weakly infeasible LMIs, there exist approximate solutions with arbitrarily
small constraint violations. However, the following theorem provides a lower
bound on the size of such approximate solutions to weakly infeasible LMIs.
Theorem 2 Let -
and suppose that
is such that
small enough, we have X(ffl) 6= 0
Proof. Suppose to the contrary that there exists a sequence ffl 1
Applying Lemma 5, it follows that
Together with Lemma 3, we obtain that (B +A) " S n\Thetan
Q.E.D.
There is an extension of Farkas' lemma from linear inequalities to convex
cones, which states that
where K ae S n\Thetan is a convex cone, and K   is the associated dual cone. See
e.g. Lemma 2.5 in [23]. If dist(B +A;S n\Thetan
we say that the LMI is
strongly infeasible. Relation (20) states that strong infeasibility can be demonstrated
by a matrix Z 2 A ? " S n\Thetan
0, and such Z is called a dual
improving direction.
For weakly infeasible LMIs, infeasibility cannot be demonstrated by a dual
improving direction. However, an LMI is infeasible if and only if there exist
approximate dual improving directions with arbitrarily small constraint viola-
tions. See e.g. Lemma 2.6 in [23]. The next theorem gives an upper bound for
the minimal norm of such approximate dual improving directions in the case of
infeasibility.
Theorem 3 Let -
there exist
0g such that for all holds that
and
Proof. Let X   2 relint ( -
A " S n\Thetan
suppose without loss of generality
that X   is of the form (9). Using the same 2 \Theta 2 partition as in (9), it follows
from Lemma 3 that
dist
S n\Thetan
I
-"
0:
Applying (20), it thus follows that there exists a matrix Y (0) such that
S n\Thetan
I
Partitioning Y (0) , we have
Y (0)
U
We shall now construct fY
A)g such that
Y
1. Remark from (21)-(22) that (23) holds for
construct Y (k) for k 2
in such a way that it satisfies (23),
provided that Y (k\Gamma1) satisfies (23). We can then use induction.
Let
immediately obtain from (23) that
irrespective of t. Furthermore, since Y
positive semi-definite if and only if the Schur-complement
is positive semi-definite. From (18) and the definition of Y t , we have
and hence
positive semi-definite if we choose t as
where we used that kY (k\Gamma1)
Setting Y
The theorem follows by letting
We remark from the proof of Theorem 3 that the matrices Y (0) and Z (k) ,
finite certificate of the infeasibility of the LMI.
Together, these matrices form essentially a solution to the regularized Farkas-
type dual of Ramana [22], see also [10, 15]. Thus, the degree of singularity is
the minimal number of layers that are needed in the perfect dual of Ramana.
As discussed in the introduction, it is easy to calculate the backward error of
an approximate solution. However, the error bound for the forward error of an
LMI, as given in Theorem 1, does not only involve the backward error, but also
the degree of singularity. We will now provide some easily computable upper
bounds on the degree of singularity.
Lemma 6 For the degree of singularity
of a linear subspace -
A ' S n\Thetan ,
it holds that
A ? g:
Proof. If
A " S n\Thetan
by definition of
A). For this case,
we have defined the (d( -
partition (18), where each of
the
diagonal blocks is at least of size 1 \Theta 1. Thus,
Furthermore, Lemma 4 defines a matrix Z
A ? , for each regularization
and it is easily verified that these matrices are
mutually independent. Therefore,
Finally, using the (d( -
partition (18), we claim that
there exists X
A with
Namely, if such X (k) does not exist, then by (6), there must exist \DeltaZ 2 -
A ?
such that
and this contradicts the fact that Z (d( -
of maximal
rank, see its definition in Lemma 4. Again, it is easy to see that the matrices
A), are mutually independent, and hence
A. Q.E.D.
The bounds of Theorem 1 and Theorem 2 quickly become inattractive as
the singularity degree increases. However, the next two examples show that
these bounds can be tight. This means that problems with a large degree of
singularity can be very hard to solve numerically.
Example 2 Consider the LMI
Due to the restriction 'X 22 = 0' and the positive semi-definiteness, we have
which further implies
and inductive argument, we have X
we can construct a sequence fX(ffl) j ffl ? 0g with a constraint violation ffl, but
, viz.
Notice that 'X 22 = 0' is the only constraint that is violated by X(ffl).
To see how unfortunate this example is, consider a backward error
Then, already for
any solution -
X of the LMI.
Example 3 Extending Example 2 with the restriction 'X we obtain a
(weakly) infeasible LMI:
However, we may construct a sequence fX(ffl) violation
ffl and Namely, we let
This example shows that (in)feasibility can be hard to detect. Namely, for
which is not
unusually large; yet, the problem is infeasible.
4 Application to semi-definite programming
bounds for LMIs can be applied to semi-definite optimization models as
well. A standard form semi-definite program is
where B and C are given symmetric matrices. Associated with this optimization
problem is a dual problem, viz.
(D)
An obvious property of the primal-dual pair (P) and (D) is the weak duality
relation. Namely, if X 2 (B +A) " S n\Thetan
Clearly, if X ffl must be optimal solutions to (P) and (D)
respectively; we say then that (X; Z) is a pair of complementary solutions. In
general, such a pair may not exist, even if both (P) and (D) are feasible. (We say
that (P) is feasible if (B+A)"S n\Thetan
and (D) is feasible if (C+A ? )"S n\Thetan
;.) A sufficient condition for the existence of a complementary solution pair is
that (P) and (D) are feasible and satisfy the primal-dual Slater condition, in
which case
Based on (25), we can formulate the set of complementary solutions as the
In principle, we can apply our error bound results for LMIs directly to the above
system. But, tighter bounds can be obtained by exploring its special structure.
Consider a bounded trajectory of approximate primal and dual solutions
C) be a complementary solution pair, i.e.
Such a pair must exist, since in particular any cluster point of f(X(ffl); Z(ffl) j
ffl ? 0g for ffl # 0 is a complementary solution pair. Notice that B
and similarly C +A
, from which we easily derive that
for feasible solutions X and Z, and
for (X(ffl); Z(ffl)) satisfying (26). This means that X(ffl) has an O(ffl) constraint
violation with respect to the LMI
Notice that (27) describes the set of optimal solutions to (P). Letting
A := Img
the Theorems 1 and 2 are applicable to the LMI (27) and hence to the semi-definite
program (P). Specifically, given a bounded trajectory fX(ffl); Z(ffl)
0g satisfying (26), we know that the distance from X(ffl) to the set of optimal
solutions to (P) is O(ffl 2 \Gammad( -
is the degree of singularity of the
linear subspace defined in (28).
0, we can move the parentheses in definition (28) to get
from which we get
Noticing the primal-dual symmetry, we conclude that the distance from Z(ffl)
to the set of optimal solutions to (D) is O(ffl 2 \Gammad( -
A ? ) is the degree
of singularity of -
A ? .
Concluding remarks
Theorem 1 provides a H-olderian error bound for LMIs. For weakly infeasible
LMIs, we have derived relations between backward errors and the size of approximate
solutions, see Theorems 2 and 3. In Section 4, we applied the error
bound of Theorem 1 to semi-definite programming problems (SDPs). If the
SDP has a strictly complementary solution, then its degree of singularity can
be at most 1, and the bound becomes
backward error):
For this case, Luo, Sturm and Zhang [16] obtained a Lipschitzian error bound if
the approximate solutions (X(ffl); Z(ffl)) are restricted to the central path. The
sensitivity of central solutions with respect to perturbations in the right-hand
side was studied by Sturm and Zhang [24].

Acknowledgment

. Tom Luo's comments on an earlier version of this paper
have resulted in substantial improvements in the presentation.



--R


Regularizing the abstract convex program.
Linear matrix inequalities in system and control theory
Computable error bounds for semidefinite program- ming
On parametric semidefinite programming.
An interior-point method for semidefinite programming
On approximate solutions of systems of linear inequalities.
Interior Point Methods for Semidefinite Programming.

Perfect duality in semi-infinite and semidefinite programming

Extensions of Hoffman's error bound to polynomial systems.
bounds for analytic systems and their applications.
bounds for quadratic systems.
Duality results for conic convex programming.
Superlinear convergence of a symmetric primal-dual path following algorithm for semidefinite programming
Interior point polynomial methods in convex programming


bounds in mathematical programming.
On the rank of extreme matrices in semidefinite programs and the multiplicity of optimal eigenvalues.
An exact duality theory for semidefinite programming and its complexity implications.

On sensitivity of central solutions in semidefinite programming.
programming.
Global error bounds for convex quadratic inequality systems.
--TR

--CTR
Dominique Az , Jean-Baptiste Hiriart-Urruty, Optimal Hoffman-Type Estimates in Eigenvalue and Semidefinite Inequality Constraints, Journal of Global Optimization, v.24 n.2, p.133-147, October 2002
regularized duality;error bounds;linear matrix inequality;semidefinite programming