Nondegeneracy of Polyhedra and Linear Programs.
This paper deals with nondegeneracy of polyhedra and linear programming (LP) problems. We allow for the possibility that the polyhedra and the feasible polyhedra of the LP problems under consideration be non-pointed. polyhedron is pointed if it has a vertex.) With respect to a given polyhedron, we consider two notions of nondegeneracy and then provide several equivalent characterizations for each of them. With respect to LP problems, we study the notion of constant cost nondegeneracy first introduced by Tsuchiya [25] under a different name, namely dual nondegeneracy. (We do not follow this terminology since the term dual nondegeneracy is already used to refer to a related but different type of nondegeneracy.) We show two main results about constant cost nondegeneracy of an LP problem. The first one shows that constant cost nondegeneracy of an LP problem is equivalent to the condition that the union of all minimal faces of the feasible polyhedron be equal to the set of feasible points satisfying a certain generalized strict complementarity condition. When the feasible polyhedron of an LP is nondegenerate, the second result shows that constant cost nondegeneracy is equivalent to the condition that the set of feasible points satisfying the generalized condition be equal to the set of feasible points satisfying the same complementarity condition strictly. For the purpose of giving a preview of the paper, the above results specialized to the context of polyhedra and LP problems in standard form are described in the introduction.
Introduction
This paper deals with the subject of nondegeneracy of polyhedra and linear programming (LP)
problems. Nondegeneracy is a subject worth of intensive investigation due to its application in
several branches of mathematical programming and has already been studied in several papers in
the literature. These include papers dealing with cycling and termination of the simplex method
and with the study of sensitivity and parametric analysis (Adler and Monteiro [1], Akg-ul [2],
Aucamp and Steinberg [3], Beale [5], Bland [6], Charnes [7], Dantzig [8], Gal [10, 11], Greenberg
[12], Hoffman [15], Magnanti and Orlin [16], Megiddo [17], Monteiro and Mehrotra [18], Ward and
Wendell [29], Williams [30], Wolfe [31]), with the convergence of the affine scaling interior point
algorithm (Barnes [4], Dikin [9], Hall and Vanderbei [14], Monteiro and Tsuchiya [19], Monteiro,
Tsuchiya and Wang [20], Tsuchiya [24, 25, 26], Vanderbei et al. [28], Vanderbei and Lagarias [27]),
and etc. The paper by G-uler et al. [13] surveys the theoretical and practical issues related to
degeneracy in the context of interior point methods for linear programming.
Recall that the LP problem optimize fc T x
A is an m \Theta n-matrix, is said to be primal nondegenerate if every feasible point x has at least m
positive components, and strongly primal nondegenerate if every x 2 IR n satisfying b has at
least m nonzero components (see Murty [21], page 121). These two concepts depend on A and b
only, and hence only on the feasible polyhedron of the LP problem. The above LP problem is said
to be dual nondegenerate if y has at least components for every dual
feasible solution y strongly dual nondegenerate (see Murty [21], page 253) if the same
property holds for every y 2 IR m . Note also that the two types of dual nondegeneracy depend only
on A and c, and hence only on the dual feasible polyhedron. Hence, it is natural to think of the
above notions of nondegeneracy as being concepts associated with polyhedra.
In the first part of the paper (Section 3), we study the concept of nondegeneracy of a general (not
necessarily pointed) polyhedron. polyhedron is said to be pointed if it contains a vertex.) Two
notions of nondegeneracy (corresponding to the polyhedron being nondegenerate and/or strongly
nondegenerate) are defined and then several equivalent conditions for each type of nondegeneracy
are given. Most of the results derived in Section 3 are well known in the context of pointed
polyhedra, but are scattered throughout the literature. Our goal here is to provide a unified
treatment of this subject and to generalize it to the context of not necessarily pointed polyhedra.
The results of Section 3 are not only interesting in their own right but are also needed for a full
understanding of the subject of Section 4.
In the second part of the paper (Section 4), we discuss the concept of constant cost nondegeneracy
(or simply, CC-nondegeneracy) of an LP problem whose feasible region is allowed to be a
non-pointed polyhedron. Tsuchiya [25] refers to this concept as dual nondegeneracy, a term which
is not appropriate since it is already used to refer to a different but related concept.
Consider the LP problem optimize fb T y is a (not necessarily pointed)
polyhedron. A nonempty face F of P is said to be a constant cost face of the LP problem
optimize fb T y j y 2 Pg if b T y is constant over F . When the reference to the LP problem is
understood, we simply say that F is a constant cost face. The LP problem optimize fb T y
is said to be CC-nondegenerate if every constant cost face is a minimal face of P .
face is said to be minimal if it does not properly contain any other nonempty face.)
One of the main results of Section 4, namely Theorem 4.4, states that CC-nondegeneracy of the
LP problem optimize fb T y j y 2 Pg is equivalent to the condition that the union of all minimal faces
of P be equal to the set of feasible points satisfying a certain generalized strict complementarity
condition. Moreover, when the polyhedron P is nondegenerate, we show that CC-nondegeneracy
is equivalent to the following condition: every point satisfying the generalized complementarity
condition must also satisfy it strictly (see Theorem 4.6).
We give below a preview of the main results of the paper when specialized to the context of
polyhedra and LP problems in standard form. First, we introduce the following notation. We
assume for the remaining part of this section that A is an m \Theta n matrix and b is an m-vector.
Given
the simply by A \Deltafi and if ng
we denote A fffi by A ff\Delta , or simply, A ff . Given a vector x 2 IR p and an index set ff '
denote the subvector [x i ] i2ff by x ff and the vector [jx i j] p
by jxj. Given two vectors x 2 IR p and
we denote the vector [x i s i
by x ffi s. If ff is a finite set then jffj denotes its cardinality.
The Euclidean norm is denoted by k \Delta k.
The polyhedron fx j is said to be nondegenerate if it satisfies any one of the
equivalent conditions of the result below.
Theorem 1.1 The following statements are equivalent:
(a) for any x 2 fx j is, x has at least m positive components);
(b) for any x 2 fx j the rows of A \Deltaoe(x) are linearly independent (that is, the
submatrix of A consisting of the columns corresponding to the positive components of x has
full row
(c) for any vertex x 2 fx j (that is, every vertex has exactly m
positive components);
(d) for any vertex x 2 fx j the submatrix A \Deltaoe(x) is nonsingular (that is, the
submatrix of A consisting of the columns corresponding to the positive components of x is a
basis of A);
0g, the set argminf kx ffi sk j A T y
contains exactly one point;
(f ) for any c 2 IR n and any constant cost face F of optimize fc T x 0g, the set
contains exactly one point;
(g) for any c 2 IR n , if the LP problem maxfb T y j A T y - cg has an optimal solution then it has a
unique optimal solution.
The polyhedron fx j is said to be strongly nondegenerate if it satisfies any one
of the equivalent conditions of the result below.
Theorem 1.2 The following statements are equivalent:
(a) for any x 2 IR n such that
(b) for any x 2 IR n such that the rows of A \Deltaoe(x) are linearly independent;
(c) for any x 2 IR n such that
(d) for any x 2 IR n such that m, the submatrix A \Deltaoe(x) is nonsingular;
(e) for any c 2 IR n and any x 2 IR n satisfying b, the set argminf kx
contains exactly one point;
(f ) for any c 2 IR n and any set of the form A j fx 2
ng and c T x is constant on A, the set f(y; s) 2 IR m+n j 9 x 2 A such that A T
contains exactly one point;
(g) for all c 2 IR n , every constant cost face of the LP problem optimize fb T y j A T y - cg is a
vertex.
Note that in the results above we have not assumed that the polyhedron fx j
is nonempty.
Regarding CC-nondegeneracy of an LP problem, we have the following two main results for
standard form LP problems. In the following two results, c denotes an n-vector.
Theorem 1.3 The LP problem optimize fc T x
CC-nondegenerate if and only if the set of all vertices of P is equal to the set
Theorem 1.4 Assume that P j fx j the LP problem
optimize fc T x j x 2 Pg is CC-nondegenerate if and only if the two sets
and (
are equal.
We end this introduction by pointing out the relationship between CC-nondegeneracy of an LP
problem in standard form and the strong dual nondegeneracy defined above. For the sake of future
reference, we repeat the definition below.
1 The LP problem optimize fc T x is said to be strongly dual non-degenerate
if for every (y; s) 2 IR m \Theta IR n such that A T y the vector s has at least
nonzero components.
Using a more general version of Theorem 1.2, namely Theorem 3.9, the following equivalence can
be proved under the assumption that the LP problem optimize fc T x
is strongly dual nondegenerate if and only if the LP problem optimize fc T x
CC-nondegenerate for every b 0 2 IR m (see Corollary (3.10)).
Notation and Terminology
In this section, we introduce some additional notation which will be used in the remaining part of
the paper.
If M is a matrix then Null(M) denotes the null space of M and Range(M) denotes the range
space of M .
In our study of nondegeneracy of polyhedra and LP problems, we consider the following poly-
hedron
ng.
The polyhedron P is said to be pointed if it contains a vertex. Throughout the remaining of
the paper, we let l denote the dimension of the lineality space Null(H) of P . It is well known that
P is pointed if and only if l = 0.
Given y 2 IR m and a
2\Omega g. For a face F of P , ri(F) denotes its relative interior. For any y 2 IR m , we denote the
corresponding slack vector by s(y) Hy. When the variable y is understood, we denote s(y)
simply by s. Also, we denote s(-y) by - s, s(-y) by - s, and etc. For y 2 P , F(y) denotes the smallest
face of P containing y. Finally, for any set ff ' I , ff c denotes the set I n ff.
For the purpose of future reference, we now make the following simple observations. Given
and two faces F and F 0 of P , we have:
ri F ,
Given a nonempty face F of P , there always exists a y 2 F such that
3 Nondegeneracy of a Polyhedron
In this section, we discuss two notions of nondegeneracy of a (not necessarily pointed) polyhedron.
We then provide several equivalent conditions for these two types of nondegeneracy. The results
of this section are not only interesting in their own right but are also needed for the discussion of
Section 4. Most of the results derived in this section, when specialized to the context of pointed
polyhedra, are well known in the research community but are scattered throughout the literature.
Hence, one of our goals is to provide a unified treatment of this subject.
In what follows, P denotes the polyhedron defined in (1). A nonempty face F of P is called a
minimal face if it does not have any nonempty face properly contained in it. The following result
gives the main properties of minimal faces that are used in our presentation. For its proof, we refer
the reader to Chapter 8 of Schrijver [23].
Proposition 3.1 Let l denote the dimension of the lineality space of P (hence,
and let F be a nonempty face of P. Then, F is a minimal face of P if and only if rank(H -(F)[E
l, in which case j-(F) [
Lemma 3.2 Given any y 2 P, there exists a minimal face F of P such that -(y) ' -(F).
Proof. Let y 2 P be given. We claim that if F(y) is not a minimal face then there exists -
such that -y) properly contains -(y). It is easy to see that using this claim a finite number of
times, we can construct a point -
y such that F j F(-y) is a minimal face and
thereby showing that the lemma holds. To show the claim, assume that F(y) is not a minimal face.
It follows from Proposition 3.1 and (2) that rank(H -(y)[E or equivalently, that
properly contains Null(H). Then, there exists d 2 Null(H -(y)[E ) such that H r d 6= 0
for some r 2 - c (y). By multiplying d by \Gamma1 if necessary, we may assume without loss of generality
that H r d ?
-d. It is now
easy to see that -y) ' -(y) [ frg, from which the claim follows.
Given b; -
define the following sets
I x I +H T
I x I +H T
I H T
;. The proof of the following lemma is left to the reader.
Lemma 3.3 Let b 2 IR m and -
be given. Then the following statements are equivalent:
(a) F(-y) is a constant cost face of the LP problem optimize fb T y
Lemma 3.4 Let b 2 IR m , a face F of P and -
ri (F) be given. Then X b (-y) ' X b (y) for every
Proof. We have -y) ' -(y) for every y 2 F . Hence the implication - s I
holds for every x 2 IR n , where -
This clearly implies the lemma.
The following theorem, which is the first main result of this section, gives several equivalent
characterizations of the notion of nondegeneracy of a polyhedron. The first four conditions are
"primal-type" characterizations with appealing geometric meanings while the other three conditions
are "dual type" characterizations.
Theorem 3.5 The following statements are equivalent:
(a) for any y 2 (there are at most m \Gamma l active hyperplanes at any feasible
(b) for any y 2 P, the set fH linearly independent (the normal vectors to the
active hyperplanes at any feasible point are linearly independent);
(c) for any minimal face F of P, (there are exactly m \Gamma l hyperplanes containing
a minimal
(d) for any minimal face F of P, the set fH linearly independent (the normal
vectors to the hyperplanes containing a minimal face are linearly independent);
I H T
contains exactly one point;
(f ) for any b 2 IR m and any constant cost face F of the LP problem optimize fb T y j y 2 Pg, the
set [fX b (y) j y 2 Fg contains exactly one point;
(g) for any b 2 IR m , if the linear program
I x I
subject to H T
I x I
x I - 0; xE unrestricted;
has an optimal solution, then it has a unique optimal solution.
Proof. (a) , (c): The forward implication follows from Proposition 3.1 and the reverse
implication follows from Lemma 3.2.
(c) , (d): Follows immediately from Proposition 3.1.
(b) , (d): The forward implication is trivial. The reverse implication follows from Lemma 3.2.
(b) Assume (b) holds and let b 2 Range(H T
I H T
Hence, due to (7), if -
xN is an optimal solution of
is a strictly convex quadratic program. Hence, - xN is uniquely determined.
Moreover, by (b), the columns of H T
B[E are linearly independent. These two observations together
with the fact that H T
implies that -
xB[E is also uniquely determined.
cost face F of optimize fb T y j y 2 Pg and y 2 F be given.
By Lemma 3.3, it follows that X b (y) 6= ;. This implies that E b and hence, by (e),
it follows that X b (y) contains exactly one point for every y 2 F . This together with Lemma 3.4
implies that [fX b (y) j y 2 Fg contains exactly one point.
holds and let b 2 IR m be such that (8) has an optimal solution. Let D
denote the optimal face of (8). It follows from the duality theorem that the dual of (8), namely the
problem maximize fb T y j y 2 Pg, has a nonempty optimal face F . By the complementary slackness
theorem, we know that D ' X b (y) for any y 2 F . This fact, (f) and the fact that F is obviously a
constant cost face of maximize fb T y j y 2 Pg implies that D contains exactly one point.
We will show that the set fH linearly
independent. Indeed, let - b j H T
is a feasible
solution of (8) with together with -
y, satisfies the strict complementarity condition.
Hence, it follows that the optimal face D of problem (8) with is given by
that the dimension of D is equal to the dimension of
holds by assumption, it follows that (8) with has a unique optimal
solution, and hence its optimal face has dimension zero. Thus, we conclude that the dimension of
is equal to zero, or equivalently, the set fH linearly independent.
In view of Theorem 3.5, we introduce the following definition.
is said to be nondegenerate if any one of the equivalent conditions of Theorem 3.5
holds.
We remark that nondegeneracy of a polyhedron is a notion that depends not only on the
polyhedron itself but also on its representation as a system of linear equalities and inequalities.
We can also define a stronger notion of nondegeneracy as follows.
3 P is said to be strongly nondegenerate if j-(y) [
g.
Note that strong nondegeneracy is a condition that depends on H , c and the index set E
only. More specifically, if P is strongly nondegenerate then any other polyhedron of the form
fy I g is strongly nondegenerate, where ? denotes a vector of - and -
symbols.
Similar to the concept of nondegeneracy, there are several equivalent ways to express the strong
nondegeneracy of a polyhedron. In what follows, we discuss this issue. For the purpose of stating
the next result, we need to introduce the following set:
Since, by Proposition 3.1,
is a minimal face of P
it follows that is a minimal face of Pg. Hence, the set M is a natural extension
of the set [fF j F is a minimal face of Pg.
A nonempty set A is said to be an affine set associated with P if fy
for some index set - ' I . It can be shown that for every affine set A there exists
A such that
We state the following lemmas whose proofs are similar to those of Lemma 3.2, Lemma 3.3 and
Lemma 3.4, and hence are left to the reader.
Lemma 3.6 Given any y 2 IR m satisfying HE
such that -(y) ' -y).
Lemma 3.7 Let b 2 IR m and an affine set A ' IR m be given. Then the following statements are
equivalent:
(a) b T y is constant over the set A;
(c) X b (y) 6= ; for every y 2 A.
Lemma 3.8 Let b 2 IR m and an affine set A ' IR m be given. Let -
A be such that
for every y 2 A.
We are now ready to state the second main result of this section. It gives several equivalent
characterizations of the notion of strong nondegeneracy of a polyhedron.
Theorem 3.9 The following statements are equivalent.
(a) for any y 2 IR m satisfying HE (i.e., P is strongly nondegenerate);
(b) for any y 2 IR m satisfying HE , the set fH linearly independent;
(c) for any y 2 M, j-(y) [
(d) for any y 2 M, fH linearly independent;
I H T
contains exactly
one point;
(f ) for any b 2 IR m and any nonempty affine set A ' IR m over which b T y is constant, the set
contains exactly one point;
(g) for all b 2 IR m , every constant cost face of the LP problem
optimize x2IR n c T
I x I
I x I
x I - 0; xE unrestricted;
is a vertex.
Proof. The equivalences and the implications (a) , (c), (c) , (d), (b) , (d), (b)
(f) can be proved using similar arguments as the ones used to prove the same equivalences and
implications of Theorem 3.5, except that now Lemma 3.6, Lemma 3.7 and Lemma 3.8 are used
instead of Lemma 3.2, Lemma 3.3 and Lemma 3.4. We next prove that (f) ) (g) and (g) ) (b).
holds and let b 2 IR m be given. Suppose that D is a constant cost face
of (10). D can be written as
for some index sets B ' I and for at least one x 2 D. Since D is a
constant cost face of (10), Lemma 3.3 implies thatB @
c N
c EC A 2 RangeB @
I N HN
where I N is the jN j \Theta jN j identity matrix. This implies that there exists a y 2 IR m such that
the affine set fy
and the fact that H T
imply that
b T y is constant over A. Hence, by (f), we conclude that D contains exactly one point, that is, that
D is a vertex.
We will show that the set fH
is linearly independent. Indeed, let - b j H T
Clearly, -
y, we know that c -y)[E 2
-y)[E ), and hence D is a constant cost face of (10) with b. By condition (g), we know
that D is a vertex. This implies that the set fH linearly independent.
Corollary 3.10 Let A 2 IR m\Thetan , b 2 IR m , c 2 IR n and assume that m. Then the LP
problem optimize fc T x strongly dual nondegenerate if and only if the LP
problem optimize fc T x
Proof. The assumption implies that the polyhedron fy
pointed. By this observation, Definition 1 and Definition 3, we conclude that strong dual non-degeneracy
of the LP problem optimize fc T x is equivalent to the condition
that the polyhedron fy strongly nondegenerate. From the equivalence of
(a) and (g) of Theorem 3.9 and the fact that every minimal face of fx j
a vertex, it follows that the latter condition is equivalent to the condition that the LP problem
be CC-nondegenerate for every b 0
4 CC-Nondegeneracy of a Linear Program
In this section, we discuss the notion of CC-nondegeneracy with respect to the LP problem
subject to y 2
and P is the polyhedron defined in (1). Problem (11) is allowed to be either a
maximization or a minimization problem. The main results of this section are Theorem 4.4 and
Theorem 4.6. Theorem 4.4 gives a characterization of CC-nondegeneracy of (11) for general feasible
polyhedron P while Theorem 4.6 gives an alternative characterization that holds only when P is
nondegenerate.
Throughout this section we consider the following two sets:
I x I +H T
I x I +H T
C is the set of feasible points satisfying the complementarity condition while SC is the set of feasible
points satisfying the same condition strictly.
The main of this section is to show that CC-nondegeneracy of (11) is equivalent to the condition
is minimal face of Pg (see Theorem 4.4) and, when the feasible polyhedron P is
nondegenerate, to the condition Theorem 4.6).
We start with the following result which follows as an immediate consequence of Lemma 3.3.
Proposition 4.1 is a constant cost face of (11)g.
The next result establishes an important relationship between the set SC and the maximal
constant cost faces of problem (11). First we need the following definition.
Definition 4 A face F of P is said to be a maximal constant cost face (of problem (11)) if it is a
constant cost face and is not properly contained in any other constant cost face.
Theorem 4.2
cost
Proof. Let F be a maximal constant cost face for (11) and let - y 2 ri F . We will show that
By (4), we have hence F(-y) is a maximal constant cost face. Hence, by
the equivalence of statements (a) and (b) of Lemma 3.3 we conclude that there exists an -
such that H T
Hence, assume that j-x B j 6? 0 and let
Consider the problem
subject to HB+
and its dual problem
subject to H T
It is easy to verify that -
x and - y are optimal solutions to problems (14) and (13), respectively.
Since every pair of primal and dual linear programs has a pair of optimal solutions satisfying
strict complementarity, we conclude that there exist optimal solutions - x and -
y of (14) and (13),
respectively, such that
Since every pair of optimal solutions of (13) and (14) satisfies the complementarity condition, we
have -
It then follows from (16) that - s N ? 0, and
hence -y). By (5), we conclude that F(-y) ' F(-y). Since - y is an optimal solution
of (13), it follows that the face F(-y) is contained in the optimal face of (13) and hence that F(-y)
is a constant cost face. Hence, we conclude that since F(-y) ' F(-y) and F(-y) is a
maximal constant cost face. Thus, we conclude that -
It then follows from (15) that - xB 0 ? 0: Using the fact that j-x
conclude that there exists a sufficiently small such that j-x B
noting that -
this shows that -
The following simple example shows that the two sets in (12) may differ.
Example 4.3 Consider the LP problem given by
maximize \Gammay 1
subject to \Gammay 1
denote the face of the feasible polyhedron in which the first constraint is active. Clearly,
the only maximal constant cost face is F 1 . It is easy to verify that hence that the
two sets in (12) differ.
The next result provides a characterization of CC-nondegeneracy of the LP problem (11).
Theorem 4.4 Assume that C 6= ;. Then, problem (11) is CC-nondegenerate if and only if
is minimal face of Pg; (18)
in which case, we have
Proof. We first prove the "only if " part. So assume that problem (11) is CC-nondegenerate.
Using Proposition 4.1, Theorem 4.2 and the CC-nondegeneracy of problem (11), we obtain
is a constant cost faceg
is a minimal faceg
is a minimal faceg
is a maximal constant cost faceg
On the hand, we know that SC ' C. Hence, we conclude from (19) that (18) holds and
For the "if " part, note that Theorem 4.2 and relation (18) imply
is a maximal constant cost is a minimal faceg:
This inclusion clearly implies that problem (11) is CC-nondegenerate.
Theorem 4.4 shows that CC-nondegeneracy of (11) implies that On the other hand,
the reverse implication may not hold as Example 4.3 illustrates. But when the polyhedron P
is nondegenerate, we will show in what follows that the condition implies that (11) is
CC-nondegenerate. With this goal in mind, we introduce the following set:
-(y) such that rank
I x I
The following theorem relates the set [ fri F j F is a maximal constant cost faceg with the set
Its proof is postponed until the end of this section.
Theorem 4.5 SC is a maximal constant cost face g.
As a consequence of this theorem, we obtain the following result with respect to problem (11)
when P is nondegenerate.
Theorem 4.6 Assume that P is nondegenerate. Then,
(a) is a maximal constant cost face
(b) problem (11) is CC-nondegenerate if and only if
Proof. We first prove (a). Combining Theorem 4.2 and Theorem 4.5, we obtain
is a maximal constant cost
Since P is nondegenerate, it follows from Theorem 3.5 that the set fH linearly
independent for any y 2 P . This observation implies that due to the definition of these
sets. Hence, (a) follows due to (21).
For (b), note that the "only if " part follows from Theorem 4.4. For the proof of "if " part,
assume that statement (a) and Proposition 4.1 then imply
is a maximal constant cost faceg
is a constant cost faceg:
This equality obviously imply that every constant cost face must be a minimal face, that is, problem
(11) is CC-nondegenerate.
We now turn our efforts towards proving Theorem 4.5. Several preliminary lemmas are needed.
The first one can be proved in the same way as Proposition 3.4 of Nemhauser [22] and hence, we
leave its proof to the reader. In what follows, the following notation is used. Given two index sets
we denote by [B; N ] the polyhedron
given by
Lemma 4.7 Let F be a face of P and assume that Assume that r 2 N is such
that the (possibly empty) set fy 2 F r g has dimension less than dim(F) \Gamma 1. Then,
Lemma 4.8 Let F and F 0 be two nonempty faces of P such that F ' F 0 and F 6= F 0 . Then there
exists an index r 2 -(F) n -(F 0 ) such that the face ~
satisfies that F ' ~
F
and dim( ~
Proof. Let ng ng
By (5), we know that B 0 ' B. For fy g. Obviously,
since otherwise we would have fy
and hence that r 2 -(F 0 ), a contradiction. Now assume for contradiction that for every r 2
g. Using Lemma 4.7, we can easily show by
induction that F In particular, F since
g. Since F is a subface of F 0 , it follows that
and N 2 are index sets such that since
must have Hence, it follows that . But this
contradicts the assumption that F 6= F 0 . Thus, we conclude there exists an index r 2 J such that
and the result follows by letting ~
Lemma 4.9 Let F and F 0 be two nonempty faces of P such that F ' F 0 and F 6= F 0 . Then there
exist a face -
F of P and an index r 2 -(F) n -
F) satisfying the following properties:
(a) F ' -
(c) rank
F)[frg
Proof. The proofs of statements (a) and (b) follow immediately from Lemma 4.8. It remains
to show (c). We first prove that H r is linearly independent from the rows of H -
F)[E . Assume for
contradiction that there exist scalars ff i with
Then, using (22) we obtain
F and H r it follows from (23) that
that r 2 -
F), a contradiction. We have thus shown that H r is linearly independent from the rows
of H -
F)[E . Using this fact and statement (a), we obtain
rank
F)[frg
Lemma 4.10 Let F be a constant cost face of P. Define the set
~
I x I +H T
F such that
I s I
Then, for any y 2 F and any x 2 ~
X(F), we have x T
I s I = 0.
Proof. Let y 2 F and x 2 ~
X(F) be given. By the definition of ~
I x I
b and there exists -
F such that x T
I
is a constant cost face and
y. Using this fact and the fact that HE
y, we obtain
I s I
I
y +H I -
I H I (-y \Gamma y)
We are now ready to prove Theorem 4.5.
Proof of Theorem 4.5. For any -
show that F(-y) is a maximal constant cost face
from which the inclusion of the theorem follows. Indeed, let - y 2 SC o be given. Since SC
follows that -
hence that F(-y) is a constant cost face, due to Proposition 4.1. Assume for
contradiction that F(-y) is not a maximal constant cost face, that is, there exists a constant cost
face F 0 such that F(-y) ' F 0 and F(-y) 6= F 0 . Applying Lemma 4.9 with
that there exists a face -
F and an index r 2 -y) n -
F) such that
rank
F)[frg
Letting
using relation (26), the definition of SC o and the fact that
we conclude that there exists -
such that
I -
x I +H T
By (6), we know there exists -
F such that
0: (28)
Hence, we have
I - s
F) is equal to zero by (28), -
is equal to zero by (27) and - x r -
s r is nonzero due
to (27) and (28) and the fact that r 2 B, r 62 -
F). On the other hand, since
(27) implies that -
I - s I = 0. This fact, relation (27), the definition of ~
F) and the fact that -
F
imply that - x 2 ~
F). Since F 0 is a constant cost face, it follows from (25) that -
F is also a constant
cost face. Using these two last conclusions, the fact that -
F and Lemma 4.10, we conclude that
I -
a fact that contradicts (30).
The reverse inclusion in Theorem 4.5 does not hold in general. To see this, consider the LP
problem of maximizing y 2 subject to the same set of constraints as the problem in Example 4.3.
Then, the vertex (1; 1) is the only maximal constant cost face, but (1;



--R

A geometric view of parametric linear programming

The computation of shadow prices in linear program- ming
A variation on Karmarkar's algorithm for solving linear programming prob- lems
Cycling in the dual simplex algorithm
New finite pivoting rules for the simplex algorithm
Optimality and degeneracy in linear programming

Iterative solution of problems of linear and quadratic programming
Postoptimal Analysis

An analysis of degeneracy


Cycling in the simplex algorithm

A note on degeneracy in linear programming
A general parametric analysis approach and its implication to sensitivity analysis in interior point methods
Global convergence of the affine scaling algorithm for convex quadratic programming
A simplified global convergence proof of the affine scaling algorithm
John Wiley
Integer and Combinatorial Optimization
Theory of Linear and Integer Programming
Global convergence of the affine-scaling methods for degenerate linear programming problems

Global convergence of a long-step affine scaling algorithm for degenerate linear programming problems

A modification of Karmarkar's linear programming algorithm
Approaches to sensitivity analysis in linear programming
Marginal values in linear programming
A technique for resolving degeneracy in linear programming
--TR
A note on degeneracy in linear programming
Theory of linear and integer programming
A variation on Karmarkar''s algorithm for solving linear programming problems
Integer and combinatorial optimization
Parametric linear programming and anti-cycling pivoting rules
Approaches to sensitivity analysis in linear programming
Global convergence of the affine scaling methods for degenerate linear programming problems
Global convergence property of the affine scaling methods for primal degenerate linear programming problems
A general parametric analysis approach and its implication to sensitivity analysis in interior point methods
linear programming;nondegeneracy;polyhedron;constant cost face;complementary slackness