SOME CHARACTERIZATIONS AND PROPERTIES OF THE “DISTANCE TO ILL-POSEDNESS” AND

THE CONDITION MEASURE OF A CONIC LINEAR SYSTEM ^{1}

Robert M. Freund^{2} M.I.T.

Jorge R. Vera^{3} University of Chile and CORE, Catholic University of Louvain

October, 1995

Abstract

A conic linear system is a system of the form

P : find x that solves b − Ax ∈ C_{Y} , x ∈ C_{X},

where C_{X} and C_{Y} are closed convex cones, and the data for the system is d = (A, b). This system is“well-posed” to the extent that (small) changes in the data (A, b) do not alter the status of the system (the system remains solvable or not). Intuitively, the more well-posed the system is, the easier it should be to solve the system or to demonstrate its infeasibility via a theorem of the alternative. Renegar defined the “distance to ill-posedness,” ρ(d), to be the smallest distance of the data d = (A, b) to other data d̄= (Ā, b̄) for which the system P is “ill=posed,” i.e., d̄= (Ā, b̄) is in the intersection of the closure of feasible and infeasible instances d′ = (A′, b′) of P. Renegar also defined the “condition measure” of the data instance d as C(d) \underline{\underline{Δ}}∥d∥/ρ(d), and showed that this measure is a natural extension of the familiar condition measure associated with systems of linear equation. This study presents two categories of results related to ρ(d), the distance to ill-posedness, and C(d), the condition measure of d. The first category of results involves the approximation of ρ(d) as the optimal value of certain mathematical programs. We present ten different mathematical programs each of whose optimal values provides an approximation of ρ(d) to within certain constant factors, depending on whether P is feasible or not. The second category of results involves the existence of certain inscribed and intersecting balls involving the feasible region of P or the feasible region of its alternative system, in the spirit of the ellipsoid algorithm. These results roughly state that the feasible region of P (or its alternative system when P is not feasible) will contain a ball of radius r that is itself no more than a distance R from the origin, where the ratio R/r satisfies R/r ≤ O(n C(d)), and such that r ≥ Ω (\frac{1}{n C(d)}) and R ≤ O(n C(d)), where n is the dimension of the feasible region. Therefore the condition measure C(d) is a relevant tool in proving the existence of an inscribed ball in the feasible region of P that is not too far from the origin and whose radius is not too small.

AMS Subject Classification: 90C, 90C05, 90C60 Keywords: Complexity of Linear Programming, Infinite Programming, Interior Point Methods, Conditioning, Error Analysis

1This research has been partially supported through a grant from FONDECYT (project number 1930948), and by a research fellowship from CORE, Catholic University of Luovain.

2Sloan School of Management, M.I.T., 50 Memorial Drive, Cambridge, MA 02142, USA. email: rfreund@mit.edu 3Department of Industrial Engineering, University of Chile, República 701, Casilla 2777, Santiago, Chile. e-mail:

jvera@dii.uchile.cl

1 Introduction

This paper is concerned with characterizations and properties of the “distance to ill-posedness” and of the condition measure of a conic linear system, i.e., a system of the form:

P:

b − Ax ∈ C_{Y} , x ∈ C_{X} ,  (1.1)

where C_{X} ⊂ X and C_{Y} ⊂ Y are each a closed convex cone in the (finite) n-dimensional normed linear vector space X (with norm ∥x∥ for x ∈ X) and in the (finite) m-dimensional linear vector space Y (with norm ∥y∥ for y ∈ Y), respectively. Here b ∈ Y, and A ∈ L(X, Y) where L(X, Y) denotes the set of all linear operators A : X ⟶ Y. At the moment, we make no assumptions on C_{X} and C_{Y} except that each is a closed convex cone. The reader will recognize immediately that when X = R^{n} and Y = R^{m}, and either (i) C_{X} = {x ∈ R^{n}|x ≥ 0} and C_{Y} = {y ∈ R^{m}|y ≥ 0}, (ii) C_{X} = {x ∈ R^{n}|x ≥ 0} and C_{Y} = {0} ⊂ R^{m} or (iii), C_{X} = R^{n} and C_{Y} = {y ∈ R^{m}|y ≥ 0}, then (1.1) is a linear inequality system of the format (i) Ax ≤ b, x ≥ 0, (ii) Ax = b, x ≥ 0, or (iii) Ax ≤ b, respectively.

The problem P is a very general format for studying the feasible region of a mathematical program, and even lends itself to analysis by interior-point methods, see Nesterov and Nemirovskii[9] and Renegar [13].

The concept of the “distance to ill-posedness” and a closely related condition measure for problems such as P was introduced by Renegar in [11] in a more specific setting, but then generalized more fully in [12] and in [13]. We now present the development of these two concepts in detail.

We denote by d = (A, b) the “data” for the problem (1.1). That is, we regard the cones C_{X} and C_{Y} as fixed and given, and the data for the problem is the linear operator A together with the vector b. We denote the set of solutions of P as X_{d} to emphasize the dependence on the data d, i.e.,

X_{d} = {x ∈ X|b − Ax ∈ C_{Y} , x ∈ C_{X}}.

We define

F = {(A, b) ∈ L(X, Y) × Y | there exists x satisying b − Ax ∈ C_{Y} , x ∈ C_{X}} .  (1.2)

Then F corresponds to those data instances (A, b) for which P is consistent, i.e., (1.1) has a solution.

For d = (A, b) ∈ L(X, Y)×Y we define the product norm on the cartesian product L(X, Y)× Y as

∥d∥ = ∥(A, b)∥ = max{∥A∥, ∥b∥}  (1.3)

where ∥b∥ is the norm specified for Y and ∥A∥ is the operator norm, namely

\begin{aligned}∥A∥ = & max & ∥Ax∥ \\ & s.t. & ∥x∥ ≤ 1 & . \end{aligned}  (1.4)

We denote the complement of F by F^{C}. Then F^{C} consists precisely of those data instances d = (A, b) for which P is inconsistent.

The boundary of F and of F^{C} is precisely the set

B = cl(F) ∩ cl(F^{C})  (1.5)

where cl(S) is the closure of a set S. Note that if d = (A, b) ∈ B, then (1.1) is ill-posed in the sense that arbitrary small changes in the data d = (A, b) will yield consistent instances of (1.1) as well as inconsistent instances of (1.1).

For any d = (A, b) ∈ L(X, Y) × Y, we define

\begin{aligned}ρ(d) = & inf & ∥d − d̄∥ = & inf & ∥(A, b) − (Ā, b̄)∥ \\ & d̄ & & Ā, b̄ \\ & s.t. & d̄∈ B & s.t. & (Ā, b̄) ∈ cl(F) ∩ cl(F^{C}) & . \end{aligned}  (1.6)

Then ρ(d) is the “distance to ill-posedness” of the data d, i.e., ρ(d) is the distance of d from the set B of ill-posedness instances. In addition to the work of Renegar cited earlier, further analysis of the distance to ill-posedness has been studied by Vera [16], [17], [18], Filipowski [6], [7], and recently by Nunez and Freund [10].

In addition to the general case (1.1), we will also be interested in two special cases when one of the cones is either the entire space or only the zero-vector. Specifically, if C_{Y} = {0}, then (1.1) specifies to

Ax = b, x ∈ C_{X} .  (1.7)

When C_{X} = X, then (1.1) specifies to

b − Ax ∈ C_{Y} , x ∈ X .  (1.8)

One of the purposes of this paper is to explore characterizations of the distance to illposedness ρ(d) as the optimal value of a mathematical program whose solution is relatively easy to obtain. By “relatively easy,” we roughly mean that such a program is either a convex program or is solveable through O(m) or O(n) convex programs. Vera [16] and [17] explored such characterizations for linear programming problems, and the results herein expand the scope of this line of research in two ways: first by expanding the problem context from linear equations and linear inequalities to conic linear systems, and second by developing more efficient mathematical programs that characterize ρ(d). Renegar [13] presents a characterization of the distance to ill-posedness as the solution of a certain mathematical program, but this characterization is not in general easy to solve. There are a number of reasons for exploring characterizations of ρ(d), not the least of which is to better understand the underlying nature of ρ(d). There is the intellectual issue of the complexity of computing ρ(d) or an approximation thereof, and there is also the prospect for using such characterizations to further understand the behavior of the underlying problem P. Finally, as is shown in [17], when ρ(d) can be computed efficiently, then there is promise that the problem of deciding the feasibility of P or the infeasibility of P can be processed with a ”fully efficient” algorithm, see [17] or Renegar [12] for details of the concept of a fully efficient algorithm. In Section 3 of this paper, we present ten different mathematical programs each of whose optimal values provides an approximation of ρ(d) to within certain constant factors, depending on whether P is feasible or not, and where the constants depend only on the “structure” of the cones C_{X} and C_{Y} and not on the dimension or on the data d = (A, b).

The second purpose of this paper is to prove the existence of certain inscribed and intersecting balls involving the feasible region of P (or the feasible region of the alternative system of P if P is infeasible), in the spirit of the ellipsoid algorithm and in order to set the stage for an analysis of the ellipsoid algorithm, hopefully in a subsequent paper. Recall that when P is specified to the case of non-degenerate linear inequalities and the data d = (A, b) is an array of rational numbers of bitlength L, that the feasible region of P will intersect a ball of radius R centered at the origin, and will contain a ball of radius r where r = (1/n)2^{−L} and R = n2^{L}. Furthermore, the ratio R/r is of critical importance in the analysis of the complexity of using the ellipsoid algorithm to solve the system P in this particular case. (For the general case of P the Turing machine model of computation is not very appropriate for analyzing issues of complexity, and indeed other models of computation have been proposed (see Blum et.al. [3], also Smale [14].))

By analogy to the properties of rational non-degenerate linear inequalities mentioned above, Renegar [13] has shown that the feasible region X_{d} must intersect a ball of radius R centered at the origin where R ≤ ∥d∥/ρ(d). Renegar [12] defines the condition measure of the data d = (A, b) to be C(d):

C(d) = \frac{∥d∥}{ρ(d)} ,

and so R ≤ C(d). Here we see the value 2^{L} has been replaced by the condition measure C(d).

For the problem P considered herein in (1.1), the feasible region is the set X_{d}. In Sections 4 and 5 of this paper, we utilize the characterization results of Section 3 to prove that the feasible region X_{d} (or the feasible region of the alternative system when P is infeasible) must contain an inscribed ball of radius r that is no more than a distance R from the origin, and where the ratio R/r must satisfy R/r ≤ O(n C(d)). Furthermore, we prove that r ≥ Ω (\frac{1}{n C(d)}) and R ≤ O(n C(d)) (and where n is replaced by m for the alternative system for the case when P is infeasible). Note that by analogy to rational non-degenerate linear inequalities, that the quantity 2^{L} is replaced by C(d). Therefore the condition measure C(d) is a very relevant tool in proving the existence of an inscribed ball in the feasible region of P that is not too far from the origin and whose radius is not too small. This should prove effective in the analysis of the ellipsoid algorithm as applied to solving P.

The paper is organized as follows. Section 2 contains preliminary results, definitions, and analysis. Section 3 contains the ten different mathematical programs each of whose optimal values provides an approximation of ρ(d) to within certain constant factors, as discussed earlier. Section 4 contains four Lemmas that give partial or full characterizations of certain inscribed and intersecting balls related to the feasible region of P (or its alternative region in the case when P is infeasible). Section 5 presents a synthesis of all of the results in the previous two sections into theorems that give a complete treatment both of the characterization results and of the inscribed and intersecting ball results.

2 Preliminaries and Some More Notation

We will work in the setup of finite dimensional normed linear vector spaces. Both X and Y are normed linear spaces of finite dimension n and m, respectively, endowed with norms ∥x∥ for x ∈ X and ∥y∥ for y ∈ Y. For x̄ ∈ X, let B(x̄, r) denote the ball centered at x̄ with radius r, i.e.,

B(x̄, r) = {x ∈ X| ∥x − x̄∥ ≤ r},

and define B(ȳ, r) analogously for ȳ ∈ Y.

For d̄= (Ā, b̄) ∈ L(X, Y) × Y, we define the ball

B(d̄, r) = {d = (A, b) ∈ L(X, Y) × Y |∥d − d̄∥ ≤ r}.

With this additional notation, it is easy to see that the definition of ρ(d) given in (1.6) is equivalent to:

ρ(d) = \{ \begin{matrix}sup \{δ|B(d, δ) ⊂ F\} & if d ∈ F \\ sup \{δ|B(d, δ) ⊂ F^{C}\} & if d ∈ F^{C} \end{matrix}  (2.1)

We associate with X and Y the dual spaces X^{∗} and Y^{∗} of linear functionals defined on X and Y, respectively, and whose (dual) norms are denoted by ∥u∥_{∗} for u ∈ X^{∗} and ∥w∥_{∗} for w ∈ Y^{∗}. Let c ∈ X^{∗}. In order to maintain consistency with standard linear algebra notation in mathematical programming, we will consider c to be a column vector in the space X^{∗} and will denote the linear function c(x) by c^{T} x. Similarly, for A ∈ L(X, Y) and f ∈ Y^{∗}, we denote A(x) by Ax and f(y) by f^{T} y. We denote the adjoint of A by A^{T}.

If C is a convex cone in X, C^{∗} will denote the dual convex cone defined by

C^{∗} = {z ∈ X^{∗}|z^{T} x ≥ 0 for any x ∈ C} .

Remark 2.1 If we identify (X^{∗})^{∗} with X, then (C^{∗})^{∗} = C whenever C is a closed convex cone.

Remark 2.2 If C_{X} = X, then C_{X}^{∗} = {0}. If C_{X} = {0}, then C_{X}^{∗} = X.

We will say that a cone C is regular if C is a closed convex cone, has a nonempty interior and is pointed (i.e., contains no line).

Remark 2.3 C is regular if and only if C^{∗} is regular.

We denote the set of real numbers by R and the set of nonnegative real numbers by R_{+}.

Regarding the consistency of (1.1), we have the following partial “theorem of the alternative,” the proof of which is a straightforward exercise using a separating hyperplane argument.

Proposition 2.1 If (1.1) has no solution, then the system (2.2) has a solution:

\begin{matrix}A^{T} y ∈ C_{X}^{∗} \\ y ∈ C_{Y}^{∗} \\ y^{T} b ≤ 0 \\ y ≠ 0. \end{matrix}  (2.2)

If the system (2.3) has a solution:

\begin{matrix}A^{T} y ∈ C_{X}^{∗} \\ y ∈ C_{Y}^{∗} \\ y^{T} b < 0, \end{matrix}  (2.3)

then (1.1) has no solution.

Using Proposition 2.1, it is elementary to prove the following:

Lemma 2.1 Consider the set of ill-posed instances B. Then B can be characterized as:

B = {d = (A, b) ∈ L(X, Y) × Y | there exists (x, r) ∈ X × R with
(x, r) ≠ 0 and y ∈ Y^{∗} with y ≠ 0 satisfying br − Ax ∈ C_{Y} , x ∈ C_{X},
y ∈ C_{Y}^{∗} , A^{T} y ∈ C_{X}^{∗}, and y^{T} b ≤ 0}  .

We now recall some facts about norms. Given a finite dimensional linear vector space X endowed with a norm ∥x∥ for x ∈ X, the dual norm induced on the space X^{∗} is denoted by ∥z∥_{∗} for z ∈ X^{∗}, and is defined as:

\begin{aligned}∥z∥_{∗} = & max & z^{T} x \\ & x \\ & s.t. & ∥x∥ ≤ 1 & . \end{aligned}  (2.4)

If we denote the unit balls in X and X^{∗} by B and B^{∗}, then it is straightforward to verify that

B = {x ∈ X|∥x∥ ≤ 1} = {x ∈ X|z^{T} x ≤ 1 for all z with ∥z∥_{∗} ≤ 1},  (2.5)

and

B^{∗} = {z ∈ X^{∗}|∥z∥_{∗} ≤ 1} = {z ∈ X^{∗}|z^{T} x ≤ 1 for all x with ∥x∥ ≤ 1}.  (2.6)

Furthermore,

z^{T} x ≤ ∥z∥_{∗}∥x∥ for any x ∈ X and z ∈ X^{∗},  (2.7)

which is the Hölder inequality. Finally, note that if A = uv^{T}, then it is easy to derive that ∥A∥ = ∥v∥_{∗}∥u∥ using (2.4) and (1.4).

If X and V are finite-dimensional normed linear vector spaces with norm ∥x∥ for x ∈ X and norm ∥v∥ for v ∈ V, then for (x, v) ∈ X × V, the function f(x, v) defined by

f(x, v) = ∥(x, v)∥ \underline{\underline{Δ}} ∥x∥ + ∥v∥  (2.8)

defines a norm on X × V, whose dual norm is given by

∥(w, u)∥_{∗} \underline{\underline{Δ}} max \{∥w∥_{∗}, ∥u∥_{∗}\} for (w, u) ∈ (X × V)^{∗} = X^{∗} × V^{∗}.  (2.9)

The following result is a special case of the Hahn-Banach Theorem, see for example [19]:

Proposition 2.2 For every x ∈ X, there exists z ∈ X^{∗} with the property that ∥z∥_{∗} = 1 and ∥x∥ = z^{T} x.

Proof: If x = 0, then any z ∈ X^{∗} with ∥z∥_{∗} = 1 will satisfy the statement of the proposition. Therefore, we suppose that x ≠ 0. Consider ∥x∥ as a function of x, i.e., f(x) = ∥x∥. Then f(·) is a real-valued convex function, and so the subdifferential operator ∂f(x) is non-empty for all x ∈ X, see [2]. Consider any x ∈ X, and let z ∈ ∂f(x). Then

f(w) ≥ f(x) + z^{T} (w − x) for any w ∈ X.  (2.10)

Substituting w = 0 we obtain ∥x∥ = f(x) ≤ z^{T} x. Substituting w = 2x we obtain 2f(x) = f(2x) ≥ f(x)+z^{T} (2x−x), and so f(x) ≥ z^{T} x, whereby f(x) = z^{T} x. From (2.7) it then follows that ∥z∥_{∗} ≥ 1. Now if we let u ∈ X and set w = x + u, we obtain from (2.10) that f(u) + f(x) ≥ f(u + x) = f(w) ≥ f(x) + z^{T} (w − x) = f(x) + z^{T} (u + x − x) = f(x) + z^{T} u. Therefore, z^{T} u ≤ f(u) = ∥u∥, and so from (2.4) we obtain ∥z∥_{∗} ≤ 1. Therefore, ∥z∥_{∗} = 1.

Because X and Y are are normed linear vector spaces of finite dimension, all norms are equivalent. Thus we can specify a norm for X and a norm for Y if we so desire. If X = R^{n}, the L_{p} norm is given by

∥x∥_{p} = (∑_{j=1}^{n} |x_{j}|^{p})^{1/p} ,  (2.11)

for p ≥ 1. The norm dual to ∥x∥_{p} is ∥z∥_{∗} = ∥z∥_{q} where q satisfies 1/p + 1/q = 1, with appropriate limits as p → 1 and p → +∞.

A critical component of our analysis concerns the extent to which the norm function ∥x∥ can be approximated by a linear function u^{T} x over the cone C_{X} for some u ∈ C_{X}^{∗}, and the extent to which the norm function ∥y∥_{∗} can be approximated by a linear function z^{T} y over the cone C_{Y}^{∗} for some z ∈ C_{Y}. We now define two important constants that relate the extent to which these norms ∥x∥ and ∥y∥_{∗} can be approximated by linear functions over the convex cones C_{X} and C_{Y}^{∗}, respectively.

Definition 2.1 (i) If C_{X} is regular, let

\begin{aligned}β = & sup & inf u^{T} x \\ & u ∈ X^{∗} & x ∈ C_{X} \\ & ∥u∥_{∗} = 1 & ∥x∥ = 1 & . \end{aligned}  (2.12)

(ii) If C_{Y} is regular, let

\begin{aligned}β^{∗} = & sup & inf y^{T} z \\ & z ∈ Y & y ∈ C_{Y}^{∗} \\ & ∥z∥ = 1 & ∥y∥_{∗} = 1 & . \end{aligned}  (2.13)

Examining (2.12) in detail, let ū denote that value of u ∈ X^{∗} that achieves the supremum in (2.12). Then for all x ∈ C_{X}, β∥x∥ ≤ ū^{T} x ≤ ∥x∥, and so ∥x∥ is approximated by the linear function ū^{T} x to within the factor β over the cone C_{X}. Therefore, β measures the extent to which ∥x∥ can be approximated by a linear function ū^{T} x on the cone C_{X}. Furthermore, ū^{T} x is the “best” such linear approximation of ∥x∥ over this cone. If we let z̄ denote that value of z ∈ Y that achieves the supremum in (2.13), then similar remarks pertain, and so z̄^{T} y is the “best” linear approximation of ∥y∥_{∗} on the cone C_{Y}^{∗} . (It is easy to see that β ≤ 1 and β^{∗} ≤ 1, since, for example, u^{T} x ≤ ∥u∥_{∗}∥x∥ = 1 for u and x as in (2.12), and y^{T} z ≤ ∥y∥_{∗}∥z∥ = 1 for y and z as in (2.13).) The larger the value of β, the more closely that ∥x∥ is approximated by a linear function u^{T} x over x ∈ C_{X}. Similar remarks pertain to β^{∗}. We have the following properties of β and β^{∗}:

Proposition 2.3 (i) If C_{X} is regular, then 0 < β ≤ 1, and there exists ū ∈ int C_{X}^{∗} such that

∥ū∥_{∗} = 1 and β = min{ū^{T} x|x ∈ C_{X}, ∥x∥ = 1}.

(ii) If C_{Y} is regular, then 0 < β^{∗} ≤ 1, and there exists z̄ ∈ int C_{Y} such that

∥z̄∥ = 1 and β^{∗} = min{z̄^{T} y|y ∈ C_{Y}^{∗} , ∥y∥_{∗} = 1}.

The proof of Proposition 2.3 follows easily from the following observation:

Remark 2.4 Suppose K is a closed convex cone. Then z ∈ int K^{∗} if and only if z^{T} x > 0 for all x ∈ K/{0}. Also, if z ∈ int K^{∗}, the set {x ∈ K|z^{T} x = 1} is a closed and bounded convex set.

For the remainder of this study, it is assumed that ū and z̄ of Proposition 2.3 are known and given, whenever C_{X} and/or C_{Y} are regular.

Corollary 2.1 (i) If C_{X} is regular, then

β∥x∥ ≤ ū^{T} x ≤ ∥x∥ for any x ∈ C_{X}.  (2.14)

(ii) If C_{Y} is regular, then

β^{∗}∥y∥_{∗} ≤ z̄^{T} y ≤ ∥y∥_{∗} for any y ∈ C_{Y}^{∗} .  (2.15)

We also define

Definition 2.2 (i) If C_{X} is regular, let

\begin{aligned}β̄ = & inf & sup w^{T} x \\ & w ∈ C_{X}^{∗} & x ∈ C_{X} \\ & ∥w∥_{∗} = 1 & ∥x∥ ≤ 1 & . \end{aligned}  (2.16)

(ii) If C_{Y} is regular, let

\begin{aligned}β̄^{∗} = & inf & sup v^{T} w \\ & w ∈ C_{Y} & v ∈ C_{Y}^{∗} \\ & ∥w∥ = 1 & ∥v∥_{∗} ≤ 1 & . \end{aligned}  (2.17)

We offer the following interpretation of β̄ and β̄^{∗}. Note that β̄ ≤ 1 since w^{T} x ≤ ∥w∥_{∗}∥x∥ ≤ 1 for any w and x given in (2.16). Now, from (2.4) we have that for any w ∈ C_{X}^{∗} with ∥w∥_{∗} = 1, that

1 = ∥w∥_{∗} = sup w^{T} x ≥ sup w^{T} x
x ∈ X  x ∈ C_{X}
∥x∥ ≤ 1  ∥x∥ ≤ 1 .

Thus β̄ represents the extent to which ∥w∥_{∗} is approximated by optimizing over C_{X} instead of over X in the construction of ∥w∥_{∗}, as w ranges over all values in C_{X}^{∗}. A similar interpretation for β̄^{∗} can also be developed. We have:

Proposition 2.4

(i) If C_{X} is regular, then 0 < β̄ ≤ 1 .
(ii) If C_{Y} is regular, then 0 < β̄^{∗} ≤ 1.

Finally, we note that the constants, β, β^{∗}, β̄, and β̄^{∗} depend \underline{only} on the norms ∥x∥ and ∥y∥ and the cones C_{X} and C_{Y}, and are independent of the data (A, b) defining the problem (1.1).

We now present two families of examples that illustrate the constructions above. For the first example, let X = R^{n} and C_{X} = {x ∈ R^{n}|x ≥ 0}. Then we can identify X^{∗} with X and in so doing, C_{X}^{∗} = {x ∈ R^{n}|x ≥ 0} as well. If ∥x∥ = ∥x∥_{p}, then for x ∈ C_{X}, it is straightforward to show that ū = (n^{\frac{1}{p} −1}) e, where e = (1, …, 1)^{T}, i.e., the linear function given by ū^{T} x is the “best” linear approximation of the function ∥x∥ on the set C_{X}. Furthermore, straightforward calculation yields that β = n^{\frac{1}{p} −1}. Then if p = 1, β = 1, but if p > 1 then β < 1. However, regardless of the value of p, it will be true that β̄ = 1. To see this, note that if w ∈ R^{n} and w ≥ 0 (i.e., w ∈ C_{X}^{∗}) and ∥w∥_{∗} = 1, then with x = (x_{1}, …, x_{n})^{T} where

x_{j} = w_{j}^{(\frac{1}{p−1})} ,

that w^{T} x = ∥w∥_{q} = ∥w∥_{∗} = 1 (where \frac{1}{p} + \frac{1}{q} = 1) and ∥x∥ = 1. Note that x ≥ 0, so that β̄ = 1.

The second example concerns the cone of symmetric positive semi-definite matrices, which has been shown to be of enormous importance in mathematical programming (see Alizadeh [1] and Nesterov and Nemiroskii [9]). Let X denote the set of real n × n symmetric matrices, and let C_{X} = {x ∈ X|x is positive semi − definite}. Then C_{X} is a closed convex cone. We can identify X^{∗} with X, and in so doing it is elementary to derive that C_{X}^{∗} = {y ∈ X^{∗}|y is postive semi − definite} i.e., C_{X} is self-dual. Foe x ∈ X, let λ(x) denote the n-vector of ordered eigenvalues of x. That is, λ(x) = (λ_{1}(x), …, λ_{n}(x))^{T} where λ_{i}(x) is the i^{th} largest eigenvalue of X. For any p ∈ [1, ∞), let the norm of x be defined by

∥x∥ = ∥x∥_{p} =^{Δ} (∑_{j=1}^{n} |λ_{j}(x)|^{p})^{\frac{1}{p}} ,

i.e., ∥x∥_{p} is the p-norm of the vector of eigenvalues of X. (see Lewis [8] for a proof that ∥x∥_{p} is a norm.)

When p = 2, ∥x∥_{2} corresponds precisely to the Fröbenius norm of x. When p = 1, ∥x∥_{1} is the

sum of the absolute values of the eigenvalues of x. Therefore, when x ∈ C_{X}, ∥x∥_{1} = tr(x) = ∑_{i=1}^{n} x_{ii}

where x_{ii} is the i^{th} diagonal entry of the real matrix x, and so is linear on C_{X}. It is easy to show for the norm ∥x∥_{p} over C_{X} that ū = (n^{\frac{1}{p} −1}) I has ∥ū∥_{∗} = ∥ū∥_{q} = 1 and that β = n^{\frac{1}{p} −1}. Thus, for the Fröbenius norm we have β = \frac{1}{\sqrt{n}} and for the L_{1}-norm, we have β = 1. Just as in the case of the non-negative orthant above, it can easily be shown that β̄ = 1 for any value of p ∈ [1, ∞).

We conclude this section with the following:

Remark 2.5 If C_{X} is regular, then it is possible to choose the norm on X in such a way that β = 1. If C_{Y} is regular, then it is possible to choose the norm on Y in such a way that β^{∗} = 1.

To see why this remark is true, recall that for finite dimensional linear vector spaces, that all norms are equivalent. Now suppose that C_{X} is regular. Pick any ū ∈ int C_{X}^{∗}. Then define the following norm on X:

∥x∥ \underline{\underline{Δ}} minimum \{ū^{T} x′ − ū^{T} x′′|x = x′ + x′′, x′ ∈ C_{X}, x′′ ∈ −C_{X}\} .

It can then easily be verified that ∥ · ∥ is a norm and that for all x ∈ C_{X}, that ∥x∥ = ū^{T} x, whereby β = 1. A parallel construction works for ∥y∥_{∗} and shows that ∥ · ∥_{∗} on Y^{∗} can be chosen so that β^{∗} = 1.

3 Characterization Results for ρ(d)

Given a data instance d = (A, b) ∈ L(X, Y) × Y, we now present characterizations of ρ(d) for the feasibility problem P given in (1.1) .

The characterizations of ρ(d) will depend on whether d ∈ F or d ∈ F^{C} (recall (1.2)), i.e., whether (1.1) is consistent or not. We first study the case when d ∈ F ((1.1) is consistent), followed by the case when d ∈ F^{C} ((1.1) is not consistent).

3.1 Characterization Results when P is consistent

In this subsection, we present five different mathematical programs and we prove that the optimal value of each of these mathematical programs provides an approximation of the value of ρ(d), in the case when P is consistent. For each of these five mathematical programs, the nature of the approximation of ρ(d) is specified in a theorem stating the result.

We motivate the development of these programs on intuitive grounds as follows. If P is consistent, i.e., d ∈ F, then it is elementary to see that:

ρ(d) = infimum ∥d − d̄∥
d̄
s.t.  d̄= (Ā, b̄) ∈ F^{C} ,

that is, ρ(d) measures how close the data d lies to the set of data for which P has no solution. As d ∉ F^{C}, then there is no solution y ∈ Y^{∗} to the system:

\begin{matrix}A^{T} y ∈ C_{X}^{∗} \\ −b^{T} y > 0 \\ y ∈ C_{Y}^{∗} \\ ∥y∥_{∗} = 1 & , \end{matrix}

see Proposition 2.1, and notice in the above that we have added a normalizing constraint “∥y∥_{∗} = 1.” However, when C_{X} is regular, then the vector ū ∈ intC_{X}^{∗} (see Proposition 2.3), and we can measure how far away d = (A, b) is from admitting a solution to the above system (i.e., how far away d is from the set F^{C}) by solving the following program:

P_{α}(d) :

\begin{aligned}α(d) = & minimum & γ \\ & y, γ \\ & s.t. & A^{T} y + γū ∈ C_{X}^{∗} \\ & & −b^{T} y + γ ≥ 0 \\ & & ∥y∥_{∗} = 1 \\ & & y ∈ C_{Y}^{∗} & . \end{aligned}  (3.1)

Notice that α(d) ≥ 0, since otherwise d ∈ F^{C} via Proposition 2.1, which would violate the hypothesis of this subsection. Also notice that α(d) < +∞, since ū ∈ intC_{X}^{∗}, and so P_{α}(d) is feasible for any y ∈ C_{Y}^{∗} with ∥y∥_{∗} = 1 and γ chosen sufficiently large. The smaller the value of α(d) is, the closer the conditions (2.3) of infeasibility are to being satisfied, and so the smaller the value of ρ(d) should be. These arguments are obviously imprecise, but we will prove their validity in the following:

Theorem 3.1 If d ∈ F and C_{X} is regular, then

β · α(d) ≤ ρ(d) ≤ α(d) .

This theorem states that α(d) approximates ρ(d) to within the factor β, where recall the definition of β in Definition 2.1. The proof of this theorem and all of the results of this subsection are deferred to the end of the subsection.

Remark 3.1 It should be pointed out that P_{α}(d) is not in general a convex program, due to the non-convex constraint “∥y∥_{∗} = 1”. However, in the case when Y = R^{m}, (then Y^{∗} can also be identified with R^{m}), if we choose the norm on Y^{∗} to be the L_{∞} norm (so the norm on Y is the L_{1} norm), then P_{α}(d) can be solved by solving 2m convex programs. To see this, observe that the constraint “∥y∥_{∗} = 1” can be written as −e ≤ y ≤ e and y_{i} = ±1 for some i ∈ {1, …, m}, where e is the vector of ones. Then α(d) = minimum {α′(d), α′′(d)}, where :

α′(d) = minimum minimum γ
i = 1, …, m  y, γ
s.t.  A^{T} y + γū ∈ C_{X}^{∗}
−b^{T} y + γ ≥ 0
−e ≤ y ≤ e
y_{i} = 1
y ∈ C_{Y}^{∗}  ,

and

α′′(d) = minimum minimum γ
i = 1, …, m  y, γ
s.t.  A^{T} y + γū ∈ C_{X}^{∗}
−b^{T} y + γ ≥ 0
−e ≤ y ≤ e
y_{i} = −1
y ∈ C_{Y}^{∗}  .

The next mathematical program is obtained by considering the following homogenization of P:

\begin{matrix}br − Ax ∈ C_{Y} \\ x ∈ C_{X} \\ r ≥ 0 & , \end{matrix}

which can be normalized in the case when C_{X} is regular as follows:

H :

br − Ax ∈ C_{Y}
x ∈ C_{X}
r ≥ 0
r + ū^{T} x = 1 .

One can think of ū^{T} x as a linear approximation of ∥x∥ over the cone C_{X}, see Corollary 2.1. (In fact, the construction of β and ū in Definition 2.1 and Proposition 2.3 is such that ū^{T} x is the “best” linear approximation of ∥x∥ over the cone C_{X}.) Now, an “internal view” of ρ(d) is that ρ(d) measures the extent to which the data d = (A, b) can be altered and yet (1.1) will still be feasible for the new system. A modification of this view is that ρ(d) measures the extent to which the system (1.1) can be modified while ensuring its feasibility. Consider the following program:

P_{w}(d) :

w(d) = minimum maximum θ
v  r, x, θ
∥v∥ ≤ 1  s.t.  br − Ax− vθ ∈ C_{Y}
x ∈ C_{X}
r + ū^{T} x = 1
r ≥ 0  .

(3.2)

Then w(d) is the largest scaling factor θ such that for any v with ∥v∥ ≤ 1, vθ can be added to the first inclusion of H without affecting the feasibility of the system. We will prove:

Theorem 3.2 If d ∈ F and C_{X} is regular, then α(d) = w(d), and so

β · w(d) ≤ ρ(d) ≤ w(d) .

Three remarks are in order here. First, the theorem asserts that α(d) = w(d), and in fact the proof of the theorem will show that P_{w}(d) can be obtained from P_{α}(d) by dualizing on a subset of the variables and constraints of P_{α}(d), i.e., P_{α}(d) and P_{w}(d) are partial duals of one another. Second, there is an underlying geometry in P_{w}(d). To see this, let

S = {v ∈ Y | there exists r ≥ 0 and x ∈ C_{X} satisfying br − Ax − v ∈ C_{Y} , ū^{T} x + r = 1}. (3.3)

Then P_{w}(d) can alternatively be written as:

\begin{aligned}w(d) = & sup & θ \\ & θ \\ & s.t. & \{v ∈ Y |∥v∥ ≤ θ\} ⊂ S & . \end{aligned}  (3.4)

Then w(d) is the radius of the largest ball centered at the origin and contained in the set S. Third, if we replace the normalizing linear constraint “r + ū^{T} x = 1” of P_{w}(d) by the norm constraint “r+∥x∥ = 1,” then the modified program is analogous to Renegar’s characterization of the distance to ill-posedness (see Theorem 3.5 in [13]) when P is consistent. The modified program is:

P_{r}(d) :

r(d) = minimum maximum θ
v  r, x, θ
∥v∥ ≤ 1  s.t.  br − Ax− vθ ∈ C_{Y}
x ∈ C_{X}
r + ∥x∥ = 1
r ≥ 0  ,

and Renegar shows that r(d) = ρ(d) when d ∈ F. We will not use this fact, nor duplicate the proof of this fact here; rather it is our intent to show the connection to the results in [13].

One problem with P_{α}(d) is that P_{α}(d) is generally nonconvex, due to the constraint “∥y∥_{∗} = 1.” When C_{Y} is also regular, then from Corollary 2.1 the linear function z̄^{T} y is a “best” linear approximation of ∥y∥_{∗} on C_{Y}^{∗}, and if we replace “∥y∥_{∗} = 1” by “z̄^{T} y = 1” in P_{α}(d) we obtain:

Pα̃(d) :

\begin{aligned}α̃(d) = & minimum & γ \\ & y, γ \\ & s.t. & A^{T} y + γū ∈ C_{X}^{∗} \\ & & −b^{T} y + γ ≥ 0 \\ & & z̄^{T} y = 1 \\ & & y ∈ C_{Y}^{∗} & . \end{aligned}  (3.5)

Replacing the norm constraint by its linear approximation will reduce (by a constant) the extent to which the program computes an approximation of ρ(d), and the analog of Theorem 3.1 becomes:

Theorem 3.3 If d ∈ F and both C_{X} and C_{Y} are regular, then

β^{∗}β · α̃(d) ≤ ρ(d) ≤ α̃(d).

Notice that a very nice feature of Pα̃(d) is that it is a convex program.

The fourth mathematical program is derived by once again measuring the extent to which the data d = (A, b) does not admit a solution of (2.3). In the case when C_{Y} is regular, consider the program:

P_{u}(d) :

u(d) = minimum maximum {∥A^{T} y − q∥_{∗}, |b^{T} y + g|}
y, q, g
s.t.  y ∈ C_{Y}^{∗}
q ∈ C_{X}^{∗}
g ≥ 0
z̄^{T} y = 1 .

(3.6)

If d = (A, b) were in F^{C}, then form Proposition 2.1 it would be true that u(d) = 0. The nonnegative quantity u(d) measures the extent to which (2.3) is not feasible. The smaller the value of u(d) is, the closer the conditions (2.3) are to being satisfied, and so the smaller the value of ρ(d) should be. These arguments are imprecise, but the next theorem validates the intuition of this line of thinking:

Theorem 3.4 If d ∈ F and C_{Y} is regular, then

β^{∗}u(d) ≤ ρ(d) ≤ u(d) .

Therefore, u(d) approximates ρ(d) to within the factor β^{∗}, where β^{∗} is defined in Definition 2.1.

Notice that P_{u}(d) is also a convex program, which is convenient. If the constraint “z̄^{T} y = 1” in P_{u}(d) is replaced with the norm constraint “∥y∥_{∗} = 1,” one obtains the nonconvex program:

P_{j}(d) :

j(d) = minimum maximum {∥A^{T} y − q∥_{∗}, |b^{T} y + g|}
y, q, g
s.t.  y ∈ C_{Y}^{∗}
q ∈ C_{X}^{∗}
g ≥ 0
∥y∥_{∗} = 1 ,

and one can prove (although we will not do this here) that P_{j}(d) can be derived as a partial dual of P_{r}(d), and so j(d) = r(d), whereby j(d) = ρ(d) as in Theorem 3.5 of [13].

Returning to P_{u}(d), notice that the feasible region of this program is a convex set, and that the objective function is a gauge function, i.e., a nonnegative convex function that is positively homogeneous of degree 1, see [15]. A mathematical program that minimizes a gauge function over a convex set is called a gauge program, and corresponding to every gauge program is a dual gauge program that also minimizes a (dual) gauge function over a (dual) convex set, see [5]. For the program P_{u}(d), its dual gauge program is given by:

P_{v}(d) :

\begin{aligned}v(d) = & minimum & & ∥x∥ + |r| \\ & x, r \\ & & br − & Ax − z̄ ∈ C_{Y} \\ & & & x ∈ C_{X} \\ & & & r ≥ 0 & . \end{aligned}  (3.7)

In general, dual gauge programs will have the product of their optimal values equal to 1, as the last theorem of this subsection indicates:

Theorem 3.5 If d ∈ F and C_{Y} is regular, then u(d) · v(d) = 1 whenever u(d) > 0, and

\frac{β^{∗}}{v(d)} ≤ ρ(d) ≤ \frac{1}{v(d)} .

Note that P_{v}(d) is also a convex program. One can interpret P_{v}(d) as measuring the extent to which P has a solution that is interior the cone C_{Y}. To see this, note from Proposition 2.3 that z̄ ∈ intC_{Y} , and so P_{v}(d) will only be feasible if P has a solution interior to C_{Y}. The more interior a solution there is, the smaller (r, x) can be scaled and still satisfy br − Ax − z̄ ∈ C_{Y}. One would then expect ρ(d) to be inversely proportional to v(d), as Theorem 3.5 indicates.

The proofs of these five theorems are given below.

Proof of Theorem 3.1: Suppose γ > α(d). Then there exist ȳ, γ̄, with α(d) ≤ γ̄ < γ and (ȳ, γ̄) is feasible for P_{α}(d). Therefore, A^{T} ȳ + γ̄ū ∈ C_{X}^{∗}, −b^{T} ȳ + γ̄ ≥ 0, ∥ȳ∥_{∗} = 1, and ȳ ∈ C_{Y}^{∗}. From Proposition 2.2, there exists v̄ ∈ Y that satisfies ∥v̄∥ = 1 and ȳ^{T} v̄ = ∥ȳ∥_{∗} = 1. Let d̄= (Ā, b̄) = (A+γv̄ū^{T} , b−γv̄). Then ∥Ā−A∥ = γ∥v̄ū^{T} ∥ = γ∥v̄∥ ∥ū∥_{∗} = γ, and ∥b̄−b∥ = γ∥v̄∥ = γ. Thus ∥d̄− d∥ = max {∥Ā − A∥, ∥b̄ − b∥} = γ. Next note that Ā^{T} ȳ = A^{T} ȳ + γūv̄^{T} ȳ = A^{T} ȳ + γū = A^{T} ȳ + γ̄ū + (γ − γ̄)ū ∈ C_{X}^{∗}, and −b̄^{T} ȳ = −b^{T} ȳ + γv̄^{T} ȳ = −b^{T} ȳ + γ > −b^{T} ȳ + γ̄ ≥ 0. Therefore, by Proposition 2.1, (Ā, b̄) ∈ F^{C}. Therefore, ρ(d) ≤ ∥d − d̄∥ = γ. As this is true for any γ > α(d), we must have ρ(d) ≤ α(d), proving the second inequality of the theorem.

To prove the first inequality of the theorem, let α > ρ(d) be chosen. Then there exists (Ā, b̄) for which ∥d − d̄∥ ≤ α and d̄ ∈ F^{C}. Then, from Proposition 2.1, there exists ȳ ∈ C_{Y}^{∗} satisfying Ā^{T} ȳ ∈ C_{X}^{∗}, b̄^{T} ȳ ≤ 0, and ∥ȳ∥_{∗} = 1 (without loss of generality). Then for any x ∈ C_{X} that satisfies ∥x∥ = 1, we will have

x^{T} A^{T} ȳ + \frac{α}{β}ū^{T} x = x^{T} (A − Ā)^{T} ȳ + x^{T} Ā^{T} ȳ + \frac{α}{β}ū^{T} x
≥ −∥x∥ ∥A − Ā∥ ∥ȳ∥_{∗} + 0 + α  (from Proposition 2.3)
≥ −α + α = 0  .

Therefore, A^{T} ȳ+\frac{α}{β} ū ∈ C_{X}^{∗}. Also, −b^{T} ȳ+\frac{α}{β} = −b̄^{T} y+(b̄−b)^{T} ȳ+\frac{α}{β} ≥ −∥b̄−b∥ ∥ȳ∥_{∗}+\frac{α}{β} ≥ −α+\frac{α}{β} ≥ 0, since β ≤ 1 from Proposition 2.3. Thus γ = \frac{α}{β} is feasible for P_{α(d)} with y = ȳ. Therefore,

α(d) ≤ γ = \frac{α}{β}. As this is true for any α > ρ(d), it is also true that α(d) ≤ \frac{ρ(d)}{β}, completing the proof.

Proof of Theorem 3.2: Consider the program P_{α}(d) given in (3.1). Because d ∈ F, i.e., P has a solution, there can be no feasible solution (y, γ) of P_{α}(d) with γ < 0 (for if so, then y ∈ C_{Y}^{∗} , b^{T} y ≤ γ < 0, and A^{T} y = A^{T} y + γū − γū ∈ intC_{X}^{∗} since ū ∈ intC_{X}^{∗}, violating Proposition 2.1). Therefore, we can amend P_{α}(d) by replacing the constraint ”∥y∥_{∗} = 1” by ”∥y∥_{∗} ≥ 1”, so that

α(d) = minimum  γ
y, γ
s.t.  A^{T} y + γū ∈ C_{X}^{∗}
−b^{T} y + γ ≥ 0
∥y∥_{∗} ≥ 1
y ∈ C_{Y}^{∗}  .

However, ∥y∥_{∗} ≥ 1 if and only if there exists v ∈ Y that satisfies ∥v∥ ≤ 1 and y^{T} v ≥ 1 (see (2.4)), and so we can write:

α(d) = minimum  γ
v, y, γ
s.t.  A^{T} y + γū ∈ C_{X}^{∗}
−b^{T} y + γ ≥ 0
y^{T} v ≥ 1
y ∈ C_{Y}^{∗}
v ∈ Y, ∥v∥ ≤ 1 .

We then separate this problem into the two-level optimization problem:

α(d) = minimum minimum  γ
v ∈ Y  y, γ
∥v∥ ≤ 1
s.t.  A^{T} y + γū ∈ C_{X}^{∗}
−b^{T} y + γ ≥ 0
y^{T} v ≥ 1
y ∈ C_{Y}^{∗}  .

Next note that the right-most (or bottom-level) problem is an instance of ND of the Appendix given in (A.9), where K_{1}^{∗} = C_{Y}^{∗} , w = v, and K_{2}^{∗} = C_{X}^{∗} ×R_{+}, M^{T} y = (−A^{T} y, +b^{T} y), and f = (ū, 1). The dual problem associated with ND is given by NP in (A.8), which translates to

v_{P} = maximum  θ
x, r, θ
s.t.  br − Ax − θv ∈ C_{Y}
x ∈ C_{X}
r ≥ 0
ū^{T} x + r = 1
θ ≥ 0  .

Furthermore, since d ∈ F, this program is feasible (set θ = 0, and rescale any solution x of P), and then since all of the hypotheses of Theorem A.2 are satisfied, v_{P} = v_{D}, and so we can replace the bottom-level program by its dual, whereby

α(d) = minimum maximum  θ
v ∈ Y  y, r, θ
∥v∥ ≤ 1
s.t.  br − Ax − θv ∈ C_{Y}
x ∈ C_{X}
r ≥ 0
ū^{T} x + r = 1
θ ≥ 0  ,

which is precisely w(d), so α(d) = w(d).

Proof of Theorem 3.3: Suppose α > α̃(d). Then there exists (ȳ, γ̄) feasible for Pα̃(d) such that γ̄ < α. Therefore, A^{T} ȳ + γ̄ū ∈ C_{X}^{∗}, −b^{T} ȳ + γ̄ ≥ 0, and z̄^{T} ȳ = 1 and ȳ ∈ C_{Y}^{∗}. From Corollary 2.1, 1 ≤ ∥ȳ∥_{∗} ≤ \frac{1}{β^{∗}}. From Proposition 2.2, there exists v̄ ∈ Y such that v̄^{T} ȳ = ∥ȳ∥_{∗} and ∥v̄∥ = 1. Now let d̄ = (Ā, b̄) = (A + αv̄ū^{T} , b − αv̄). Then ∥Ā − A∥ = α∥v̄∥ ∥ū∥_{∗} = α, and ∥b̄ − b∥ = α∥v̄∥ = α, so that ∥d̄ − d∥ = α. Now b̄^{T} ȳ = b^{T} ȳ − αv̄^{T} ȳ = b^{T} ȳ − α∥ȳ∥_{∗} ≤ b^{T} ȳ − α < b^{T} ȳ − γ̄ ≤ 0, so that b̄^{T} ȳ < 0 (the first inequality here being an instance of (2.15)). Also, for any x ∈ C_{X} satisfying ∥x∥ = 1, we have x^{T} Ā^{T} ȳ = x^{T} A^{T} ȳ + αx^{T} ūv̄^{T} ȳ + γ̄ū^{T} x − γ̄ū^{T} x ≥ αx^{T} ūv̄^{T} ȳ − γū^{T} x = ū^{T} x(αv̄^{T} ȳ − γ̄) ≥ γ̄ū^{T} x(v̄^{T} ȳ − 1) ≥ 0. Thus Ā^{T} ȳ ∈ C_{X}^{∗}. From Proposition 2.1, then d̄ ∈ F^{C}, and so ρ(d) ≤ ∥d̄− d∥ = α. As this is true for any α > α̃(d), then ρ(d) ≤ α̃(d), which proves the second inequality of the theorem.

To prove the first inequality of the theorem, suppose that α > ρ(d). Then there exists a data instance d̄ = (Ā, b̄) with ∥d̄ − d∥ ≤ α for which d̄ ∈ F^{C}. From Proposition 2.1, there exists ȳ ∈ C_{Y}^{∗} satisfying Ā^{T} ȳ ∈ C_{X}^{∗}, b̄^{T} ȳ ≤ 0, and without loss of generality, z̄^{T} ȳ = 1. We now show that (y, γ) = (ȳ, \frac{α}{ββ^{∗}} ) is feasible for Pα̃(d). First observe that ȳ ∈ C_{Y}^{∗} and z̄^{T} ȳ = 1. Also −b^{T} ȳ + \frac{α}{ββ^{∗}} = −b̄^{T} ȳ + (b̄ − b)^{T} ȳ + \frac{α}{ββ^{∗}} ≥ −∥b̄ − b∥∥ȳ∥_{∗} + \frac{α}{ββ^{∗}} ≥ −\frac{α}{β^{∗}} + \frac{α}{ββ^{∗}} ≥ 0. It remains to show that A^{T} ȳ + \frac{α}{ββ^{∗}} ū ∈ C_{X}^{∗}. To see this, observe that for any x ∈ C_{X} with ∥x∥ = 1, that

x^{T} A^{T} ȳ + \frac{α}{ββ^{∗}} ū^{T} x = x^{T} Ā^{T} ȳ + x^{T} (A − Ā)^{T} ȳ + \frac{αū^{T} x}{ββ^{∗}}
≥ −∥x∥ ∥A − Ā∥ ∥ȳ∥_{∗} + \frac{αū^{T} x}{ββ^{∗}}
≥ −α∥ȳ∥_{∗} + \frac{αū^{T} x}{ββ^{∗}}
≥ −\frac{αȳ^{T} z̄}{β^{∗}} + \frac{α}{β^{∗}} ∥x∥  (from Proposition 2.1)
= \frac{−α}{β^{∗}} + \frac{α}{β^{∗}} = 0  .

Thus A^{T} ȳ + \frac{αū^{T} x}{ββ^{∗}} ū ∈ C_{X}^{∗}, showing that (y, γ) = (ȳ, \frac{α}{ββ^{∗}} ) is feasible for Pα̃(d). Therefore, \frac{α}{ββ^{∗}} ≥ α̃(d). As this is true for any α > ρ(d), then ρ(d) ≥ ββ^{∗}α̃(d), completing the proof.

Proof of Theorem 3.4: Suppose that α > ρ(d). Then there exists d̄ = (Ā, b̄), with the property that ∥d̄ − d∥ ≤ α and d̄ ∈ F^{C}. From Proposition 2.1, this implies the existence of a vector ȳ ∈ C_{Y}^{∗} that satisfies Ā^{T} ȳ ∈ C_{X}^{∗}, b̄^{T} ȳ ≤ 0, and without loss of generality, z̄^{T} ȳ = 1. Let q = Ā^{T} ȳ. Then A^{T} ȳ − q = (A − Ā)^{T} ȳ + Ā^{T} ȳ − q = (A − Ā)^{T} ȳ, whereby ∥A^{T} ȳ − q∥_{∗} ≤ ∥ (A − Ā) ∥ ∥ȳ∥_{∗} ≤ α∥ȳ∥_{∗} ≤ \frac{αz̄^{T} ȳ}{β^{∗}} = \frac{α}{β^{∗}}, from Corollary 2.1. Let g = −b̄^{T} ȳ. Then g ≥ 0 and

|b^{T} ȳ + g| = |b^{T} ȳ − b̄^{T} ȳ| ≤ ∥b − b̄∥ ∥ȳ∥_{∗} ≤ \frac{αz̄^{T} ȳ}{β^{∗}} = \frac{α}{β^{∗}}. Thus (ȳ, q, g) is feasible for P_{u}(d) with

objective value max \{∥A^{T} ȳ − q∥_{∗}, |b^{T} ȳ + g|\} ≤ \frac{α}{β^{∗}}, whereby u(d) ≤ \frac{α}{β^{∗}}. As this is true for any

α > ρ(d), it is also true that u(d) ≤ \frac{ρ(d)}{β^{∗}}, which proves the first inequality of the theorem.

Next, suppose that α > u(d). Then there exists ȳ ∈ C_{Y}^{∗} , q ∈ C_{X}^{∗}, and g ≥ 0 such that z̄^{T} ȳ = 1 and ∥A^{T} ȳ − q∥_{∗} < α and |b^{T} ȳ + g| < α. Let ϵ = α − |b^{T} ȳ + g|, and note that ϵ > 0. Define d̄= (Ā, b̄) = (A − z̄(ȳ^{T} A − q^{T} ) , b − (b^{T} ȳ + g + ϵ) z̄). Then ∥Ā− A∥ = ∥z̄∥ ∥A^{T} ȳ− q∥_{∗} < α, and

∥b̄ − b∥ = ∥z̄∥ |b^{T} ȳ + g + ϵ| ≤ ∥z̄∥ (|b^{T} ȳ + g| + |ϵ|) = ∥z̄∥α = α. Therefore, ∥d̄− d∥ ≤ α. However,

Ā^{T} ȳ = A^{T} ȳ − (A^{T} ȳ − q) z̄^{T} ȳ = q ∈ C_{X}^{∗}, and b̄^{T} ȳ = b^{T} ȳ − (b^{T} ȳ + g + ϵ) z̄^{T} ȳ = −g − ϵ < 0. Thus from Proposition 2.1, d̄ ∈ F^{C}, and so ρ(d) ≤ ∥d − d̄∥ ≤ α. As this is true for any α > u(d), it is true that ρ(d) ≤ u(d), completing this proof.

Proof of Theorem 3.5: Note that P_{u}(d) in (3.6) is an instance of the program GP of the Appendix given in (A.2). To see this, we make the following associations. We let U = Y^{∗} × X^{∗} × R, and V = X^{∗}×R, where R is the set of real numbers. We let K = C_{Y}^{∗} ×C_{X}^{∗} ×R_{+}, where R_{+} is the cone of non-negative real numbers. We let d = (z̄, 0, 0) and let the gauge function f(·) : V → R be defined by F (w, α) = max {∥w∥_{∗}, |α|} for (w, α) ∈ X^{∗} × R. Then with the linear operator M given by M(y, q, g) = (−A^{T} y + q, b^{T} y + g), (3.6) is seen to be an instance of GP. The gauge dual GD of GP for this instance is precisely P_{v}(d) given in (3.7), and so we can apply Theorem A.1. If u(d) = 0, then v(d) = +∞, proving the result. If u(d) > 0, we cannot have u(d) = +∞, since P_{u}(d) always has a feasible solution. It remains to show the result when u(d) > 0, and from Theorem A.1 of the Appendix, we need only to verify that the four hypotheses of part (III) of Theorem A.1 are satisfied. Hypothesis (i) translates to the assertion that all projections of {y ∈ C_{Y}^{∗} |z̄^{T} y = 1} × C_{X}^{∗} × R_{+} are closed sets. This is true because C_{X}^{∗} and R_{+} are closed cones (whose projections will be closed sets), and {y ∈ C_{Y}^{∗} |z̄^{T} y = 1} is a closed bounded set, and so its projections will be closed sets. Hypothesis (ii) translates to sup{z̄^{T} y|y ∈ C_{Y}^{∗} } = +∞, which is true because C_{Y} is regular and z̄ ∈ intC_{Y} from Proposition 2.3. Hypothesis (iii) is true because f(·) = f(w, α) = max {∥w∥_{∗}, |α|} is a norm, and so is a closed gauge function, and hypothesis (iv) is true because f(w, α) is a norm and so its level sets are bounded. Since the hypotheses of Theorem A.1 are satisfied for the gauge program P_{u}(d), then u(d) > 0 implies u(d)v(d) = 1, proving the result.

3.2 Characterization Results when P is not consistent

In this subsection, we parallel the results of the previous subsection for the case when P is not consistent. That is, we present five different mathematical programs and we prove that the optimal value of each of these mathematical programs provides an approximation of the value of ρ(d), in the case when P is not consistent. For each of these five mathematical programs, the nature of the approximation of ρ(d) is specified in a theorem stating the result.

We motivate the development of these programs on intuitive grounds as follows. If P is not consistent, i.e.,d ∈ F^{C}, then it is elementary to see that:

ρ(d) = infimum ∥d − d̄∥
d̄
s.t.  d̄= (Ā, b̄) ∈ F ,

that is, ρ(d) measures how close the data d lies to the set of data for which P has a solution. As d ∉ F, then there is no solution x ∈ X and r > 0 to the homogenized system:

br − Ax ∈ C_{Y}
x ∈ C_{X}
r > 0
r + ∥x∥ = 1 ,

and notice in the above that we have added a normalizing constraint ”r +∥x∥ = 1.” However, when C_{Y} is regular, then the vector z̄ ∈ intC_{Y} (see Proposition 2.3), and we can measure how close d = (A, b) is to being in the set F by solving the following program:

P_{σ}(d) :

\begin{aligned}σ(d) = & minimum & γ \\ & r, x, γ \\ & s.t. & br − Ax + z̄γ ∈ C_{Y} \\ & & r + ∥x∥ = 1 \\ & & r ≥ 0 \\ & & x ∈ C_{X} & . \end{aligned}  (3.8)

Notice that σ(d) ≥ 0, since otherwise it would be true that d ∈ F (by perturbing r to make r positive if need be in P_{σ}(d)), which would violate the hypothesis of this subsection. Also notice that σ(d) < +∞, since z̄ ∈ intC_{Y} , and so P_{σ}(d) is feasible for any x ∈ C_{X} and r ≥ 0 with ∥x∥ + r = 1 and γ chosen sufficiently large. The smaller the value of σ(d) is, the closer the conditions (1.1) are to being satisfied, and so the smaller the value of ρ(d) should be. These arguments are obviously imprecise, but we will prove their validity in the following:

Theorem 3.6 If d ∈ F^{C} and C_{Y} is regular, then

β^{∗} · σ(d) ≤ ρ(d) ≤ σ(d) .

This theorem states that σ(d) approximates ρ(d) to within the factor β^{∗}, where recall the definition of β^{∗} in Definition 2.1. The proof of this theorem and all of the results of this subsection are deferred to the end of the subsection.

Remark 3.2 It should be pointed out that P_{σ}(d) is not in general a convex program, due to the non-convex constraint “r + ∥x∥ = 1”. However, in the case when X = R^{n}, if we choose the norm on X to be the L_{∞} norm, then P_{σ}(d) can be solved by solving 2n convex programs, where the construction exactly parallels that given for P_{α}(d) earlier in this section. One can easily show that σ(d) = min {σ′(d), σ′′(d)}, where :

σ′(d) = minimum minimum γ
j = 1, …, n r, x, γ
s.t.  br − Ax + z̄γ ∈ C_{Y}
−(1 − r)e ≤ x ≤ (1 − r)e
x_{j} = (1 − r)
r ≥ 0
x ∈ C_{X}  ,

and

σ′′(d) = minimum minimum γ
j = 1, …, n r, x, γ
s.t.  br − Ax + z̄γ ∈ C_{Y}
−(1 − r)e ≤ x ≤ (1 − r)e
x_{j} = −(1 − r)
r ≥ 0
x ∈ C_{X}  .

The next mathematical program is obtained by considering the following normalized version of the infeasibilty conditions (2.2):

HD :

\begin{matrix}A^{T} y ∈ C_{X}^{∗} \\ −b^{T} y ≥ 0 \\ y ∈ C_{Y}^{∗} \\ z̄^{T} y = 1 & . \end{matrix}

One can think of z̄^{T} y as a linear approximation of ∥y∥_{∗} over the cone C_{Y}^{∗}, see Corollary 2.1. (In fact, the construction of β^{∗} and z̄ in Definition 2.1 and Proposition 2.3 is such that z̄^{T} y is the ”best” linear approximation of ∥y∥_{∗} over the cone C_{Y}^{∗}.) Now, an “internal view” of ρ(d) is that ρ(d) measures the extent to which the data d = (A, b) can be altered and yet (2.2) will still be feasible for the new system. A modification of this view is that ρ(d) measures the extent to which the system (2.2) can be modified while still ensuring the feasibility of the system. Consider the following program: P_{δ}(d) :

δ(d) = minimum maximum θ
v ∈ X^{∗}  y, θ
∥v∥_{∗} ≤ 1  s.t.  A^{T} y − vθ ∈ C_{X}^{∗}
−b^{T} y − θ ≥ 0
y ∈ C_{Y}^{∗}
z̄^{T} y = 1  .

(3.9)

Then δ(d) is the largest scaling factor θ such that for any v with ∥v∥_{∗} ≤ 1, (−vθ) can be added to the first inclusion of HD and θ can be added to the inequality in HD while still ensuring its feasibility. We will prove:

Theorem 3.7 If d ∈ F^{C} and C_{Y} is regular, then σ(d) = δ(d), and so

β^{∗} · δ(d) ≤ ρ(d) ≤ δ(d) .

Three remarks are in order here. First, the theorem asserts that σ(d) = δ(d), and in fact the proof of the theorem will show that P_{δ}(d) can be obtained from P_{σ}(d) by dualizing on a subset of the variables and constraints of P_{σ}(d), i.e., P_{σ}(d) and P_{δ}(d) are partial duals of one another. Second, there is an underlying geometry in P_{σ}(d). To see this, let

T = {(v, γ) ∈ X^{∗} × R| there exists y ∈ C_{Y}^{∗} satisfying A^{T} y − v ∈ C_{X}^{∗}, −b^{T} y − γ ≥ 0, z̄^{T} y = 1}.

(3.10)

Then P_{δ}(d) can alternatively be written as:

\begin{aligned}δ(d) = & maximum & θ \\ & θ \\ & s.t. & \{(v, γ) ∈ X^{∗} × R|max\{∥v∥_{∗}, |γ|\} ≤ θ\} ⊂ T & , \end{aligned}  (3.11)

and we see that δ(d) is the radius of the largest ball centered at (v, γ) = (0, 0) and contained in T, where the norm is max{∥v∥_{∗}, |γ|}. Third, if we replace the normalizing linear constraint “z̄^{T} y = 1” of P_{δ}(d) by the norm constraint “∥y∥_{∗} = 1,” then the modified program is analogous to the construction of Renegar (as applied to the system (2.2)) for characterizing the distance to ill-posedness (see Theorem 3.5 of [13]) when P is not consistent. The modified program is:

P_{π}(d) :

π(d) = minimum maximum θ
v ∈ X^{∗}  y, θ
∥v∥_{∗} ≤ 1  s.t.  A^{T} y − vθ ∈ C_{X}^{∗}
−b^{T} y − θ ≥ 0
y ∈ C_{Y}^{∗}
∥y∥_{∗} = 1  ,

and one can in fact show that π(d) = ρ(d) when d ∈ F^{C}. We will not prove this here; rather it is our intent to show the connection to the results in [13].

One problem with P_{σ}(d) is that P_{σ}(d) is generally nonconvex, due to the constraint “r + ∥x∥ = 1.” When C_{X} is also regular, then from Corollary 2.1 the linear function ū^{T} x is a “best” linear approximation of ∥x∥ on C_{X}, and if we replace ”r + ∥x∥ = 1” by “r + ū^{T} x = 1” in P_{σ}(d) we obtain:

Pσ̃(d) :

\begin{aligned}σ̃(d) = & minimum & γ \\ & r, x, γ \\ & s.t. & br − Ax + z̄γ ∈ C_{Y} \\ & & r + ū^{T} x = 1 \\ & & r ≥ 0 \\ & & x ∈ C_{X} & . \end{aligned}  (3.12)

Replacing the norm constraint by its linear approximation will reduce (by a constant) the extent to which the program computes an approximation of ρ(d), and the analog of Theorem 3.6 becomes:

Theorem 3.8 If d ∈ F^{C} and both C_{X} and C_{Y} are regular, then

β^{∗}β · σ̃(d) ≤ ρ(d) ≤ σ̃(d).

Notice that a very nice feature of Pσ̃(d) is that it is a convex program.

The fourth mathematical program of this subsection is derived by once again measuring the extent to which the data d = (A, b) does not admit a solution of (1.1). In the case when C_{X} is regular, consider the program:

P_{g}(d) :

\begin{aligned}g(d) = & minimum & ∥br − Ax − w∥ \\ & x, r, w \\ & s.t. & x ∈ C_{X} \\ & & r ≥ 0 \\ & & w ∈ C_{Y} \\ & & ū^{T} x + r = 1 & . \end{aligned}  (3.13)

If d = (A, b) were in F, then it would be true that g(d) = 0. The nonnegative quantity g(d) measures the extent to which (1.1) is not feasible. The smaller the value of g(d) is, the closer the conditions (1.1) are to being satisfied, and so the smaller the value of ρ(d) should be. These arguments are imprecise, but the next theorem validates the intuition of this line of thinking:

Theorem 3.9 If d ∈ F^{C} and C_{X} is regular, then

β · g(d) ≤ ρ(d) ≤ g(d) .

Therefore, g(d) approximates ρ(d) to within the factor β, where β is defined in Definition 2.1.

Notice that P_{g}(d) is also a convex program, which is convenient. If the constraint “ū^{T} x+r = 1” in P_{g}(d) is replaced with the norm constraint “∥x∥+r = 1,” one obtains the nonconvex program:

P_{k}(d) :

k(d) = minimum ∥br − Ax − w∥
x, r, w
s.t.  x ∈ C_{X}
r ≥ 0
w ∈ C_{Y}
∥x∥ + r = 1  ,

and one can prove (although we will not do this here) that P_{k}(d) can be derived as a partial dual of P_{π}(d), and so k(d) = π(d) = ρ(d) as mentioned earlier.

Returning to P_{g}(d), notice that P_{g}(d) is a gauge program. For the program P_{g}(d), its dual gauge program is given by:

P_{h}(d) :

\begin{aligned}h(d) = & minimum & ∥y∥_{∗} \\ & y \\ & s.t. & A^{T} y − ū ∈ C_{X}^{∗} \\ & & −b^{T} y − 1 ≥ 0 \\ & & y ∈ C_{Y}^{∗} & . \end{aligned}  (3.14)

In general, dual gauge programs will have the product of their optimal values equal to 1, as the last theorem of this subsection indicates:

Theorem 3.10 If d ∈ F^{C} and C_{X} is regular, then g(d) · h(d) = 1 whenever g(d) > 0, and

\frac{β}{h(d)} ≤ ρ(d) ≤ \frac{1}{h(d)} .

Note that P_{h}(d) is also a convex program. One can interpret P_{h}(d) as measuring the extent to which (2.2) has a solution that is interior to the cone C_{X}^{∗} and that satisfies b^{T} y ≤ 0 strictly. To see this, note from Proposition 2.3 that ū ∈ intC_{X}^{∗}, and so P_{h}(d) will only be feasible if the first and the third conditions of (2.2) are satisfied in their interior. The more interior a solution there is, the smaller y can be scaled and still satisfy A^{T} y − ū ∈ C_{Y} and −b^{T} y − 1 ≥ 0. One would then expect ρ(d) to be inversely proportional to h(d), as Theorem 3.5 indicates.

The proofs of these last five theorems are given below.

Proof of Theorem 3.6: Suppose that α > σ(d) is given. Then there exists a feasible solution (r̄, x̄, γ̄) of P_{σ}(d) with γ̄ < α, i.e., br̄ − Ax̄ + z̄γ̄ ∈ C_{Y} , r̄ + ∥x̄∥ = 1, r̄ ≥ 0, and x̄ ∈ C_{X}. From Proposition 2.2, there exists (v, t) ∈ X^{∗}×R satisfying v^{T} x̄+tr̄ = r̄+∥x̄∥ = 1, and max {∥v∥_{∗}, |t|} = 1. Let us then define d̄ = (Ā, b̄) = (A − αz̄v^{T} , b + αz̄t). Then ∥Ā − A∥ = α∥z̄∥ ∥v∥_{∗} ≤ α and ∥b̄−b∥ = α|t| ∥z̄∥ ≤ α, so ∥d̄−d∥ ≤ α. However, b̄r̄−Āx̄ = br̄+αz̄tr̄−Ax̄+αz̄v^{T} x̄ = br̄−Ax̄+αz̄ = br̄ − Ax̄ + γ̄z̄ + (α − γ̄)z̄ ∈ int C_{Y}. Thus b̄(r̄ + ϵ) − Ax̄ ∈ C_{Y} for ϵ > 0 and sufficiently small, and so after dividing this expression by r̄ + ϵ, we see that d̄ = (Ā, b̄) ∈ F. Therefore, ρ(d) ≤ α. Since this is true for any α > σ(d), it is also true that ρ(d) ≤ σ(d), proving the second inequality of the theorem.

To prove the first inequality of the theorem, let α > ρ(d) be chosen. Then there exists d̄ = (Ā, b̄) for which ∥d − d̄∥ ≤ α, and d̄ ∈ F, whereby there exists x̄ ∈ C_{X} and r̄ > 0 satisfying b̄r̄ − Āx̄ ∈ C_{Y}, and ∥x̄∥ + r̄ = 1. Thus for any y ∈ C_{Y}^{∗} that satisfies ∥y∥_{∗} = 1,

y^{T} (br̄ − Ax̄ + \frac{α}{β^{∗}} z̄) = y^{T} (b̄r̄ − Āx̄ + (b − b̄)r̄ − (A − Ā)x̄ + \frac{α}{β^{∗}} z̄)
≥ −∥b − b̄∥r̄ − ∥Ā − A∥ ∥x̄∥ + \frac{α}{β^{∗}} z̄^{T} y
≥ −α(r̄ + ∥x̄∥) + α  (from Corollary 2.1)
= 0  .

Therefore, (br̄ − Ax̄ + \frac{α}{β^{∗}} z̄) ∈ C_{Y} , ∥x̄∥ + r̄ = 1, and x̄ ∈ C_{X} and r̄ ≥ 0. Thus (x, r, γ) = (x̄, r̄, \frac{α}{β^{∗}} ) is feasible for P_{σ}(d), whereby σ(d) ≤ \frac{α}{β^{∗}}. As this is true for any α > ρ(d), it must be true that

σ(d) ≤ \frac{ρ(d)}{β^{∗}}, completing the proof.

Proof of Theorem 3.7: Consider the program P_{σ}(d) given in (3.8). Because d ∈ F^{C}, i.e., (1.1) has no solution, there can be no feasible solution (x, r, γ) of P_{σ}(d) with γ < 0 (for if so, then br − Ax ∈ int C_{Y} , r ≥ 0, x ∈ C_{X}, and so for ϵ > 0 and sufficiently small b(r + ϵ) − Ax ∈ C_{Y}, and rescaling would give a solution \frac{x}{r+ϵ} of (1.1)). Therefore, we can amend P_{σ}(d) by replacing the constraint “∥x∥ + r = 1” by ”∥x∥ + r ≥ 1”, so that

σ(d) = minimum γ
r, x, γ
s.t.  br − Ax + z̄γ ∈ C_{Y}
∥x∥ ≥ 1 − r
r ≥ 0
x ∈ C_{X}  .

However, ∥x∥ ≥ 1 − r if and only if there exists v ∈ X^{∗} that satisfies v^{T} x ≥ 1 − r and ∥v∥_{∗} ≤ 1 (see (2.4)), and so we can write:

σ(d) = minimum γ
v, r, x, γ
s.t.  br − Ax + z̄γ ∈ C_{Y}
v^{T} x ≥ 1 − r
r ≥ 0
x ∈ C_{X}
v ∈ X^{∗}
∥v∥_{∗} ≤ 1  .

We then separate this problem into the two-level optimization problem:

σ(d) = minimum minimum γ
v ∈ X^{∗}  r, x, γ
∥v∥_{∗} ≤ 1
s.t.  br − Ax + z̄γ ∈ C_{Y}
r + v^{T} x ≥ 1
r ≥ 0
x ∈ C_{X}  .

Next note that the right-most (or bottom level) problem is an instance of ND of the Appendix given in (A.9), where K_{2}^{∗} = C_{Y} , K_{1}^{∗} = C_{X} ×R_{+}, y = (x, r), M^{T} y = Ax−br, f = z̄, and w = (v, 1). The dual problem associated with ND is given by NP in (A.8), which translates to:

v_{P} = maximum θ
y, θ
s.t.  A^{T} y − θv ∈ C_{X}^{∗}
−b^{T} y − θ ≥ 0
z̄^{T} y = 1
y ∈ C_{Y}^{∗}  .

Furthermore, since d ∈ F^{C}, this program is feasible (set θ = 0 and apply Proposition 2.1), whereby the hypotheses of Theorem A.2 are satisfied, and so v_{P} = v_{D} and we can replace the bottom-level program by its dual, so

σ(d) = minimum maximum θ
v ∈ X^{∗}  y, θ
∥v∥_{∗} ≤ 1
s.t.  A^{T} y − θv ∈ C_{X}^{∗}
−b^{T} y − θ ≥ 0
y ∈ C_{Y}^{∗}
z̄^{T} y = 1  ,

which is precisely δ(d), so σ(d) = δ(d).

Proof of Theorem 3.8: Suppose that α > ρ(d) is given. Then there exists a data instance d̄ = (Ā, b̄) with ∥d − d̄∥ ≤ α for which d̄ ∈ F. Then by rescaling if necessary, there exists x̄ ∈ C_{X} and r̄ > 0 such that b̄r̄ − Āx̄ ∈ C_{Y} and ū^{T} x̄ + r̄ = 1. We now show that (br̄ − Ax̄ + \frac{α}{β^{∗}β} z̄) ∈ C_{Y}. To see this, note that for any y ∈ C_{Y}^{∗} that satisfies ∥y∥_{∗} = 1, then

y^{T} (br̄ − Ax̄ + (\frac{α}{β^{∗}β} ) z̄) = y^{T} (b̄r̄ − Āx̄ + (b − b̄)r̄ − (A − Ā)x̄ + \frac{α}{β^{∗}β} z̄)
≥ −∥b − b̄∥r̄ − ∥A − Ā∥ ∥x̄∥ + \frac{α}{β^{∗}β} z̄^{T} y
≥ −α(r̄ + ∥x̄∥) + \frac{α∥y∥_{∗}β^{∗}}{β^{∗}β}  (from Corollary 2.1)
≥ −α (r̄ + \frac{ū^{T} x̄}{β}) + \frac{α}{β}
≥ −\frac{α}{β}(r̄ + ū^{T} x̄) + \frac{α}{β} = 0  .

Therefore (br̄ − Ax̄ + (\frac{α}{β^{∗}β} ) z̄) ∈ C_{Y}. Thus (x, r, γ) = (x̄, r̄, \frac{α}{β^{∗}β} ) is feasible for Pσ̃(d), and so

σ̃(d) ≤ \frac{α}{β^{∗}β}. As this is true for any α > ρ(d), then σ̃(d) ≤ \frac{ρ(d)}{β^{∗}β}, proving the first inequality of the theorem.

Next, suppose that α > σ̃(d) is given. Then there exists a feasible solution (x̄, r̄, γ̄) of Pσ̃(d) with γ̄ < α, i.e., x̄ ∈ C_{X}, r̄ ≥ 0, γ̄ < α, br̄ − Ax̄ + γ̄z̄ ∈ C_{Y}, and r̄ + ū^{T} x̄ = 1. Let d̄ = (Ā, b̄) = (A−αz̄ū^{T} , b+αz̄). then ∥Ā−A∥ = α∥z̄∥ ∥ū∥_{∗} = α, and ∥b̄−b∥ = α∥z̄∥ = α, whereby ∥d̄−d∥ = α. However, b̄r̄ − Āx̄ = br̄ − Ax̄ + αz̄(r̄ + ū^{T} x̄) = br̄ − Ax̄ + αz̄ = br̄ − Ax̄ + γ̄z̄ + (α − γ̄)z̄ ∈ int C_{Y}. Then b̄(r̄+ ϵ) − Āx̄ ∈ C_{Y} for ϵ > 0 and sufficiently small, so x = \frac{x̄}{(r̄+ϵ)} satisfies for (1.1) for the data d̄= (Ā, b̄), i.e., d̄∈ F. Thus ρ(d) ≤ ∥d − d̄∥ = α. Since this is true for any α > σ̃(d), it is also true that ρ(d) ≤ σ̃(d), completing the proof.

Proof of Theorem 3.9: Suppose that α > ρ(d) is given. Then there exists d̄ = (Ā, b̄) ∈ F that satisfies ∥d̄ − d∥ ≤ α. Thus, by rescaling if necessary, there exists x̄ ∈ C_{X} and r̄ > 0 such that b̄r̄ − Āx̄ ∈ C_{Y} and ū^{T} x̄ + r̄ = 1. Let w = b̄r̄ − Āx̄. Then w ∈ C_{Y} and br̄ − Ax̄ − w = b̄r̄−Āx̄−w +(b−b̄)r̄−(A−Ā)x̄ = (b−b̄)r̄−(A−Ā)x̄, so ∥br̄−Ax̄−w∥ ≤ ∥b−b̄∥r̄+∥A−Ā∥ ∥x̄∥ ≤ αr̄ + α∥x̄∥ ≤ αr̄ + α (\frac{ū^{T} x̄}{β}) ≤ \frac{α}{β}, from Corollary 2.1. Therefore, (x̄, r̄, w) is feasible for P_{g}(d) with objective value at most \frac{α}{β}, and so g(d) ≤ \frac{α}{β}. As this is true for any α > ρ(d), it must be true that

g(d) ≤ \frac{ρ(d)}{β}, which proves the first part of the theorem.

Next, suppose that α > g(d) is given. Then there exists (x, r, w) feasible for P_{g}(d) with objective value ∥br−Ax−w∥ < α. Then from (3.13), (x, r, w) satisfies x ∈ C_{X}, r ≥ 0, ū^{T} x+r = 1, and w ∈ C_{Y}. For ϵ > 0, define (x̄, r̄) = (\frac{x}{1+ϵ}, \frac{r+ϵ}{1+ϵ}). Then (x̄, r̄, w) is feasible for P_{g}(d), and we can always choose ϵ sufficiently small that ∥br̄ − Ax̄ − w∥ ≤ α. Let d̄ = (Ā, b̄) = (A − (Ax̄ − br̄ + w)ū^{T} , b + (Ax̄ − br̄ + w)). Then ∥Ā−A∥ ≤ α and ∥b̄−b∥ ≤ α, so that ∥d̄−d∥ ≤

α. However, b̄r̄ − Āx̄ = br̄ − Ax̄ + (Ax̄ − br̄ + w) (ū^{T} x̄ + r̄) = w ∈ C_{Y}. Since r̄ > 0, then b̄ − Ā (\frac{x̄}{r̄}) ∈ C_{Y}, and we see that d̄ = (Ā, b̄) ∈ F. This implies that ρ(d) ≤ ∥d − d̄∥ ≤ α. As this is true for any α > g(d), it is also true that ρ(d) ≤ g(d), proving the theorem.

Proof of Theorem 3.10: Note that P_{g}(d) of (3.13) is an instance of the program GP of the Appendix given in (A.2). To see this, first change the notation of “x” in GP to “x̃” and then x̃ = (x, r, w), Mx̃ = Ax − br + w, f(·) = ∥ · ∥, K = C_{X} × R_{+} × C_{Y}, and d = (ū, 1, 0). The gauge dual GD of GP for this instance is precisely P_{h}(d) given in (3.14), and so we can apply Theorem A.2. If g(d) = 0, then h(d) = +∞, proving the result. If g(d) > 0, we cannot have g(d) = +∞, since P_{g}(d) always has a feasible solution. It remains to show the result when g(d) > 0, and from Theorem A.1 of the Appendix, we need only to verify that the four hypotheses of Theorem A.1 are satisfied. Hypothesis (i) translates to the assertion that all projections of {(x, r, w) ∈ C_{X} ×R_{+}×C_{Y} |ū^{T} x+r = 1} are closed sets, which is true because {(x, r) ∈ C_{X} × R_{+}|ū^{T} x + r = 1} is a closed and bounded set (and hence its projections will be closed sets), and C_{Y} is a closed convex cone (and so its projections will be closed sets). Hypothesis (ii) translates to sup{ū^{T} x + r|x ∈ C_{X}, r ∈ R_{+}} = +∞, which is true since one can set x = 0 and r arbitrarily large. Hypotheses (iii) and (iv) are true since f(·) = ∥ · ∥ is a closed gauge function with bounded level sets because ∥ · ∥ is a norm. Since the hypotheses of Theorem A.1 are satisfied, then g(d) > 0 implies g(d) · h(d) = 1, proving the theorem.

4 Bounds on Radii of Contained and Intersecting Balls

In this section, we develop four results concerning the radii of certain inscribed balls in the feasible region of the system (1.1) or, in the case when P is not consistent, of the alternative system (2.2). These results are stated as Lemmas 4.1, 4.2, 4.3, and 4.4 of this section. While these results are of an intermediate nature, it is nevertheless useful to motivate them, which we do now, by thinking in terms of the ellipsoid algorithm for finding a point in a convex set.

Consider the ellipsoid algorithm for finding a feasible point in a convex set C. Roughly speaking, the main ingredients that are needed to apply the ellipsoid algorithm and to produce a complexity bound on the number of iterations of the ellipsoid algorithm are the existence of:

\begin{matrix}(i) & a ball B(x̂, r) with the property that B(x̂, r) ⊂ C , \\ (ii) & a ball B(0, R) with the property that B(x̂, r) ⊂ B(0, R) , and \\ (iii) & an upper bound on the ratio R/r . \end{matrix}

With these three ingredients, it is then possible to produce a complexity bound on the number of iterations of the ellipsoid algorithm, which will be O(n^{2} ln(R/r)). In addition, it is also convenient to have the following:

\begin{matrix}(iv) & a lower bound on the radius r of the contained ball B(x̂, r), and \\ (v) & an upper bound on the radius R of the initial ball B(0, R) . \end{matrix}

In the bit model of complexity as applied to linear inequality systems, one is usually able to set r = (1/n)2^{−L} and R = n2^{L}, where L is the number of bits needed to represent the system. (Of course, these values of r and R break down when the system is degenerate (in our parlance, “ill=posed” ) in which case the system must be perturbed first.)

By analogy for the problem P considered herein in (1.1), the convex set in mind is the set X_{d}, which is the feasible region of the problem P, and 2^{L} is generally replaced by the condition measure of d = (A, b), denoted C(d), which is defined to be

C(d) = \frac{∥d∥}{ρ(d)} ,

see Renegar [13]. The results in this section will be used in Section 5 to demonstrate in general that we can find a point x̂ ∈ X_{d} and radii r and R with the five properties below, that are analogs of the five properties listed above:

\begin{matrix}(i) & B(x̂, r) ⊂ X_{d} \\ (ii) & B(x̂, r) ⊂ B(0, R) \\ (iii) & R/r ≤ O(n C(d)) = O (\frac{n∥d∥}{ρ(d)}) \\ (iv) & r ≥ 1/(O(n C(d))) = Ω (\frac{ρ(d)}{n∥d∥}) , and \\ (v) & R ≤ O(n C(d)) = O (\frac{n∥d∥}{ρ(d)}) . \end{matrix}

Here the quantity 2^{L} is roughly replaced by C(d) .

The above remarks pertain to the the case when P is consistent, i.e., when (1.1) has a solution. When (1.1) is not consistent, then the convex set in mind is the feasible region for the alternative system (2.2), denoted by Y_{d}. The results in this section will also be used in Section 5 to demonstrate in general that we can find a point ŷ in Y_{d} and radii r and R with the three properties below, that are analogs of the first three properties listed above:

\begin{matrix}(i) & B(ŷ, r) ⊂ Y_{d} \\ (ii) & B(ŷ, r) ⊂ B(0, R) \\ (iii) & R/r ≤ O(m C(d)) = O (\frac{m∥d∥}{ρ(d)}) . \end{matrix}

Because the system (2.2) is homogeneous, it makes little sense to bound r from below or R from above, as all constructions can be scaled by any positive quantity. Therefore properties (iv) and (v) are not relevant.

The results in this section are rather technical, and their proofs are unfortunately quite long. The reader may first want to read Section 5 before pondering the results in this Section in detail.

We first examine the case when (1.1) is consistent, in which case the feasible region X_{d} = {x ∈ X|b − Ax ∈ C_{Y} , x ∈ C_{X}} is nonempty.

Lemma 4.1 Suppose that d ∈ F and C_{Y} is regular. If ρ(d) > 0, then there exists x̂ ∈ X_{d} and PROPERTIES OF THE DISTANCE TO ILL-POSEDNESS 28 positive scalars r_{1} and R_{1} satisfying:

(i) B (x̂, r_{1}) ⊂ {x ∈ X|b − Ax ∈ C_{Y} }  (4.1)
(ii) B (x̂, r_{1}) ⊂ B (0, R_{1})  (4.2)
(iii) \frac{R_{1}}{r_{1}} ≤ \frac{3∥d∥}{β^{∗}ρ(d)}
(iv) r_{1} ≥ \frac{β^{∗}ρ(d)}{3∥d∥}
and (v) R_{1} ≤ \frac{3∥d∥}{β^{∗}ρ(d)} .

In the case when C_{X} = X, (4.1) states that the feasible region X_{d} contains a ball of radius r_{1}, and (4.2) states that this ball does not lie more than the distance R_{1} from the origin. Furthermore, \frac{R_{1}}{r_{1}} ≤ \frac{3∥d∥}{β^{∗}ρ(d)}. In order to prove Lemma 4.1, we first prove: Proposition 4.1 ρ(d) ≤ ∥d∥ . Proof: If d ∈ F (respectively, F^{C}), then θd ∈ F (respectively, F^{C}) for all θ > 0. Therefore, d̄= (Ā, b̄) = (0, 0) ∈ B = cl(F) ∩ cl (F^{C}), and so ρ(d) ≤ ∥d − d̄∥ = ∥d − 0∥ = ∥d∥. Proof of Lemma 4.1: For any w ∈ C_{Y}^{∗} with ∥w∥_{∗} = 1, we have

z̄^{T} w + \frac{β^{∗}b^{T} w}{∥d∥} ≥ β^{∗} − \frac{β^{∗}∥d∥ ∥w∥_{∗}}{∥d∥} = 0 ,

so that \frac{1}{2} (z̄ + \frac{β^{∗}}{∥d∥}b) ∈ C_{Y}. Now let (x̃, r̃) solve P_{v}(d), and let

x̂ = \frac{x̃}{r̃ + \frac{β^{∗}}{δ∥d∥}} = \frac{x̃}{δ} ,

where δ = r̃ + \frac{β^{∗}}{2∥d∥}. Let q = br̃ − Ax̃ − z̄. Then q ∈ C_{Y} and we have br̃ − Ax̃ + \frac{β^{∗}}{2∥d∥}b − \frac{1}{2} z̄ = z̄+ q + \frac{β^{∗}}{2∥d∥}b − \frac{1}{2} z̄ = \frac{1}{2} (z̄ + \frac{β^{∗}}{∥d∥}b) + q ∈ C_{Y}, so that δb − Ax̃ − \frac{1}{2} z̄ ∈ C_{Y}, whereby b − Ax̂ − \frac{1}{2δ} z̄ ∈ C_{Y}. Thus x̂ ∈ C_{X} and b − Ax̂ ∈ C_{Y}, so x̂ ∈ X_{d}. Let r_{1} = \frac{β^{∗}}{2δ∥d∥}. Then if ∥x − x̂∥ ≤ r_{1}, we have

\begin{aligned}b − Ax = b − Ax̂ + A(x̂ − x) & = \frac{1}{δ} (δb − Ax̃ − \frac{1}{2} z̄) + \frac{1}{2δ} z̄ + A(x̂ − x) \\ & = y + \frac{1}{2δ} z̄ + A(x̂ − x) \end{aligned}

where y ∈ C_{Y} . Thus for any w ∈ C_{Y}^{∗} with ∥w∥_{∗} = 1,

\begin{aligned}w^{T} (b − Ax) & ≥ \frac{1}{2δ} z̄^{T} w + w^{T} A(x̂ − x) & ≥ \frac{β^{∗}}{2δ} − ∥w∥_{∗}∥A∥ ∥x̂ − x∥ \\ & ≥ \frac{β^{∗}}{2δ} − ||d∥r_{1} & = 0 . \end{aligned}

Therefore b − Ax ∈ C_{Y}, proving (i).

Next, let R_{1} = \frac{v(d)}{δ} + r_{1}.

Then

\frac{R_{1}}{r_{1}} = \frac{v(d)}{δr_{1}} + 1 ≤ \frac{v(d)}{δr_{1}} + \frac{∥d∥}{ρ(d)}  (from Proposition 4.1)
= \frac{2∥d∥}{β^{∗}u(d)} + \frac{∥d∥}{ρ(d)}  (from Theorem 3.5)
≤ \frac{3∥d∥}{β^{∗}ρ(d)}  ,  (from Theorem 3.4)

proving (iii). To compute the bounds in (iv) and (v), notice first that δ = r̃+ \frac{β^{∗}}{2∥d∥} ≥ \frac{β^{∗}}{2∥d∥}, so that r_{1} ≤ 1. Therefore,

R_{1} = \frac{v(d)}{δ} + r_{1} ≤ \frac{2∥d∥v(d)}{β^{∗}} + 1
≤ \frac{2∥d∥}{β^{∗}u(d)} + \frac{∥d∥}{ρ(d)}  (from Theorem 3.5 and Proposition 4.1)
≤ \frac{3∥d∥}{β^{∗}ρ(d)}  ,  (from Theorem 3.4)

proving (v). We also have:

δ = r̃ + \frac{β^{∗}}{2∥d∥} ≤ v(d) + \frac{β^{∗}}{2∥d∥}  (from (3.7))
≤ v(d) + \frac{1}{2ρ(d)}  (from Proposition 4.1)
≤ \frac{3}{2ρ(d)}  .  (from Theorem 3.5)

Therefore, r_{1} = \frac{β^{∗}}{2δ∥d∥} ≥ \frac{β^{∗}ρ(d)}{3∥d∥}, proving (iv). Finally, observe that ∥x̂∥ + r_{1} = \frac{∥x̃∥}{δ} + r_{1} ≤ \frac{v(d)}{δ} + r_{1} = R_{1}, which proves (ii).

We next have:

Lemma 4.2 Suppose that d ∈ F and C_{X} is regular. If ρ(d) > 0, then there exists x̂ ∈ X_{d} and positive scalars r_{2} and R_{2} satisfying:

(i) B (x̂, r_{2}) ⊂ C_{X}  (4.3)
(ii) B (x̂, r_{2}) ⊂ B (0, R_{2})  (4.4)
(iii) \frac{R_{2}}{r_{2}} ≤ \frac{(2n+5)∥d∥}{β^{2}ρ(d)}
(iv) r_{2} ≥ \frac{ββ̄ρ(d)}{2(n+2)∥d∥}
and (v) R_{2} ≤ \frac{(2n+6)∥d∥}{β^{2}ρ(d)} .

In the case when C_{Y} = {0}, we can intersect both sides of (4.3) with the affine subspace of x ∈ X satisfying Ax = b. Then (4.3) will imply that the feasible region X_{d} contains a ball of radius r_{2} intersected with affine subspace of x ∈ X satisfying Ax = b. Furthermore, (4.4) states that this ball does not lie more than a distance R_{2} from the origin. Furthermore, \frac{R_{2}}{r_{2}} ≤ \frac{(2n+5)∥d∥}{ρ(d)β^{2}β̄}.

Proof of Lemma 4.2: Let us consider the set

C = {(x, r) ∈ X × R|x ∈ C_{X}, r ≥ 0, ū^{T} x + r = 1, br − Ax ∈ C_{Y} } .  (4.5)

Then C is closed, bounded and convex, and there is Löwner-John pair of ellipsoids for C (see [4]). Therefore, letting (x̃, r̃) be the common center of both ellipsoids, then (x̃, r̃) ∈ C, and it will be true that for any w ∈ X^{∗} and any scalar g, that

\begin{aligned}w^{T} x̃ + gr̃ − & minimum w^{T} x + gr & ≥ \frac{1}{n+1} & (maximum w^{T} x + gr − (w^{T} x̃ + gr̃)) . \\ & s.t. (x, r) ∈ C & & s.t. (x, r) ∈ C \end{aligned} (4.6)

Let v = \frac{−bw(d)}{∥d∥}. Then ∥v∥ ≤ w(d), and from (3.3) and (3.4) there exists (x′, r′) satisfying x′ ∈

C_{X}, r′ ≥ 0, br′ − Ax′ + \frac{bw(d)}{∥d∥} = q ∈ C_{Y}, and ū^{T} x′ + r′ = 1. Let

(x′′, r′′) = \frac{(x′, r′ + \frac{w(d)}{∥d∥})}{1 + \frac{w(d)}{∥d∥}} .  (4.7)

Then (x′′, r′′) ∈ C, and r′′ = \frac{r′+ \frac{w(d)}{∥d∥}}{1+ \frac{w(d)}{∥d∥}} > 0, since ρ(d) > 0 and applying Theorem 3.2. If we

then set w = 0 and g = 1 in (4.6), we obtain

r̃ ≥ \frac{1}{n + 1} (r′′ − r̃) ,  (4.8)

using the facts that minimum{ r|(x, r) ∈ C} ≥ 0 and maximum{ r|(x, r) ∈ C} ≥ r′′. Therefore,

r̃ ≥ \frac{r′′}{n + 2} > 0 .  (4.9)

We now let x̂ = \frac{x̃}{r̃}. Then x̂ ∈ C_{X} and b − Ax̂ ∈ C_{Y} from (4.5). Thus x̂ ∈ X_{d}.

We next demonstrate the following:

for any w ∈ C_{X}^{∗} with ∥w∥_{∗} = 1, w^{T} x̃ ≥ \frac{w(d)β̄}{(∥d∥ + w(d)) (n + 2)}.  (4.10)

In order to prove (4.10), we choose any w ∈ C_{X}^{∗} with ∥w∥_{∗} = 1. Then, from (2.16), there exists x̄ ∈ C_{X} such that ∥x̄∥ = 1 and w^{T} x̄ ≥ β̄. If we set v = \frac{Ax̄w(d)}{∥Ax̄∥}, then ∥v∥ = w(d) and from (3.4),

there exists (x̄′, r̄′) such that x̄′ ∈ C_{X}, r̄′ ≥ 0, ū^{T} x̄′ + r̄′ = 1, and br̄′ − Ax̄′ − \frac{Ax̄w(d)}{∥Ax̄∥} = q ∈ C_{Y}. If we then set

(x̄′′, r̄′′) = \frac{(x̄′ + \frac{x̄w(d)}{∥Ax̄∥}, r̄′)}{1 + \frac{w(d)x̄^{T} ū}{∥Ax̄∥}} ,  (4.11)

then br̄′′ − Ax̄′′ ∈ C_{Y} , x̄′′ ∈ C_{X}, r̄′′ ≥ 0, and ū^{T} x̄′′ + r̄′′ = 1, so that (x̄′′, r̄′′) ∈ C. Therefore, if we choose g = 0 in (4.6), we obtain

\begin{aligned}w^{T} x̃ ≥ w^{T} x̃ − & minimum w^{T} x & ≥ (\frac{1}{n+1}) & (maximum w^{T} x − w^{T} x̃) \\ & (x, r) ∈ C & & (x, r) ∈ C \\ & & ≥ (\frac{1}{n+1}) & (w^{T} x̄′′ − w^{T} x̃) \\ & & = (\frac{1}{n+1}) & (^{\frac{(w^{T} x̄′+ \frac{w^{T} x̄w(d)}{∥Ax̄∥})}{1+ \frac{w(d)x̄^{T} ū}{∥Ax̄∥}}} − w^{T} x̃) , \end{aligned}  (4.12)

where the first inequality follows since w^{T} x ≥ 0 for any x ∈ C_{X} since w ∈ C_{X}^{∗}. Rearranging (4.12) we obtain

\begin{matrix}w^{T} x̃ ≥ & \frac{w^{T} x̄w(d)}{(n+2)(∥Ax̄∥+w(d)x̄^{T} ū)} & & (since w^{T} x̄′ ≥ 0) \\ ≥ & \frac{β̄w(d)}{(n+2)(∥d∥+w(d))} & , & (from (2.14)) \end{matrix}

which demonstrates (4.10).

We now set r_{2} = \frac{β̄w(d)}{r̃(n+2)(∥d∥+w(d))} and prove (4.3). It suffices to prove that if ∥x − x̂∥ ≤ r_{2}, then w^{T} x ≥ 0 for any w ∈ C_{X}^{∗} that satisfies ∥w∥_{∗} = 1. To verify this, suppose w ∈ C_{X}^{∗} and ∥w∥_{∗} = 1. Then w^{T} x = w^{T} (x − x̂) + w^{T} x̂ ≥ −∥x − x̂∥ + \frac{w^{T} x̃}{r̃} ≥ −r_{2} + \frac{β̄w(d)}{(n+2)(∥d∥+w(d))r̃} = 0, which shows (4.3).

To prove (iv), note that since r̃ ≤ 1, then

r_{2} ≥ \frac{β̄w(d)}{(n+2)(∥d∥+w(d))}
≥ \frac{β̄ρ(d)}{(n+2)(∥d∥+ \frac{∥d∥}{β})} (from Theorem 3.2 and Proposition 4.1)
= \frac{ββ̄ρ(d)}{(n+2)(∥d∥+β∥d∥)}
≥ \frac{ββ̄ρ(d)}{2(n+2)∥d∥}  (since β ≤ 1)

which proves (iv).

Now let R_{2} = \frac{1}{βr̃} + r_{2}. Then

\frac{R_{2}}{r_{2}} = \frac{1}{βr̃r_{2}} + 1 = \frac{(n+2)(∥d∥+w(d))}{ββ̄w(d)} + 1
≤ ^{\frac{(n+2)(∥d∥+ \frac{∥d∥}{β})}{ββ̄w(d)}} + \frac{∥d∥}{βw(d)}  (from Proposition 4.1 and Theorem 3.2)
≤ \frac{(2n+5)∥d∥}{β^{2}β̄w(d)}
≤ \frac{(2n+5)∥d∥}{β^{2}β̄ρ(d)}  ,  (from Theorem 3.2)

proving (iii). To prove (ii), note that

∥x̂∥ + r_{2} = \frac{∥x̃∥}{r̃} + r_{2} ≤ \frac{ū^{T} x̃}{βr̃} + r_{2}  (from (2.14))
≤ \frac{1}{βr̃} + r_{2}
= R_{2}  ,

which proves (ii). As a means to proving (v), first observe that

(n + 2)r̃ ≥ r′′  (from (4.9))

= \frac{r′+ \frac{w(d)}{∥d∥}}{1+ \frac{w(d)}{∥d∥}}

≥ \frac{w(d)}{∥d∥+w(d)}  (since r′ ≥ 0)
≥ _{\frac{w(d)}{∥d∥+ \frac{∥d∥}{β}}}  (from Proposition 4.1 and Theorem 3.2)

≥ \frac{w(d)β}{2∥d∥}  (since β ≤ 1)
≥ \frac{ρ(d)β}{2∥d∥}  .  (from Theorem 3.2)

Therefore,

R_{2} = \frac{1}{βr̃} + r_{2} ≤ \frac{2(n+2)∥d∥}{β^{2}ρ(d)} + r_{2}  (from above)
≤ \frac{2(n+2)∥d∥}{β^{2}ρ(d)} + \frac{1}{r̃(n+2)}
≤ \frac{2(n+2)∥d∥}{β^{2}ρ(d)} + \frac{2∥d∥}{βρ(d)}  (from above)
≤ \frac{(2n+6)∥d∥}{β^{2}ρ(d)}  ,

which proves (v).

We now turn to the case when (P) is inconsistent, i.e., (1.1) has no solution. In this case, from Proposition 2.1, the system (2.2) has a solution, and let us then examine the set of all solutions to (2.2), which we denote by Y_{d} to emphasize the dependence on the data d = (A, b):

Y_{d} = {y ∈ Y^{∗}|A^{T} y ∈ C_{X}^{∗}, y ∈ C_{Y}^{∗} , y^{T} b ≤ 0} .  (4.13)

Lemma 4.3 Suppose that d ∈ F^{C} and C_{X} is regular. If ρ(d) > 0, then there exists ŷ ∈ Y_{d} and positive scalars r_{3} and R_{3} satisfying \frac{R_{3}}{r_{3}} ≤ \frac{∥d∥}{βρ(d)}, and that satisfy:

B(ŷ, r_{3}) ⊂ {y ∈ Y^{∗}|A^{T} y ∈ C_{X}^{∗}, b^{T} y ≤ 0}  (4.14)

and

∥ŷ∥_{∗} ≤ R_{3} .  (4.15)

In the case when C_{Y} = {0}, then C_{Y}^{∗} = Y^{∗}, and (4.14) states that the “dual” feasible region Y_{d} contains a ball of radius r_{3}, and (4.15) states that the center of this ball does not lie more than the distance R_{3} from the origin. Furthermore, \frac{R_{3}}{r_{3}} ≤ \frac{∥d∥}{βρ(d)}.

Proof of Lemma 4.3: Let ỹ solve P_{h}(d). Then A^{T} ỹ − ū ∈ C_{X}^{∗}, −b^{T} ỹ ≥ 1, and ỹ ∈ C_{Y}^{∗}. Then since ỹ ≠ 0 (otherwise −ū ∈ C_{X}^{∗} and so C_{X} is not regular, via Proposition 2.3), let ŷ = \frac{ỹ}{∥ỹ∥_{∗}}. Let

r_{3} = \frac{βg(d)}{∥d∥}, and let R_{3} = 1.

To prove (4.14) it suffices to show that if ∥y − ŷ∥_{∗} ≤ r_{3}, then A^{T} y ∈ C_{X}^{∗} and y^{T} b ≤ 0. We have that q = A^{T} ŷ − \frac{ū}{∥ỹ∥_{∗}} ∈ C_{X}^{∗}. For any x ∈ C_{X} with ∥x∥ = 1,

x^{T} A^{T} y = x^{T} A^{T} (y − ŷ) + x^{T} A^{T} ŷ − \frac{ū^{T} x}{∥ỹ∥_{∗}} + \frac{ū^{T} x}{∥ỹ∥_{∗}}
≥ −∥x∥ ∥A∥ ∥y − ŷ∥_{∗} + x^{T} q + \frac{ū^{T} x}{∥ỹ∥_{∗}}
≥ −∥A∥r_{3} + \frac{ū^{T} x}{∥ỹ∥_{∗}}  (since x^{T} q ≥ 0)
≥ −βg(d) + \frac{ū^{T} x}{∥ỹ∥_{∗}}  (since ∥d∥ ≥ ∥A∥)
≥ −βg(d) + \frac{β}{∥ỹ∥_{∗}}  (from (2.14))
≥ −β (g(d) − \frac{1}{h(d)})
= 0 .  (from T heorem 3.10)

Therefore, A^{T} y ∈ C_{X}^{∗}. Similarly,

−b^{T} y = −b^{T} (y − ŷ) − b^{T} ŷ
≥ −∥d∥ ∥y − ŷ∥_{∗} − \frac{b^{T} ỹ}{∥ỹ∥_{∗}}
≥ −βg(d) + \frac{1}{∥ỹ∥_{∗}}
≥ −βg(d) + \frac{1}{h(d)} = g(d)(1 − β) (from T heorem 3.10)
≥ 0.  (from P roposition 2.3)

Therefore, A^{T} y ∈ C_{X}^{∗} and b^{T} y ≤ 0, which proves (4.14).

To prove (4.15), note that ∥ŷ∥ = 1 = R_{3}, which demonstrates (4.15). Finally note that \frac{R_{3}}{r_{3}} = \frac{1}{r_{3}} = \frac{∥d∥}{βg(d)} ≤ \frac{∥d∥}{βρ(d)} from Theorem 3.9.

We next prove:

Lemma 4.4 Suppose that d ∈ F^{C} and C_{Y} is regular. If ρ(d) > 0, then there exists ŷ ∈ Y_{d} and positive scalars r_{4} and R_{4} satisfying \frac{R_{4}}{r_{4}} ≤ \frac{2m∥d∥}{(β^{∗})^{2}β̄^{∗}ρ(d)}, and that satisfy:

B(ŷ, r_{4}) ⊂ C_{Y}^{∗}  (4.16)

and

∥ŷ∥_{∗} ≤ R_{4} .  (4.17)

In the case when C_{X} = X, then C_{X}^{∗} = {0}, and we can intersect both sides of (4.16) with the affine subspace of y ∈ Y that satisfy A^{T} y = 0. Then (4.16) will imply that the feasible region Y_{d} contains a ball of radius r_{4} intersected with the affine subspace of y ∈ Y that satisfy A^{T} y = 0. Furthermore, (4.17) states that the center of the ball does not lie more than a distance R_{4} from the origin. Furthermore, \frac{R_{4}}{r_{4}} ≤ \frac{2m∥d∥}{(β^{∗})^{2}β̄^{∗}ρ(d)}.

Proof of Lemma 4.4: Let S = Y_{d} ∩ {y ∈ Y^{∗}|z̄^{T} y = 1}. Because S is bounded, closed and convex, there is a Löwner-John pair of ellipsoids for S (see [4]). Therefore, letting ŷ be the common center of both ellipsoids, then ŷ ∈ S, and it will be true that for any w ∈ Y, that

\begin{aligned}w^{T} ŷ− & minimum w^{T} y & ≥ \frac{1}{(m−1)} & (maximum w^{T} y & −w^{T} ŷ). \\ & y ∈ S & & y ∈ S \end{aligned}  (4.18)

(Note that dim(S) ≤ m − 1 from (4.13) and the definition of S.)

We first demonstrate the following fact:

for any w ∈ C_{Y} with ∥w∥ = 1, ŷ^{T} w ≥ \frac{β̄^{∗}δ(d)}{m (∥d∥ + δ(d))} .  (4.19)

In order to prove (4.19), we choose any w ∈ C_{Y} with ∥w∥ = 1. Then, from (2.17), there exists v̄ ∈ C_{Y}^{∗} with ∥v̄∥_{∗} = 1 and v̄^{T} w ≥ β̄^{∗}. Let M = max\{∥A^{T} v̄∥_{∗}, |b^{T} v̄|\}, and set v = −\frac{A^{T} v̄}{M}. Then ∥v∥_{∗} ≤ 1. From (3.10) and (3.11), there exists (y, θ) with θ = δ(d) such that A^{T} y − vθ ∈ C_{X}^{∗}, −b^{T} y − θ ≥ 0, y ∈ C_{Y}^{∗} , and z̄^{T} y = 1. Let y′ = y + \frac{v̄θ}{M}. Then A^{T} y′ = A^{T} y + \frac{A^{T} v̄θ}{M} = A^{T} y − vθ ∈ C_{X}^{∗}. Also b^{T} y′ = b^{T} y + \frac{b^{T} v̄θ}{M} ≤ b^{T} y + θ ≤ 0. Furthermore, since y ∈ C_{Y}^{∗} and v̄ ∈ C_{Y}^{∗} , y′ ∈ C_{Y}^{∗}. We also have y^{′T} w = y^{T} w + \frac{v̄^{T} wθ}{M} ≥ \frac{v̄^{T} wθ}{M} ≥ \frac{β̄^{∗}θ}{M} = \frac{β̄^{∗}δ(d)}{M}. Note that y^{′T} z̄ = y^{T} z̄ + \frac{v̄^{T} z̄θ}{M} = 1 + \frac{v̄^{T} z̄θ}{M} ≤ 1 + \frac{θ}{M} = 1 + \frac{δ(d)}{M}.

Now let y′′ = \frac{y′}{(y^{′T} z̄)}. Then y′′ ∈ S, and w^{T} y′′ ≥ \frac{β̄^{∗}δ(d)}{M(1+ \frac{δ(d)}{M})} = \frac{β̄^{∗}δ(d)}{(M+δ(d))} ≥ \frac{β̄^{∗}δ(d)}{∥d∥+δ(d)}, since

∥v∥_{∗} = 1 implies M ≤ max{∥A∥, ∥b∥} = ∥d∥.

We now apply (4.18) to assert that

w^{T} ŷ ≥ w^{T} ŷ− minimum w^{T} y ≥ (\frac{1}{m−1}) (maximum w^{T} y − w^{T} ŷ)
y ∈ S  y ∈ S
≥ (\frac{1}{m−1}) (w^{T} y′′ − w^{T} ŷ)

which after rearranging yields

w^{T} ŷ ≥ \frac{β̄^{∗}δ(d)}{m(∥d∥ + δ(d))} , which proves (4.19).

Let r_{4} = \frac{δ(d)β̄^{∗}}{m(∥d∥+δ(d))}. To prove (4.16), it suffices to show that ∥y − ŷ∥_{∗} ≤ r_{4} implies y ∈ C_{Y}^{∗}. To demonstrate this, it suffices to show that for any w ∈ C_{Y} with ∥w∥ = 1, that w^{T} y ≥ 0. Let w ∈ C_{Y} and ∥w∥ = 1. Then if ∥y − ŷ∥_{∗} ≤ r_{4}, w^{T} y = w^{T} (y − ŷ) + w^{T} ŷ ≥ −r_{4} + \frac{β̄^{∗}δ(d)}{m(∥d∥+δ(d))} ≥ 0. Thus y ∈ C_{Y}^{∗}, proving (4.16).

Let R_{4} = \frac{1}{β^{∗}}. Then ∥ŷ∥_{∗} ≤ \frac{z̄^{T} ŷ}{β^{∗}} = \frac{1}{β^{∗}} = R_{4}, from (2.15), which proves (4.17). Finally, note that

\frac{R_{4}}{r_{4}} = \frac{1}{β^{∗}r_{4}} = \frac{m(∥d∥+δ(d))}{δ(d)β̄^{∗}β^{∗}}

≤ ^{\frac{m(∥d∥+ \frac{ρ(d)|}{β^{∗}})}{δ(d)β̄^{∗}β^{∗}}}  ( from Theorem 3.7)
≤ \frac{2m∥d∥}{ρ(d)(β^{∗})^{2}β̄^{∗}} , from Proposition 4.1 .

5 Synthesis of Results

In this section, we synthesize the results of the previous two sections into theorems that characterize aspects of the distance to ill-posedness for the three particular cases of problem P of (1.1), namely

\begin{matrix}(i) & Case 1 : C_{X} and C_{Y} are both regular, \\ (ii) & Case 2 : C_{X} is regular and C_{Y} = \{0\}, \\ (iii) & Case 3 : C_{X} = X and C_{Y} is regular, \end{matrix}

and for the status of solvability of P of (1.1), namely

\begin{matrix}(a) & P is consistent, i.e., (1.1) has a solution, and \\ (b) & P is inconsistent, i.e., (2.2) has a solution. \end{matrix}

Each of the six theorems of this section synthesizes our results of the previous two sections, as applied to the one of the three cases above and one of the two status’ of the solvability of P. Each theorem summarizes the applicable approximation characterizations of ρ(d) of Section 3, and also synthesizes the appropriate bounds on radii of contained and intersecting balls developed in Section 4. For a motivation of the importance of these bounds on radii of contained and intersecting balls contained herein, the reader is referred to the opening discussion at the beginning of Section 4.

Each case is treated as a separate subsection, and all proofs are deferred to the end of the section.

5.1 Case 1: C_{X} and C_{Y} are both regular.

Theorem 5.1 Suppose that C_{X} and C_{Y} are both regular. If P is consistent, i.e., d ∈ F, then (i) β · α(d) ≤ ρ(d) ≤ α(d) (ii) α(d) = w(d), and so β · w(d) ≤ ρ(d) ≤ w(d) (iii) β^{∗}β · α̃(d) ≤ ρ(d) ≤ α̃(d) (iv) β^{∗} · u(d) ≤ ρ(d) ≤ u(d)

(v) \frac{β^{∗}}{v(d)} ≤ ρ(d) ≤ \frac{1}{v(d)} . (vi) If ρ(d) > 0, then there exists x̂ ∈ X_{d} and positive scalars r and R satisfying:

(a) B (x̂, r) ⊂ X_{d}
(b) B (x̂, r) ⊂ B(0, R)
(c) \frac{R}{r} ≤ \frac{(4n+10)∥d∥}{β^{2}β̄β^{∗}ρ(d)}
(d) r ≥ \frac{ββ̄β^{∗}ρ(d)}{4(n+2)∥d∥}
(e) R ≤ \frac{(2n+6)∥d∥}{β^{2}β̄β^{∗}ρ(d)}  .

Theorem 5.2 Suppose that C_{X} and C_{Y} are both regular. If P is not consistent, i.e., d ∈ F^{C}, then (i) β^{∗} · σ(d) ≤ ρ(d) ≤ σ(d) (ii) σ(d) = δ(d), and so β^{∗} · δ(d) ≤ ρ(d) ≤ δ(d) (iii) β^{∗}β · σ̃(d) ≤ ρ(d) ≤ σ̃(d) (iv) β · g(d) ≤ ρ(d) ≤ g(d)

(v) \frac{β}{h(d)} ≤ ρ(d) ≤ \frac{1}{h(d)} . (vi) If ρ(d) > 0, then there exists ŷ ∈ Y_{d} and positive scalars r and R satisfying

\frac{R}{r} ≤ \frac{(4m + 1)∥d∥}{(β^{∗})^{2}ββ̄^{∗} · ρ(d)}

such that

{y ∈ Y^{∗}|∥y − ŷ∥_{∗} ≤ r} ⊂ Y_{d}

and

{y ∈ Y^{∗}|∥y − ŷ∥_{∗} ≤ r} ⊂ {y ∈ Y^{∗}|∥y∥_{∗} ≤ R} .

5.2 Case 2: C_{X} is regular and C_{Y} = {0}.

Theorem 5.3 Suppose that C_{X} is regular and C_{Y} = {0}. If P is consistent, i.e., d ∈ F, then (i) β · α(d) ≤ ρ(d) ≤ α(d)

(ii) α(d) = w(d), and so β · w(d) ≤ ρ(d) ≤ w(d) (iii) If ρ(d) > 0, then there exists x̂ ∈ X_{d} and positive scalars r and R satisfying:

(a) {x ∈ X| |∥x − x̂∥ ≤ r, Ax = b} ⊂ X_{d}
(b) {x ∈ X| ∥x − x̂∥ ≤ r, Ax = b} ⊂ B(0, R)
(c) \frac{R}{r} ≤ \frac{(2n+5)∥d∥}{ρ(d)β^{2}β̄}
(d) r ≥ \frac{ββ̄ρ(d)}{2(n+2)∥d∥}
(e) R ≤ \frac{(2n+6)∥d∥}{β^{2}β̄ρ(d)}  .

Theorem 5.4 Suppose that C_{X} is regular and C_{Y} = {0}. If P is not consistent, i.e., d ∈ F^{C}, then (i) β · g(d) ≤ ρ(d) ≤ g(d) (ii) \frac{β}{h(d)} ≤ ρ(d) ≤ \frac{1}{h(d)} (iii) If ρ(d) > 0, then there exists ŷ ∈ Y_{d} and positive scalars r and R satisfying

\frac{R}{r} ≤ \frac{2∥d∥}{β · ρ(d)}

such that

{y ∈ Y^{∗}|∥y − ŷ∥_{∗} ≤ r} ⊂ Y_{d}

and

{y ∈ Y^{∗}|∥y − ŷ∥_{∗} ≤ r} ⊂ {y ∈ Y^{∗}|∥y∥_{∗} ≤ R} .

5.3 Case 3: C_{X} = X and C_{Y} is regular.

Theorem 5.5 Suppose that C_{X} = X and C_{Y} is regular. If P is consistent, i.e., d ∈ F, then (i) β^{∗} · u(d) ≤ ρ(d) ≤ u(d) (ii) \frac{β^{∗}}{v(d)} ≤ ρ(d) ≤ \frac{1}{v(d)} (iii) If ρ(d) > 0, then there exists x̂ ∈ X_{d} and positive scalars r and R satisfying:

(a) {x ∈ X| |∥x − x̂∥ ≤ r} ⊂ X_{d}
(b) {x ∈ X| ∥x − x̂∥ ≤ r} ⊂ B(0, R)
(c) \frac{R}{r} ≤ \frac{3∥d∥}{β^{∗}ρ(d)}
(d) r ≥ \frac{β^{∗}ρ(d)}{3∥d∥}
(e) R ≤ \frac{3∥d∥}{β^{∗}ρ(d)}  .

Theorem 5.6 Suppose that C_{X} = X and C_{Y} is regular. If P is not consistent, i.e., d ∈ F^{C}, then

(i) β^{∗} · σ(d) ≤ ρ(d) ≤ σ(d)

(ii) σ(d) = δ(d), and so β^{∗} · δ(d) ≤ ρ(d) ≤ δ(d)

(iii) If ρ(d) > 0, then there exists ŷ ∈ Y_{d} and positive scalars r and R satisfying

\frac{R}{r} ≤ \frac{(4m + 1)∥d∥}{(β^{∗})^{2}β̄^{∗} · ρ(d)}

such that

{y ∈ Y^{∗}|∥y − ŷ∥_{∗} ≤ r, A^{T} y = 0} ⊂ Y_{d}

and

{y ∈ Y^{∗}|∥y − ŷ∥_{∗} ≤ r} ⊂ {y ∈ Y^{∗}|∥y∥ ≤ R} .

Proof of Theorem 5.1: Parts (i), (ii), (iii), (iv) and (v) follow directly from Theorems 3.1, 3.2, 3.3, 3.4 and 3.5, respectively. It remains to prove part (vi).

Let S = {x ∈ X|b − Ax ∈ C_{Y} } and T = C_{X}. Then S ∩ T = X_{d}. From Lemma 4.1, there exists x̂_{1} ∈ X_{d} and r_{1}, R_{1} satisfying conditions (i) − (v) of Lemma 4.1. From Lemma 4.2, there exists x̂_{2} ∈ X_{d} and r_{2}, R_{2} satisfying conditions (i) − (v) of Lemma 4.2. Then the conditions of Proposition A.2 of the Appendix are satisfied, and so there exists x̂ and r, R̂ satisfying the five conditions of Proposition A.2. Therefore, (i) B (x̂, r) ⊂ S ∩ T = X_{d}, which is (a). Also from (ii), B (x̂, r) ⊂ B(0, R̂), which is (b). From (iii), we have

\frac{R̂}{r} ≤ 2max \{\frac{R_{1}}{r_{1}} , \frac{R_{2}}{r_{2}} \} ≤ \frac{(4n + 10)∥d∥}{β^{2}β̄β^{∗}ρ(d)}

(invoking Lemma 4.1 (iii) and Lemma 4.2 (iii)), which is (c). Similarly applying Lemma 4.1 and 4.2 and Proposition A.2 in parts (iv) and (v) yields

r ≥ \frac{1}{2}min \{r_{1}, r_{2}\} ≥ \frac{ββ̄β^{∗}ρ(d)}{4(n + 2)∥d∥}

and

R̂ ≤ max \{R_{1}, R_{2}\} ≤ \frac{(2n + 6)∥d∥}{β^{2}β^{∗}ρ(d)} .

Proof of Theorem 5.2: Parts (i), (ii), (iii), (iv) and (v) follow directly from Theorems 3.6, 3.7, 3.8, 3.9 and 3.10, respectively. It remains to prove part (vi).

Let S = {y ∈ Y^{∗}|A^{T} y ∈ C_{X}^{∗}, b^{T} y ≤ 0} and T = C_{Y}^{∗}. Then S ∩ T = Y_{d}. From Lemma 4.3, there exists ŷ_{3}, r_{3}, R_{3} satisfying ŷ_{3} ∈ S ∩ T, B(ŷ_{3}, r_{3}) ⊂ S and ∥ŷ_{3}∥_{∗} ≤ R_{3}, and \frac{R_{3}}{r_{3}} ≤ \frac{∥d∥}{βρ(d)}. From Lemma 4.4 there exists ŷ_{4}, r_{4}, R_{4} satisfying ŷ_{4} ∈ S ∩ T, B(ŷ_{4}, r_{4}) ⊂ T, and ∥ŷ_{4}∥_{∗} ≤ R_{4}, and \frac{R_{4}}{r_{4}} ≤ \frac{2m∥d∥}{(β^{∗})^{2}β̄^{∗}ρ(d)}. Then from Proposition A.1 of the Appendix, there exists ŷ and r, R̂ satisfying

B(ŷ, r) ⊂ S ∩ T = Y_{d}, and ∥ŷ∥ ≤ R̂, and

\begin{aligned}\frac{R̂}{r} & ≤ 2max \{\frac{R_{3}}{r_{3}} , \frac{R_{4}}{r_{4}} \} & ≤ 2max \{\frac{∥d∥}{βρ(d)}, \frac{2m∥d∥}{(β^{∗})^{2}β̄^{∗}ρ(d)}\} \\ & ≤ \frac{4m∥d∥}{β(β^{∗})^{2}β̄^{∗}ρ(d)} & . \end{aligned}

Now let R = R̂ + r. Then for any y ∈ B(ŷ, r), ∥y∥_{∗} ≤ ∥ŷ∥_{∗} + r ≤ R̂ + r = R, and

\frac{R}{r} = \frac{R̂}{r} + 1 ≤ \frac{4m∥d∥}{β(β^{∗})^{2}β̄^{∗}ρ(d)} +\frac{∥d∥}{ρ(d)} (from Proposition 4.1)
≤ \frac{(4m+1)∥d∥}{β(β^{∗})^{2}β̄^{∗}ρ(d)}  .

Proof of Theorem 5.3: Parts (i) and (ii) follow directly from Theorems 3.1 and 3.2, respectively. To prove (iii) we apply Lemma 4.2; there exists x̂ ∈ X_{d} and r_{2}, R_{2} satisfying the five conditions of Lemma 4.2. Let r = r_{2} and R = R_{2} + r_{2}. Then (b), (c), (d), and (e) follow directly. To prove (a), observe that from Lemma 4.2 (i) that

{x ∈ X| ∥x − x̂∥ ≤ r} ⊂ C_{X} ,

and intersecting both sides with the affine set {x ∈ X|Ax = b} gives

{x ∈ X| ∥x − x̂∥ ≤ r, Ax = b} ⊂ C_{X} ∩ {x ∈ X|Ax = b} = X_{d} .

Proof of Theorem 5.4: Parts (i) and (ii) follow directly from Theorems 3.9 and 3.10, respectively. To prove (iii) we apply Lemma 4.3; there exists ŷ ∈ Y_{d} and r_{3}, R_{3} satisfying \frac{R_{3}}{r_{3}} ≤ \frac{∥d∥}{βρ(d)} and (4.14) and (4.15). Let r = r_{3} and R = R_{3} + r_{3}. Then from (4.14) we obtain

{y ∈ Y^{∗}| ∥y − ŷ∥_{∗} ≤ r} ⊂ {y ∈ Y^{∗}|A^{T} y ∈ C_{X}^{∗}, b^{T} y ≤ 0} = Y_{d} .

Also, for any y satisfying ∥y − ŷ∥ ≤ r, ∥y∥ ≤ ∥ŷ∥ + r ≤ R_{3} + r_{3} = R. Finally, note that

\frac{R}{r} = \frac{R_{3}}{r_{3}} + 1 ≤ \frac{∥d∥}{βρ(d)} + 1 ≤ \frac{∥d∥}{βρ(d)} + \frac{∥d∥}{ρ(d)}  (from Proposition 4.1)
≤ \frac{2∥d∥}{βρ(d)}  .

Proof of Theorem 5.5: Parts (i) and (ii) follow directly from Theorems 3.4 and 3.5, respectively. To prove (iii) we apply Lemma 4.1; there exists x̂ ∈ X_{d} and r_{1}, R_{1} satisfying the five conditions of Lemma 4.1. Let r = r_{1} and R = R_{1}. Then (b), (c), (d), and (e) following directly. To prove (a), observe from Lemma 4.1(i) that

{x ∈ X| ∥x − x̂∥ ≤ r} ⊂ {x ∈ X|b − Ax ∈ C_{Y} } = X_{d} .

Proof of Theorem 5.6: Parts (i) and (ii) follow from Theorems 3.6 and 3.7, respectively. It remains to prove (iii).

Let S = {y ∈ Y^{∗}|b^{T} y ≤ 0}. If we let v = 0 in (3.9), we see that there exists ŷ_{1} ∈ C_{Y}^{∗} satisfying A^{T} ŷ_{1} = 0, z̄^{T} ŷ_{1} = 1 and −b^{T} ŷ_{1} ≥ δ(d) ≥ ρ(d), from Theorem 3.7. Therefore, if we set r_{1} = \frac{ρ(d)}{∥d∥} and R_{1} = \frac{1}{β^{∗}}, we have ∥ŷ_{1}∥_{∗} ≤ \frac{z̄^{T} ŷ_{1}}{β^{∗}} = R_{1} (from 2.15), and for any y satisfying ∥y − ŷ_{1}∥_{∗} ≤ r_{1}, we have b^{T} y = b^{T} (y − ŷ_{1}) + b^{T} ŷ_{1} ≤ ∥b∥ ∥ŷ_{1} − y∥_{∗} − ρ(d) ≤ ∥d∥r_{1} − ρ(d) = 0, and so B(ŷ_{1}, r_{1}) ⊂ S. If we let T = C_{Y}^{∗}, we have S ∩ T ∩ {y ∈ Y^{∗}|A^{T} y = 0} = Y_{d}, and ŷ_{1} ∈ Y_{d}. From Lemma 4.4, there exists ŷ_{2} and r_{4}, R_{4} satisfying \frac{R_{4}}{r_{4}} ≤ \frac{2m∥d∥}{(β^{∗})^{2}β̄^{∗}ρ(d)}, and (4.16) and (4.17). Then from

Proposition A.1 of the Appendix, there exists ŷ and r, R̂ satisfying B(ŷ, r) ⊂ S ∩ T and ∥ŷ∥ ≤ R̂, and

\frac{R̂}{r} ≤ 2max \{\frac{∥d∥}{β^{∗}ρ(d)}, \frac{2m∥d∥}{(β^{∗})^{2}β̄^{∗}ρ(d)}\} = \frac{4m∥d∥}{(β^{∗})^{2}β̄^{∗}ρ(d)} .

Note also that

{y ∈ Y^{∗}| ∥y − ŷ∥_{∗} ≤ r, A^{T} y = 0} ⊂ S ∩ T ∩ {y ∈ Y^{∗}|A^{T} y = 0} = Y_{d} .

Let R = R̂ + r. Then for any y ∈ B(ŷ, r), ∥y∥_{∗} ≤ ∥ŷ∥_{∗} + r = R̂ + r = R, and

\frac{R}{r} = \frac{R̂}{r} + 1 ≤ \frac{4m∥d∥}{(β^{∗})^{2}β̄^{∗}ρ(d)} +\frac{∥d∥}{ρ(d)} (from Proposition 4.1)
≤ \frac{(4m+1)∥d∥}{(β^{∗})^{2}β̄^{∗}ρ(d)}  .

APPENDIX

This appendix contains four results that are used in the body of the paper. The first result is an application of gauge duality theory from [5]. The second result is a duality theorem for a class of mathematical programs, and the last two results are simple constructions with balls on the intersection of two sets.

1. Nonlinear gauge duality for closed gauge functions

Let V be a finite-dimensional normed linear vector space with norm ∥v∥ for v ∈ V. A function f(·) : V → R ∪ {+∞} is a gauge function if f(·) is a nonnegative convex function that is positively homogeneous of degree one, and f(0) = 0. The level sets of f(·) are those sets of the form S_{α} = {v ∈ V |f(v) ≤ α}. If all of the level sets of f(·) are closed sets, then f(·) is a closed gauge function.

Corresponding to every gauge function f(·) is a polar gauge function f^{∗}(y) defined for all y in the dual space V^{∗}. When f(·) is a closed gauge function, this polar function takes on the convenient definitional form:

\begin{aligned}f^{∗}(y) = & sup & y^{T} v \\ & v \\ & s.t. & f(v) ≤ 1 & , \end{aligned}  (A.1)

for all y ∈ V^{∗}. Also, when f(·) is a closed gauge function, f^{∗∗}(·) = f(·), provided that we identify V^{∗∗} with V. An excellent treatment of polarity for gauge functions is given in [15].

Consider the following optimization problem:

GP :

\begin{aligned}s^{∗} = & infimum & f(Mx) \\ & x \\ & s.t. & x ∈ K \\ & & d^{T} x = 1 & , \end{aligned}  (A.2)

and its \underline{gauge dual}, defined as

GD :

\begin{aligned}t^{∗} = & infimum & f^{∗}(y) \\ & y \\ & s.t. & M^{T} y − d ∈ K^{∗} \\ & & y ∈ V^{∗} & , \end{aligned}  (A.3)

where M is a linear operator from a finite-dimensional normed linear vector space U to the finitedimensional normed linear vector space V, i.e., M ∈ L(U, V), d is a linear functional, i.e., d ∈ U^{∗}, and K is a convex cone in U. The following duality theorem is a special instance of Theorem 2A in [5].

TheoremA.1 : (I) If s^{∗} = 0, then t^{∗} = +∞.
(II) If t^{∗} = 0, then s^{∗} = +∞.
(III) If s^{∗} > 0 and t^{∗} > 0, then s^{∗}t^{∗} = 1 under the following hypotheses :

(i) all projections of {x ∈ K|d^{T} x = 1} are closed sets, (ii) sup{d^{T} x|x ∈ K} = +∞, (iii) f(·) is a closed gauge function, and (iv) {v ∈ V |f(v) ≤ 1} is a closed and bounded set.

Before proving the theorem, we first prove the following:

Lemma A.1 Under the four hypotheses of Theorem A.1 (III), suppose that ȳ ∈ V^{∗} is given. Then

ȳ^{T} Mx > 1 for all x ∈ K ∩ {x ∈ U|d^{T} x = 1}  (A.4)

if and only if

there exists π > 1 satisfying M^{T} ȳ − dπ ∈ K^{∗} .  (A.5)

Proof : First suppose (A.5) holds. Then, if x ∈ K and d^{T} x = 1, we have x^{T} (M^{T} ȳ − dπ) ≥ 0, so that ȳ^{T} Mx ≥ πd^{T} x = π > 1, so that (A.4) is true. Conversely, suppose that (A.4) holds. Let

ϵ = minimum ȳ^{T} Mx
x
s.t.  x ∈ K
d^{T} x = 1 .

From (A.4) and the hypothesis (i), it must be true that ϵ > 1. Let S = {(α, δ) ∈ R × R | there exists x ∈ K satisfying 1 − d^{T} x = α, ȳ^{T} Mx − ϵ < δ}. Then S is a nonempty convex set and (0, 0) ∉ S. Thus, there exists a hyperplane that separates (0, 0) from S, i.e., there exists (π, γ) ≠ (0, 0) with the property that απ + δγ ≥ 0 for any (α, γ) ∈ S. Therefore γ ≥ 0. Also, for any x ∈ K and any μ > 0, π (1 − d^{T} x) + (ȳ^{T} Mx − ϵ + μ) γ ≥ 0. If γ = 0, then π ≠ 0 and π ≥ πd^{T} x for any x ∈ K. Thus π ≥ 0 and π = 1 without loss of generality. Thus d^{T} x ≤ 1 for any x ∈ K, violating the second hypothesis of the theorem. As this is a contradiction, it must be true that γ > 0, and so γ = 1 without a loss of generality. Then π − πd^{T} x + ȳ^{T} Mx − ϵ + μ ≥ 0 for any x ∈ K, and μ > 0. Therefore, M^{T} ȳ − πd ∈ K^{∗}. Also, upon setting x = 0 we obtain π ≥ ϵ − μ for any μ > 0. Thus π ≥ ϵ > 1, proving that (A.5) holds.

Proof of Theorem A.1 : If s^{∗} and t^{∗} are both finite, then GP and GD have feasible solutions. Note that for any feasible solutions x of GP and y of GD, that x^{T} M^{T} y − x^{T} d ≥ 0. Therefore, 1 = d^{T} x ≤ y^{T} Mx ≤ f(Mx)f^{∗}(y), where the last inequality follows from (A.1). Therefore s^{∗}t^{∗} ≥ 1, which is “weak duality” for these dual programs. If either s^{∗} = 0 or t^{∗} = 0, then t^{∗} = +∞ or s^{∗} = +∞, respectively, demonstrating (I) and (II) of the theorem.

To prove (III), we suppose that s^{∗}t^{∗} > 1 and derive a contradiction. Therefore s^{∗} > \frac{1}{t^{∗}}, and so the two sets

S_{1} = {v ∈ V |v = Mx for some x ∈ K satisfying d^{T} x = 1}

and

S_{2} = \{v ∈ V |f(v) ≤ \frac{1}{t^{∗}} \}

are nonempty and disjoint. Now from hypothesis (i) we have S_{1} is a closed convex set, and from hypotheses (iii) and (iv) we have that S_{2} is a closed and bounded convex set. Since S_{1} ∩ S_{2} = ϕ, there exists a hyperplane that strictly separates S_{1} and S_{2}, due to the boundedness of S_{2}. Thus there exists ȳ ∈ V^{∗} and β such that

ȳ^{T} Mx > β for all x ∈ K satisfying d^{T} x = 1  (A.6)

and

ȳ^{T} v < β for all v that satisfy f(v) ≤ \frac{1}{t^{∗}} .  (A.7)

With v = 0 in (A.7) we see that β > 0, and so β = 1 without loss of generality. From (A.7) and (A.1), we conclude that f^{∗}(ȳ) ≤ t^{∗}. Next we observe that with β = 1 that (A.6) corresponds to (A.4), so by Lemma A.1, there exists π > 1 satisfying M^{T} ȳ − dπ ∈ K^{∗}. With y = \frac{ȳ}{π}, we have M^{T} y − d ∈ K^{∗}, y ∈ V^{∗}, and f^{∗}(y) = \frac{1}{π} f^{∗}(ȳ) < f^{∗}(ȳ) ≤ t^{∗}. However, as y is feasible for GD, t^{∗} ≤ f^{∗}(y), which yields a contradiction. Thus s^{∗}t^{∗} = 1 is proved.

2. A Strong Duality Theorem

Consider the following pair of optimization problems:

NP :

\begin{aligned}v_{P} = & maximum & θ \\ & x, θ \\ & s.t. & Mx − θw ∈ K_{1} \\ & & x ∈ K_{2} \\ & & f^{T} x = 1 \\ & & θ ≥ 0 & , \end{aligned}  (A.8)

ND :

\begin{aligned}v_{D} = & minimum & γ \\ & y, γ \\ & s.t. & −M^{T} y + γf ∈ K_{2}^{∗} \\ & & y^{T} w ≥ 1 \\ & & y ∈ K_{1}^{∗} & , \end{aligned}  (A.9)

where K_{1}, K_{2} are convex cones in finite-dimensional normed linear vector spaces V_{1} and V_{2}, respectively, M ∈ L (V_{2}, V_{1}) , f ∈ V_{2}^{∗}, and w ∈ V_{1}.

Theorem A.2: Suppose that NP has a feasible solution. If K_{1} and K_{2} are closed convex cones and f ∈ int K_{2}^{∗}, then v_{P} = v_{D}.

Proof: First suppose that (x, θ) and (y, γ) are feasible for NP and ND, respectively. Then y^{T} Mx − θy^{T} w ≥ 0, −x^{T} M^{T} y + γf^{T} x ≥ 0, and θy^{T} w ≥ θ, all follow by combining feasibility conditions of NP and ND. Summing these inequalities we obtain γ = γf^{T} x ≥ θ, whereby v_{D} ≥ v_{P}.

By the hypothesis of the theorem, v_{P} > −∞. If v_{P} = +∞, then v_{D} = +∞ from the above inequality. Therefore it remains to consider the case when v_{P} is finite. We proceed as follows:

Let us define the set S = {(s, t, z) ∈ V_{2}^{∗} × R × R|there exists (y, γ, v) satisfying y ∈ K_{1}^{∗},

v ∈ K_{2}^{∗}, −M^{T} y + γf + s = v, 1 − y^{T} w ≤ t, γ ≤ z}. Then S ≠ ϕ, and for any given ϵ > 0, the point (0, 0, v_{D} − ϵ) ∉ S. Therefore, since S is a convex set, there exists a hyperplane separating S from (0, 0, v_{D} − ϵ). Thus, there exists (x, θ, δ) ≠ 0 and g such that

δ (v_{D} − ϵ) ≤ g ≤ x^{T} s + θt + δz for any (s, t, z) ∈ S .

This implies that θ ≥ 0. Also, for any v ∈ K_{2}^{∗} and any y ∈ K_{1}^{∗}, and any γ,

x^{T} (v + M^{T} y − γf) + θ (1 − y^{T} w) + δγ ≥ δ (v_{D} − ϵ) .

In particular, this implies that x ∈ K_{2} and Mx − θw ∈ K_{1}, f^{T} x = δ, and θ ≥ δ (v_{D} − ϵ). Also, since f ∈ int K_{2}^{∗} from the hypothesis of the theorem, then δ ≥ 0. If δ > 0, without loss of generality δ = 1, so that f^{T} x = 1 and θ ≥ v_{D} − ϵ. Then (x, θ) is feasible for NP, and v_{P} ≥ θ ≥ v_{D} − ϵ. As this is true for any ϵ > 0, then v_{P} ≥ v_{D}, which proves that v_{P} = v_{D}.

It only remains to examine the case when δ = 0. Then f^{T} x = 0, which implies that x = 0, since f ∈ int K_{2}^{∗} and x ∈ K_{2}. Therefore, θ ≠ 0, and since θ ≥ 0, θ = 1 without loss of generality. Then 1 − y^{T} w ≥ 0 for any y ∈ K_{1}^{∗}, whereby −w ∈ K_{1}. Because NP is feasible, there exists (x̄, θ̄) feasible for NP. And since −w ∈ K_{1}, (x̄, θ̄ + θ) is feasible for NP for all θ ≥ 0, whereby v_{P} = +∞, which contradicts the supposition of the case. Thus δ > 0 as desired.

3. A Construction Using Inscribed Balls and Intersecting Sets

Proposition A.1 Let X be a finite-dimensional normed linear vector space with norm ∥ · ∥ and let S and T be subsets of X. Suppose that

(i) x̂_{1} ∈ S ∩ T, B(x̂_{1}, r_{1}) ⊂ S, where r_{1} > 0, and ∥x̂_{1}∥ ≤ R_{1}, and
(ii) x̂_{2} ∈ S ∩ T, B(x̂_{2}, r_{2}) ⊂ T, where r_{2} > 0, and ∥x̂_{2}∥ ≤ R_{2}.
Let α = \frac{r_{2}}{r_{1}+r_{2}} , and r = \frac{r_{1}r_{2}}{r_{1}+r_{2}} , and R̂ = αR_{1} + (1 − α)R_{2}.
Then the point x̂ = αx̂_{1} + (1 − α)x̂_{2} will satisfy:
(i) B(x̂, r) ⊂ S ∩ T ,
(ii) ∥x̂∥ ≤ R̂ ,
and (iii) \frac{R̂}{r} ≤ 2max \{\frac{R_{1}}{r_{1}} , \frac{R_{2}}{r_{2}} \} .

Proof: First note that 0 ≤ α ≤ 1. Because B(x̂_{1}, r_{1}) ⊂ S and x̂_{2} ∈ S, B(αx̂_{1} +(1−α)x̂_{2}, αr_{1}) ⊂ S. Similarly, because B(x̂_{2}, r_{2}) ⊂ T and x̂_{1} ∈ T, B(αx̂_{1} + (1 − α)x̂_{2}, (1 − α)r_{2}) ⊂ T. Noticing that αr_{1} = (1 − α)r_{2} = r, we have B(x̂, r) = B(αx̂_{1} + (1 − α)x̂_{2}, r) ⊂ S ∩ T. Also ∥x̂∥ ≤ α∥x̂_{1}∥ + (1 − α)∥x̂_{2}∥ ≤ αR_{1} + (1 − α)R_{2} = R̂. Finally, to show (iii), suppose first that \frac{R_{1}}{r_{1}} ≥ \frac{R_{2}}{r_{2}} . Then

\frac{R̂}{r} = \frac{αR_{1} + (1 − α)R_{2}}{r} = \frac{r_{2}R_{1} + r_{1}R_{2}}{r_{1}r_{2}} ≤ \frac{r_{2}R_{1} + r_{2}R_{1}}{r_{1}r_{2}} = \frac{2R_{1}}{r_{1}} = 2max \{\frac{R_{1}}{r_{1}} , \frac{R_{2}}{r_{2}} \} .

A similar argument holds when \frac{R_{1}}{r_{1}} ≤ \frac{R_{2}}{r_{2}} .

Proposition A.2 Let X be a finite-dimensional normed linear vector space with norm ∥ · ∥ and let S and T be subsets of X. Suppose that

(i) x̂_{1} ∈ S ∩ T, B(x̂_{1}, r_{1}) ⊂ S, where r_{1} > 0, and B(x̂_{1}, r_{1}) ⊂ B(0, R_{1}) and
(ii) x̂_{2} ∈ S ∩ T, B(x̂_{2}, r_{2}) ⊂ T, where r_{2} > 0, and B(x̂_{2}, r_{2}) ⊂ B(0, R_{2}).

Let α = \frac{r_{2}}{r_{1}+r_{2}} , and r = \frac{r_{1}r_{2}}{r_{1}+r_{2}} , and R̂ = αR_{1}+(1−α)R_{2}. Then the point x̂ = αx̂_{1}+(1−α)x̂_{2} will satisfy:

(i) B(x̂, r) ⊂ S ∩ T ,
(ii) B(x̂, r) ⊂ B(0, R̂) ,
(iii) \frac{R̂}{r} ≤ 2max \{\frac{R_{1}}{r_{1}} , \frac{R_{2}}{r_{2}} \} ,
(iv) r ≥ \frac{1}{2}min\{r_{1}, r_{2}\} ,
and (v) R̂ ≤ max{R_{1}, R_{2}} .

Proof: Parts (i) and (iii) follow identically the proof of Proposition A.1. To see (iv), note that by definition of r, r ≥ \frac{min\{r_{1},r_{2}\}max\{r_{1},r_{2}\}}{2max\{r_{1},r_{2}\}} = \frac{1}{2}min \{r_{1}, r_{2}\}. Part (v) follows from the fact that R̂ is a convex combination of R_{1} and R_{2}. To prove (ii), note that for any x ∈ B(x̂, r), we have ∥x∥ ≤ ∥x̂∥ + r ≤ α∥x̂_{1}∥ + (1 − α)∥x̂_{2}∥ + r. However, ∥x̂_{i}∥ + r_{i} ≤ R_{i}, i = 1, 2, so that ∥x∥ ≤ α (R_{1} − r_{1}) + (1 − α) (R_{2} − r_{2}) + r = R − r ≤ R, which completes the proof.

References

[1] F. Alizadeh, Interior Point Methods in Semidefinite Programming with Applications to Combinatorial Optimization, SIAM Journal on Optimization 5 (1995), pp. 13-51.

[2] M. Bazaraa, Sherali, H.D., and Shetty, C.M., Nonlinear Programming Theory and Applications, Wiley, 1970, New York.

[3] L. Blum, M. Shub, and S. Smale, On a Theory of Computation and Complexity over the Real Numbers: NP-completeness, Recursive Functions and Universal Machines, Bull. Amer. Math. Soc., 21 (1989), pp. 1-46.

[4] L. Danzer, Grünbaum, B., and Klee, V., Helly’s Theorem and its relatives, in Convexity, B. Klee, ed., amer. Math. Soc., Providentce, RI, pp. 101-180.

[5] R.M. Freund, Dual Gauge Programs, with Applications to Quadratic Programming and the Minimum-Norm Problem, Mathematical Programming 38 (1987), pp. 47-67.

[6] S. Filipowski, On the Complexity of Solving Linear Programs Specified with Approximate Data and Known to be Feasible, Technical Report, Dept. of Industrial and Manufacturing Systems Engineering, Iowa State Univeristy, May 1994, Ames, Iowa.

[7] S. Filipowski, On the Complexity of Solving Sparse Symmetric Linear Programs Specified with Approximate Data, Technical Report, Dept. of Industrial and Manufacturing Systems Engineering, Iowa State Univeristy, December 1994, Ames, Iowa.

[8] A.S. Lewis, Group invariance and convex matrix analysis, Technical Report, Dept. of Combinatorics and Optimization, University of Waterloo, February 1995, Waterloo, Canada.

[9] Nesterov, Y., A. Nemirovskii, Interior-Point Polynomial Algorithms in Convex Programming. SIAM Studies in Applied Mathematics No. 13, SIAM, Philadelphia, 1994.

[10] M. Nunez, and R.M. Freund, Condition Measures and Properties of the Central Trajectory of a Linear Program, in preparation.

[11] J. Renegar, Some Perturbation Theory for Linear Programming, Mathematical Programming 65 (1994) 1, pp. 73-92.

[12] J. Renegar, Incorporating Condition Measures into the Complexity Theory of Linear Programming, to apperar in SIAM Journal on Optimization.

[13] J. Renegar, Linear Programming, Complexity Theory and Elementary Functional Analysis. To appear in Mathematical Programming.

[14] S. Smale, Some Remarks on the Foundations of Numerical Analysis, SIAM Review, 32 (1990) pp.211-220.

[15] T. Rockafellar, Convex Analysis, Princeton Univeristy Press, 1970, Princeton, N.J.

[16] J. Vera, Ill-Posedness in Mathematical Programming and Problem Solving with Approximate Data. Ph.D. Dissertation, Cornell University, Ithaca, N.Y. 1992.

[17] J. Vera, Ill-Posedness and the Complexity of Deciding Existence of Solutions to Linear Programs, to apperar in SIAM Journal on Optimization.

[18] J. Vera, On the Complexity of Linear Programming under Finite Precision Arithmetic, working paper, Dept. of Industrial Engineering, University of Chile, 1994.

[19] K. Yosida, Functional Analysis, Springer, Berlin, 1987.