Global Error Bounds for Convex Conic Problems.
This paper aims at deriving and proving some Lipschitzian-type error bounds for convex conic problems in a simple way. First, it is shown that if the recession directions satisfy Slater's condition, then a global Lipschitzian-type error bound holds. Alternatively, if the feasible region is bounded, then the ordinary Slater condition guarantees a global Lipschitzian-type error bound. These can be considered as generalizations of previously known results for inequality systems, which also follow from general results by Bauschke and Borwein in [ SIAM Review, 38 (1996), pp. 367--426] and Bauschke, Borwein, and Li in a 1997 report. However, the proofs in the current paper are considerably simpler. Some of the results are generalized to the intersection of multiple shifted cones (with different shifts). Under Slater's condition alone, a global Lipschitzian-type error bound does not hold. It is shown, however, that such an error bound holds for a specific conic region. For linear systems we establish that the sharp constant involved in Hoffman's error bound is nothing but the condition number for linear programming as used by Vavasis and Ye in [ Math. Programming, 74 (1996), pp. 79--120].
Introduction
In optimization theory it is often desirable to measure the distance to the solution set from a certain
given point. In general, this distance can be difficult to assess, since one may not have a complete
knowledge about the solution set. However, if the form of the solution set is explicitly given, then
in some cases it is possible to estimate the distance to the solution set by the so-called constraint
violation which is computable. This kind of estimation is termed error bound relation. The first
such result was obtained by Hoffman [7] for systems of linear equalities and inequalities. We shall
discuss Hoffman's error bound in the paper too. A recent extensive survey on various types of error
bound results can be found in Pang [15].
Most papers discussing error bound results assume that the solution set is given by equations and
inequalities, e.g.
For a given point x the amount of constraint violation can be measured as the following quantity
with the notation (y)
A measure for constraint violation is similar to a penalty function in the sense that it takes positive
value for points outside the set, and zero otherwise. Note that a measure for constraint violation
should be easy computable, such as the case for the above defined function v(x). Hoffman's
lemma [7] states that if S 6= ;, and f i and g j are all affine linear functions, then there is a positive
dist (x; S) -v(x) (1.1)
for all x 2 ! n . This means that the distance to S is of the same magnitude as v(x). Such a relation
is known as a Lipschitzian type error bound.
In the case that f i and g j are not linear, the above inequality (1.1) does not hold in general. Early
results concerning nonlinear functions are due to Robinson [17] and Mangasarian [13]. Robinson [17]
showed that for inequality systems if all functions are convex and differentiable, S is bounded and
the Slater condition holds, i.e. there is a - x such that g j (-x) ! 0 for all j, then relation (1.1) holds.
Mangasarian [13] removed the assumption that S is bounded by assuming an additional asymptotic
constraint qualification condition, which however can be difficult to verify in general.
In this paper we consider the following convex conic set:
is a subspace of ! n and K ' ! n is a closed convex cone. Polynomial-time
interior-point algorithms for solving convex optimization problems with convex conic feasible set
were introduced in a systematic manner by Nesterov and Nemirovskii [14]. It turns out that
many important classes of optimization problems, such as linear programming and semidefinite
programming, can be cast in this form. The focus of this paper is to discuss how error bound
type relation can be established for such problems. Throughout this paper we make the following
assumption:
Assumption 1 F 6= ;.
The organization of the paper is as follows. In the next section we prove that with a proper definition
of constraint violation a Lipschitzian type error bound (1.1) can be established for general convex
conic problems, under various conditions on the relations between L and K, including Slater type
conditions. In Section 3 we discuss a link between the constant in Hoffman's error bound and the
so-called condition number for linear programming. Finally, we conclude the paper in Section 4.
We use the following notation in this paper. Matrices are denoted by capital letters, e.g. X. For
indicates the maximum eigenvalue of X, and - min (X) the minimum
eigenvalue of X. We denote n-dimensional Euclidean space by ! n and its nonnegative quadrant
by
. The space of all symmetric n by n matrices is denoted by S n\Thetan and the cone of all
symmetric positive semidefinite n by n matrices by S n\Thetan
. Vector e represents a vector of all ones
with appropriate dimension. For a vector we use the capitalized letter V to denote the
diagonal matrix which takes v as its diagonal elements. For two vectors
as the component-wise Hadamard product. We use the Euclidean norm for vectors
and the spectral norm for matrices. A vector a - 0 means that each component of a is nonnegative,
and X - 0 indicates that X is positive semidefinite.
systems
Consider the convex conic set (1.2). For convenience we further assume that K is a pointed and
solid cone, i.e. K "
The dual of K is
Since K is pointed and solid, K   too is a closed, convex, pointed and solid cone.
An immediate next question is: How can we define a constraint violation function for F? For this
purpose we note the following lemma due to Moreau (see Theorem 31.5 in [18]).
Lemma 2.1 For any x 2 ! n there is a unique x p 2 K and x d 2 K   such that
In fact, x p is simply the projection of x onto K and kx d k measures the distance from x to K. A
natural definition for the constraint violation for F is now in order:
Definition 2.1 For any x 2 ! n define
dist
as the constraint violation function for F .
It is readily seen that v(x;
It is, however, not immediately clear how the function v(x; F) can be computed. Below we shall
see some examples in which this function is explicitly derived. First we consider the case
, the nonnegative quadrant of ! n . Clearly,
which is exactly the usual definition of the violation for nonnegativity constraints.
Another example is
, the cone of n by n symmetric positive semidefinite matrices.
Consider a given n by n symmetric matrix X. Following Lemma 2.1 we know that there is unique
positive semidefinite matrices X p and X d such that
and X d can be computed as follows. Let an orthonormal matrix and   is a
diagonal matrix with eigenvalues of X as its components. Splitting
\Gamma denote the nonnegative and nonpositive parts of   respectively, it follows that X
denotes the
minimum eigenvalue of X.
Finally, we consider another popular convex cone: the second order cone K defined as
It can be shown that in this case
2:
In general, Definition 2.1 is only related to the geometry of the object under consideration.
Consider now an arbitrary point z Assume that z 62 F . The following problem yields a
unique point in F with the shortest Euclidean distance to z:
subject to x
Let this optimal solution be -
x. The Karush-Kuhn-Tucker optimality condition for (Proj) is given
as follows:
Hence,
where the first inequality follows from the fact that z p 2 K and - 2 K   .
Let the projection of z onto the affine subspace b + L be z l . Then,
dist
Substitute this relation into (2.2) we obtain
(dist (z; dist
In Section 3 we shall discuss how to further bound the errors when K is a polyhedral cone, which is
the situation when the original Hoffman lemma applies. In the rest of this section we assume that
K is a general convex cone. In addition to this we assume that the Slater condition is satisfied, i.e.
Assumption
The following lemma is well-known; see e.g., Duffin [5], Borwein and Wolkowicz [2], Luo, Sturm
and Zhang [11], Nesterov and Nemirovskii [14] and Sturm [21]. For completeness we provide here
a short proof.
Lemma 2.2 Suppose that Assumption 2 holds. Then, for any y 2 must
follow that b T y ? 0.
Proof. Suppose, for the sake of deriving a contradiction, that there is y 6= 0 such that y 2
Consider the hyperplane
For any x while for any x 2 K, since y 2 K   we have y T x - 0.
This means that H y separates b +L and K, yielding a contradiction to the fact that b +L intersects
with the interior of K.For fixed - x we consider again the system (KKT) in terms of - and -. After some re-arrangements
this yields 8
which is a closed convex cone as well.
Note that -
case and is omitted in our proof. In many applications, 0 62 L and so
We shall mention another easy case, i.e. - x lies in the interior of K then -
f0g. In this case
x, and therefore
dist (z; F) - dist
due to (2.3). In what remains we shall only concentrate on the situation when - x 62 int K.
Remark that for -
K   is known as a face of K   .
The condition (2.4) is equivalent to
Lemma 2.3 If Assumption 2 holds then
Proof. Suppose for contradiction that there is y
K   . This means that
However, -
which is impossible due to Lemma 2.2. 2
Now we define the minimum angle between L ? and -
K   as
Note that both L ? and -
K   are closed cones. According to Lemma 2.3, it follows that
for any -
In order to pursue our analysis further, one of the following two mutually exclusive cases will be
considered.
Assumption 3 The set
Assumption
Let us first consider the situation when Assumption 3 holds. In that case we know that there exists
such that for any -
we always have
Now take -
K   . Let the projection of 0 onto -
-s
s
s
s

Figure

and the cone -
K   .
Let the angle between - and - \Gamma p be '. Clearly, ' -=2. Moreover,
Denote
We are now in a position to prove the following error bound result.
Theorem 2.1 If Assumption 2 and Assumption 3 hold then
dist (z; F) -v(z; F)
for all z
Proof. By (2.5) we have
dist (z; F)= sin ' -dist (z; F):
Using the first equation in (2.4) we also have
')dist (z; -dist (z; F):
Recall relation (2.3). By the above estimations on k-k and k-k, it follows from (2.3) that
(dist (z; F)) 2 -dist (z; F)(kz d k dist
and consequently
dist (z; F) -v(z; F):In the other situation, namely if Assumption 4 holds, then a similar result can be shown.
Theorem 2.2 If Assumption 4 holds, then for any b 2 ! n we must have (b
Moreover, there is a constant - ? 0, independent of b, such that
dist (z; F) -v(z; F)
Proof. First we show that (b Suppose otherwise that there is b with
(b
Then, there will be a hyperplane separating b +L and K, say with such that
Since K is a closed cone, the above separation implies that y T x - 0 for all x 2 K and
Moreover, we also have y T This is in contradiction with the condition
Compared with Lemma 2.3, we have now a stronger relation: f0g. This means that
the proof of Theorem 2.1 can remain exactly the same, except that now ' ? 0 can be taken as the
minimum angle between L ? and K   which is independent of b. 2
We remark that both Theorem 2.1 and Theorem 2.2 easily extend to the case when L is a closed
cone.
Theorem 2.3 Suppose that K 1 is a closed convex cone and K 2 is a closed, convex, solid and pointed
cone. Furthermore, suppose that (b compact. Then there
is a constant - ? 0 such that
dist (z; F) -(dist (z; b dist (z; K 2
for all z
Proof. We follow similar lines as in the proof of Theorem 2.1. Consider
subject to x 2 b +K 1
Let the optimal solution be -
x. The Karush-Kuhn-Tucker optimality condition yields:
Let
and
Both -
are closed convex cones.
Now we claim that
Suppose such is not the case. Then, one should be able to find - 6= 0 satisfying
Hence, b T This implies
that contradicting the Slater condition.
are closed convex cones and, moreover, -
2 is a solid pointed cone, we derive
from (2.6) that -
2 can be strictly separated from \Gamma -
1 . Due to compactness of F we may let ' be
a positive lower bound on the minimum angle between this separating hyperplane and -
2 . Then
we have
and consequently
dist (z; b +K 1 )k- dist (z; K 2
dist (z; K 2
The desired result thus follows. 2
Similarly, we have the following result, the proof of which is pretty much the same as that of
Theorems 2.2 and 2.3 and is omitted here.
Theorem 2.4 Suppose that K 1 is a closed convex cone and K 2 is a closed, convex, solid and pointed
cone. Furthermore, suppose that here is a constant - ? 0,
independent of b, such that
dist (z; F) -(dist (z; b dist (z; K 2
for all z
When more than two cones are concerned, a similar result holds under Slater's condition. First we
note the following lemma, see e.g. [11].
Lemma 2.4 Let K be a convex cone and int K 6= ;. Then, x 2 int K if and only if for any
holds that
Theorem 2.5 Let K i be convex cones, m. Suppose that
Then, there is - ? 0 such that
dist
dist (z; K i
for any z 2 ! n .
Proof. Consider
subject to x 2 K
Hence, for the optimal solution -
x the KKT condition yields
with
Let
By Lemma 2.4 there exists
m.
Let
with z ip 2 K i , z id 2 K
ip z due to Lemma 2.1. Moreover, kz id dist (z; K i m.
Therefore,
z
z T
kz id kk- i k:
On the other hand, since
dist (z; K i
and so by letting
it follows that
dist
dist (z; K i ):Theorem 2.1 can be viewed as an analogue to Robinson's result for convex inequality systems. In
the form of convex inequality systems, Theorem 2.2 can be found in Hu and Wang [9] and Deng
and Hu [3]. In particular, Deng and Hu [3] investigated the case when K is the cone of positive
semidefinite matrices. This case is known as linear matrix inequalities (LMIs for short). In its
optimization version it is also called semidefinite programming and has received intensive research
attention recently. Sturm [20] mainly investigated error bounds for LMIs in the absence of Slater's
condition. In fact, in the context of LMIs, both Theorem 2.1 and Theorem 2.2 also follow from the
analysis in [20]. Moreover, an example was given in Sturm [20] showing that Assumption 2 alone
cannot guarantee a global Lipschitzian type error bound even for LMIs. Such an error bound is
only possible when an additional scaling factor is present.
Below we shall discuss how to derive some conditioned error bound relation for the convex conic
problem (1.2) under Assumption 2, without assuming Assumption 3 and Assumption 4.
In this situation the recession cone L " K must be non-empty and it is not contained in the interior
of K.
For a fixed positive angle consider the following cone
the projection of x onto L and the cone L " K has an angle at least -=2
Theorem 2.6 Suppose that Assumption 2 holds. There exists a constant - ? 0 such that
dist (z; F) -v(z; F):
for all z 2 C.
Proof. Observe that if -
x is the projection of z on F , then it must also be the projection of z
on F for any y 2 L ? . This can be seen as follows. The fact that - x is the projection
of z is equivalent to the existence of - 2 L ? and - 2 K   such that
(See also (2.1)). Now if z is changed to z y, then we need only to change - to -
satisfy the same set of KKT conditions.
Remark also that to prove the theorem it is sufficient to show that, for any z 2 C, its projection
onto F is contained in a compact set.
Suppose that the theorem is false and that there is a sequence fz :::g, such that the
corresponding projection on F , f-x unbounded. Due to the above remarks
we have made, we need only to consider the projection of z (k) onto the subspace L. Without loss
of generality, assume that z
For sufficiently large k we have
where the first inequality is because -
x (k) must be pointing towards the cone of recession directions
and the last inequality is due to the fact that k-x (k) k ! 1. This contradicts to -
x being
the closest point in F to z (k) .For any given point z C. The
following relation is immediate.
Lemma 2.5 dist (z; F) - dist (z
Proof. Let the projection of z 2 onto F be - x 2 . Then,
dist (z; F) -
where we used the fact that z 1 2 L " K and so -
2.5 and Theorem 2.6 we have
Theorem 2.7 Suppose that Assumption 2 holds. Then
dist (z; F) -v(z
for all z
3 Hoffman's error bound and the condition number
In this section we shall discuss error bounds for the linear system fx j A T x - bg with A 2 ! m\Thetan and
m. This is the setting for which Hoffman's error bound result applies ([7]). Our purpose
is to see how the constant in Hoffman's bound is related to other known quantities for the linear
system. Previous results on the constant of Hoffman's bound can be found, e.g., in [12, 1, 6, 10].
By introducing a slack confine ourselves to the range space of A T , i.e.
Accordingly,
.
For a given z
. Let
which minimizes the distance
to s(z).
Let
ng n K:
Then, for this given s(-x) - 0 we can rewrite (2.1) as
A J -
As (3.1) is a necessary condition for optimality, it is certain that (3.1) is feasible. What remains to
be analyzed is the size of the solution. A key ingredient in our analysis is the following lemma.
Lemma 3.1 Suppose that A has full row rank. Then,
diagonal and D -
Lemma 3.1 was first shown by Dikin [4] and was used in his convergence analysis for affine scaling
methods. Among others, Stewart [19] and Todd [23] rediscovered this result later.
The meaning of Lemma 3.1 can be interpreted as follows. It is well known that
0g and are orthocomplements to each other. Obviously, for
a given positive diagonal matrix D, Null(A) can only intersect with at the origin,
hence there must be a positive angle between them. Lemma 3.1 further states that the minimum
angle between Null(A) and uniformly bounded from below by a positive constant
which is independent of D.
To understand this fact we may consider the following example. Let
simply the line x 1 For a given positive diagonal matrix D, contained
in the first and the third quadrants. The angle between these two subspaces never exceeds -=4.
An important property of the constant -(A) is that it reflects an intrinsic, geometric relationship
of the spaces. Vavasis and Ye [24] used this constant -(A) as a measure of complexity for solving
the related linear programming problem. Their results showed that, in a real-number computation
model, linear program is solvable in polynomial-time, in terms of total number of basic operations,
with respect to the dimension n and the complexity measure log -(A). For problems with integral
input data, this result yields the usual polynomiality complexity result for linear programs in terms
of the input-length.
Holder, Sturm and Zhang [8] showed that -(A) plays an important role in sensitivity analysis
for linear programming. Furthermore, Sturm and Zhang [22] extended some of the results in [8]
to semidefinite programming. It is known however, that Lemma 3.1 cannot extend to general
semidefinite programming for arbitrary invariant scaling of the cone S n\Thetan
Fortunately, in analyzing (3.1) we need only to deal with a polyhedral cone. To see how condition
number -(A) can play a role in error bound analysis, we need to introduce a number of technical
lemmas.
First we note the following equivalent definition of -(A) for arbitrary matrix A due to Vavasis and
Ye [24].
Lemma 3.2 It holds that
kck
positive diagonalg:
For our analysis it is important to know the size of a solution for a linear system. To this end,
we note the following two lemmas. Remark that Renegar [16] studied similar problems in a quite
general framework using a quantity called distance to ill-posedness.
Lemma 3.3 Suppose that A has full row rank. Further assume that fx j
Then, there is a solution -
x in 0g such that
k-xk -(A)kbk:
Proof. Consider a linear program
subject to
and its dual
(D) maximize b T y
subject to A T y
Both (P) and (D) satisfy Slater's condition. Therefore their respective analytic central paths
satisfying the following relation:
x(-)s(-e:
Multiplying the second equation in (3.2) with X(-), the diagonal matrix with x(-) as its diagonal
components, and applying the first equation in (3.2) we obtain
e:
Substituting this into the second equation and finally using the third relation in (3.2) we have
Now we can apply Lemma 3.1 to obtain
The lemma is proven. 2
Next we shall extend this result to the case when Slater's condition is no longer assumed.
Lemma 3.4 Suppose that A has full row rank. Further assume that fx j
Then, there is a solution -
x in 0g such that
k-xk -(A)kbk:
Proof. Let Consider a perturbed set
Clearly, F ffi contains an interior point and therefore Lemma 3.3 can be invoked. Let x
The set fx be a cluster point of x ffi as
and
shall compare the condition number of A and that of its submatrices.
Proof. By Lemma 3.2,
kck
positive diagonalg:
partitioned in accordance with
For fixed c 1 6= 0 and fixed positive diagonal matrix D 1 . Let c positive
diagonal and D 2 ! 0. Clearly, the set of solutions minimizing kD 1=2 converges to the
set of solutions minimizing kD 1=2
)k. For given c and D let y(c; D) be a maximum norm
solution among solutions which minimize kD 1=2 similarly. It follows
that
lim sup
As a consequence,
and so the lemma is proven. 2
Applying Lemmas 3.4 and 3.5 to (3.1) we have
Finally we shall give a bound on the constant in Hoffman's error bound for linear systems.
Theorem 3.1 Suppose that and A has full row rank. It holds that
dist (z; F) -(A)(cond(AA T
for any z 2
Proof. Using (3.1) and (3.3),
By (2.3), on one hand we have
On the other hand,
Combining these two inequalities, the desired result follows. 2
Conclusions
In this paper we discuss error bounds for sets in convex conic form. The notion of constraint
violation is extended to this class of problems. For a number of applications the measure of
constraint violation is easy computable. We show that under Slater's condition, and additionally,
if either the feasible set is bounded or the recession directions satisfy the Slater's condition, then
there is a global Lipschitzian type error bound for general convex conic problems. These results
can be generalized to the intersection of multiple convex cones, or intersection of two shifted convex
cones, one of them being pointed and solid. If only Slater's condition is satisfied without additional
assumptions on the feasible region, then a global error bound is impossible as shown by Sturm [20].
In this case, one may still identify a region in which Lipschitzian type error bound holds. Finally,
we discuss the bounds in Hoffman's lemma for linear systems. It is shown that such a bound is
linked closely with the condition number for linear programming as investigated by Vavasis and
Ye [24].

Acknowledgement

I would like to thank Jos Sturm for pointing out an error in an earlier version
of the paper.



--R

The distance to a polyhedron
Characterizations of optimality for the abstract convex program with finite dimensional range
Computable error bounds for semidefinite programming
Iterative solution of problems of linear and quadratic programming
Linear Inequalities and Related Systems
Approximations to solutions to systems of linear inequalities
On approximate solutions of systems of linear inequalities
sensitivity analysis and parametric programming
On approximate solutions of infinite systems of linear inequalities
The sharp Lipschitz constants for feasible and optimal solutions of a perturbed linear program
Duality results for conic convex programming
A condition number of linear inequalities and equalities
A condition number for differentiable convex inequalities

bounds in mathematical programming
Some perturbation theory for linear programming
An application of error bounds for convex programming in a linear space
Convex Analysis
On scaled projections and pseudoinverses
bounds for linear matrix inequalities

On sensitivity of central solutions in semidefinite programming
A Dantzig-Wolfe-like variant of Karmarkar's interior-point linear programming algorithm
A primal-dual interior point method whose running time depends only on the constraint matrix
--TR
convex conic problems;error bound;condition number