An Interior-Point Approach to Sensitivity Analysis in Degenerate Linear Programs.
We consider an interior-point approach to sensitivity analysis in linear programming developed by the authors. We investigate the quality of the interior-point bounds under degeneracy. In the case of a special type of degeneracy, we show that these bounds have the same nice asymptotic relationship with the optimal partition bounds as in the nondegenerate case. We prove a weaker relationship for general degenerate linear programs.
Introduction
Sensitivity analysis (or post-optimality analysis) is the study of how the optimal solution
of an optimization problem changes with respect to the changes in the problem
data. The possible presence of errors in the problem data often makes sensitivity
analysis as important as solving the original problem itself.
In the context of linear programming (LP), sensitivity analysis can be performed
using an optimal basis approach (as in the simplex method) or an optimal partition
approach, where the optimal partition refers to knowing, for each index, whether the
corresponding component of an optimal primal solution or of an optimal dual slack
vector can be positive. The latter approach has close connections with interior-point
methods since such methods, when properly terminated, provide an optimal solution
in the relative interior of the optimal face, from which the optimal partition is readily
available. In fact, as will shortly be discussed in detail, the optimal partition approach
has been developed by Adler and Monteiro [1] and Jansen, de Jong, Roos and
[7] as a promising alternative in order to circumvent the drawbacks of the classical
optimal basis approach in the presence of degeneracy. Later, Monteiro and Mehrotra
[9] extended this approach by relaxing the requirement that the optimal partition be
known. They also provided two methods to estimate the range of perturbations, each
of which can be performed at any optimal solution, regardless of where it lies on the
optimal face. More recently, Greenberg, Holder, Roos and Terlaky [5] related the
dimension of the optimal set to the dimension of the set of objective perturbations for
which the optimal partition is invariant. Greenberg [4] considered the simultaneous
perturbations of the right-hand side and the cost vectors from an optimal partition
perspective.
Recently, the authors studied perturbations of the right-hand side and the cost
parameters in linear programming [12], motivated by how interior-point methods from
a near-optimal pair of strictly feasible solutions for a problem and its dual would
compare with the optimal basis approach obtained from a nondegenerate optimal basic
solution for such perturbations. The proposed interior-point perspective stems from the
objectives of regaining feasibility and maintaining near-optimality in a single iteration
of the interior-point method. This requires the setup of the "right" Newton system
among many possible choices in order to achieve both objectives simultaneously. Such
a perspective provides a basis for the comparison of the interior-point and the simplex
approaches to sensitivity analysis.
Under the assumption of a unique, nondegenerate optimal solution, the authors
showed that the Newton system proposed in [12] is the "right" one in the sense that it
yields asymptotically the same bounds on perturbations as those that keep the current
basis optimal (after symmetrization with respect to the origin). Similar results, but
changing only one of the primal or dual near-optimal solutions, were obtained by Kim,
Park and Park [8].
However, most LPs arising from real-life problems are degenerate. Our goal in this
paper is to investigate the quality of the bounds from the interior-point perspective in
the absence of the strong assumption of nondegeneracy. This will lead to a complete
analysis of the interior-point perspective proposed in [12]. In doing so, we need something
to compare our interior-point bounds with. In contrast to the nondegenerate
case, the presence of multiple optimal bases makes a simplex-based approach unsuit-
able, as will be explained shortly. We therefore compare our bounds to those obtained
from considering how much the right-hand side or the cost vector can change while
maintaining the same optimal partition. Consequently, we use completely different
tools for our analysis in this paper.
The next section is devoted to the preliminaries including the introduction of the
tools relevant for the analysis as well as the restatement of our interior-point approach.
Section 3 discusses the equivalence between the primal and dual formulations and shows
that it suffices to consider perturbations of the right-hand side only. We analyze the
interior-point bounds under a special case of degeneracy in Section 4 and extend the
analysis to the general degenerate case in Section 5. We present and discuss some
computational results in Section 6 and Section 7 concludes the paper.
Preliminaries
We consider the LP in the following standard form:
c T x; subject to
The associated dual LP is given by
subject to A T y
constitute the data, and (x;
are the decision variables. Throughout this paper, the coefficient matrix A will be
fixed and we will consider one-dimensional perturbations of the right-hand side vector
b and the cost vector c, i.e., b will be replaced by b + t\Deltab and c by c
and \Deltac will be fixed in IR m and IR n , respectively, and t 2 IR will be the parameter.
This is also called parametric analysis in the literature.
We will make the following assumptions:
1. The coefficient matrix A has full row rank.
2. Both (P) and (D) have strictly feasible solutions, i.e., there exist x ?
and y such that
The classical approach to sensitivity analysis has been based on the simplex method.
Assuming that an optimal solution exists, the simplex method terminates with a basic
optimal solution along with a corresponding basis. A natural criterion for the allowable
perturbations in the data is then given by the following: how much perturbation in the
data can one allow so that the current basis remains optimal for the perturbed LP?
Let us consider the parametric right-hand side (RHS) problem, i.e., let b be replaced
0g. It is well-known that v
is a convex, piecewise linear, continuous function of t. The parametric RHS problem
includes finding out all the "breakpoints" of v(t).
Fixing a value of t, say at 0 for the purposes of this paper, the classical approach to
sensitivity analysis then provides the set of values of t for which an optimal basis for
remains optimal for the resulting LPs parametrized by t. This is called the optimality
interval associated with an optimal basis. Note that the optimal basis approach
indeed yields the breakpoints of v(t) around 0 under primal and dual nondegeneracy
(which holds only if 0 itself is not a breakpoint of v(t)). However, the presence of
primal and/or dual degeneracies is a shortcoming for this approach since, for example,
multiple optimal bases might yield different optimality intervals. This shortcoming has
been observed by several researchers. Adler and Monteiro [1], and Jansen, de Jong,
Roos and Terlaky [7] developed an optimal partition approach to sensitivity analysis
and showed that the optimality intervals associated with the optimal partitions
uniquely and unambiguously identify the breakpoints of v(t) and the intervals between
the consecutive breakpoints. By the symmetry between (P) and (D), which will be
treated in more detail in Section 3, the same conclusions also hold for the parametric
analysis of the cost vector c.
The idea of the optimal partition is based on a well-known result of Goldman and
Tucker [2]. The optimality conditions for (P) and (D) are given by primal and dual
feasibility and complementary slackness, that is, a triple (x; y; s) is optimal for (P) and
(D) if and only if it satisfies
where x i and s i denote the ith components of x and s, respectively.
and\Omega D
denote the set of optimal solutions for (P) and (D), respectively. Then, we can define
two index sets as
ng
2\Omega D g: (2.2)
The optimality conditions (2.1) imply that B " ;. The Goldman-Tucker result
indicates that B and N actually partition the index set
ng. Therefore, there exist at least one primal solution x
2\Omega P and one dual
solution
2\Omega D such that x Such a solution will be called strictly
complementary and B and N will be called the optimal partition. In contrast to the
possibility of multiple optimal bases, the optimal partition is unique for a given LP
instance.
We will denote by B and N the columns of A corresponding to the indices in B
and N , respectively, and we will also partition the cost vector c as c B and c N , and the
variables x and s as xB and xN , and s B and s N accordingly. Note that if (x; y; s) is a
strictly complementary solution, then we have xB ? 0,
Let us again restrict our attention to one-dimensional perturbations of the right-hand
side vector b. The optimal partition approach is based on maintaining the whole
dual optimal set invariant rather than an optimal basis as in the classical simplex
approach. Note that perturbations of b do not affect the dual feasible region. Conse-
quently, the range of t is given by solving two auxiliary LPs. More precisely, if b is
replaced by b + t\Deltab, and
if\Omega D denotes the dual optimal set for (D) (i.e.,
the lower and upper bounds on t are given by the optimal values of
subject to
We will call the resulting bounds the optimal partition bounds. Note that both problems
are always feasible since together with any x
2\Omega P satisfy all the constraints.
Fixing the dual optimal
set\Omega D is equivalent to fixing the optimal partition B and N
by the Goldman-Tucker result. Therefore, the (possibly infinite) last constraint set in
(AUX1) can be replaced by the equivalent single constraint x T s
point in the relative interior
of\Omega D (hence s
This condition, in turn, is the same
as setting Consequently, (AUX1) can be written in the following simplified
subject to
The analogous derivation for the one-dimensional perturbations of the cost vector c
leads to the following auxiliary problems, whose optimal values give the optimal partition
bounds for t when c is replaced by c
subject to
Here, \Deltac B and \Deltac N constitute the corresponding partition of \Deltac.
Before getting into the symmetrized bounds we would like to recall an important
result about the dimensions of the optimal solution
and\Omega D . In what follows,
dim(\Delta) denotes the dimension and j \Delta j denotes the cardinality of a set. The reader is
referred to Lemma IV.44 in [10] for a proof.
Proposition 2.1
dim(\Omega
dim(\Omega
2.1 Symmetrized Bounds
The auxiliary problems (AUX1) and (AUX2) can be reformulated in the following
way. Let us consider (AUX1) and let x
2\Omega P . Then, the equality constraint can be
rewritten as
Therefore, by a change of variable, if we let
then (AUX1) is equivalent
to
subject to
Next, we will tighten the constraints in the above formulation by putting upper bounds
on u as well, and our choice for the upper bound will be x
B , which will give the largest
L1 -box around the origin which is contained in the feasible region:
subject to
We will call (SA1) the symmetrized LP and the resulting optimal solutions the symmetrized
bounds. The formulation of (SA1) reveals that if (u   ; -   ) solves the maximization
problem, then (\Gammau   ; \Gamma-   ) solves the minimization problem. Therefore, it suffices
to solve one LP as opposed to solving two LPs to obtain the optimal partition bounds
from (AUX1). A similar treatment of (AUX2) gives rise to the following symmetrized
LP:
subject to
\Gammas
which is obtained by replacing y \Gamma y   by v and s
N by w, where (y   ; s   )
2\Omega D .
Finally, a similar symmetrization has been applied to w.
Next, we would like to discuss the relationship between the auxiliary and the symmetrized
LPs. First of all, let us assume that both (P) and (D) have unique and
nondegenerate solutions. Then, Proposition 2.1 implies that B is actually a square
and nonsingular matrix, hence invertible. In fact, B is the optimal basis. Conse-
quently, (AUX1) and (AUX2) are trivial to solve and their optimal solutions coincide
with the optimal basis bounds arising from the simplex method. With this observation,
the constraints of (AUX1) reduce to
-B
B or -(X
B is the diagonal matrix whose components are given by x
B and e denotes the
vector of ones in the appropriate dimension. Similarly, the constraints of (SA1) can be
rewritten as
\Gammae -(X
is the L1 -norm. A similar treatment reveals that the constraints of
are equivalent to
-(S
N is defined similarly, and that those of (SA2) to
The derivations (2.3)-(2.6) imply the following relationship between the auxiliary
and the symmetrized LPs: let the optimal partition bounds given
by the optimal solutions of the auxiliary LPs (including possibly \Sigma1). Then, the
symmetrized bounds for t are (\Gamma- s
Therefore, the symmetrized bounds are indeed equal to the "symmetrization" of the
optimal partition bounds.
Next, let us assume that (P) has a unique but degenerate solution. Then, by
Proposition 2.1, B is nonsquare but it has full column rank. Therefore, (AUX1) is still
easy to solve. If \Deltab does not lie in the range space of B, then the optimal solutions
of (AUX1) and (SA1) are all zero (which implies that is a breakpoint of v(t)).
Otherwise, there exists a unique vector v such that \Deltab, and hence, the constraints
of (AUX1) are equivalent to
-(X
Similarly, the constraints of (SA1) can be stated as
Once again, we conclude that a similar symmetry as in (2.7) continues to hold between
(SA1) and (AUX1). In a similar manner, one can show that such a relationship holds
between (SA2) and (AUX2) if (D) has a unique but degenerate solution.
The preceding discussion shows that the optimal solutions of the auxiliary and
the symmetrized LPs have the nice relationship (2.7) as long as there is a unique
optimal solution that one can use to symmetrize the constraints of the auxiliary LPs
to obtain the symmetrized LPs. An interesting question then is whether the same
nice relationship continues to hold between the auxiliary and the symmetrized LPs
if there are multiple optimal solutions, that is whether the symmetrized bounds are
independent of the choice of the optimal solution used to symmetrize the constraints.
Unfortunately, the answer is no as shown by the following example. Let (P) be given
by 0g. Then (P) has multiple optimal
solutions given by with an optimal value
of 0. If the right-hand side is perturbed to (0; then the reader can
easily verify that (AUX1) yields (\Gamma1=3; +1) as the optimal partition bounds, whereas
the symmetrized bounds are (\Gammafi; +fi) if one uses the optimal solutions with
to symmetrize the constraints, and (\Gamma1=3; 1=3) if those with fi - 1=3 are used. This
example illustrates that in case of multiple optimal solutions, the symmetrized bounds
are dependent on the optimal solution used in the formulation of the symmetrized
LPs. Therefore, the relationship (2.7) no longer holds between the symmetrized and
the auxiliary LPs.
However, we will keep using the symmetrized LPs for two reasons. First of all, at
least in the unique solution case, they bear a nice relationship to the auxiliary LPs.
For our analysis, we will always choose an optimal solution in the relative interior of
the optimal set; therefore the symmetrization will hopefully allow more room for the
decision variables of the symmetrized LPs. Secondly, the symmetrized LPs are easier
to deal with than the auxiliary LPs and the symmetrized bounds will provide a good
comparison basis for our interior-point approach proposed in [12], as will be analyzed
in the subsequent sections.
2.2 Interior-Point Approach and Central Path Neighborhood

We will start with a brief review of the primal-dual path-following interior-point meth-
ods. The reader is referred to [11] for an extensive treatment. The central path is a
path of strictly feasible points (x(-); y(-); s(-)) parametrized by a positive scalar -.
Each point on the central path satisfies the following system for some - ? 0:
Under the two assumptions in Section 2, such a solution exists
and is unique for each positive -. Interior-point methods are iterative algorithms
that generate iterates which "follow" the central path in the direction of decreasing
- towards the primal-dual optimal
\Theta\Omega D . The iterates generated typically lie
in some neighborhood of the central path. For any given feasible iterate (x; the
duality gap is given by c T and we define the duality measure - as
denote the set of feasible and strictly feasible
primal-dual points respectively, that is,
One of the commonly used neighborhoods in interior-point methods is the so-called
wide neighborhood, denoted by N
where
At each iteration, given (x; (fl), the algorithm determines a search
direction (\Deltax; \Deltay; \Deltas). This direction is usually obtained by seeking an approximation
to the point on the central path corresponding to some parameter -, and then
applying Newton's method to the nonlinear system of equations (2.10). Finally, a
(damped) step is taken in this direction in such a way that the resulting iterate still
lies in N \Gamma1 (fl).
However, as in the context of target-following methods, one might seek an approximation
to a point other than the one on the central path. We will say that a
Newton step from (x; targeting the feasible pair of points
is the direction (\Deltax; \Deltay; \Deltas) obtained from the Newton's method applied
to (2.10) with -e replaced by X e:
A T \Deltay
Next, we describe the interior-point approach proposed by the authors in [12].
Given a primal-dual pair of LPs (P) and (D), let us assume that b or c is perturbed
in some fixed direction. Assuming strictly primal-dual feasible for (P) and
(D), a full Newton step is taken from (x; targeting "a feasible point"
of the perturbed LPs which satisfies X is possible that there is no
such feasible point for the perturbed LPs, however, the Newton step as given above
is still well-defined.) We state the results formally, referring the reader to [12] for the
proofs. Note, in particular, that the duality gap of the resulting feasible iterate for the
perturbed LPs is no greater than that of the original iterate.
Proposition 2.2 Assume that (x; y; s) is a strictly feasible point for (P) and (D) and
the right-hand side vector b is replaced by b+t\Deltab, where t 2 IR and \Deltab 2 IR m . Suppose
a Newton step is taken from (x; targeting the feasible pair of points
the perturbed pair of LPs that satisfies X a full Newton step will
yield a feasible iterate for the new problem if and only if
. Moreover, in this case the new iterate will have duality gap at
most x T s.
Proposition 2.3 Assume that (x; y; s) is a strictly feasible point for (P) and (D) and
the cost vector c is replaced by c Suppose a Newton
step is taken from (x; targeting the feasible pair of points of the perturbed
pair of LPs that satisfies X a full Newton step will yield a feasible
iterate for the new problem if and only if
. Moreover, in this case the new iterate will have duality gap at
most x T s.
Under primal-dual nondegeneracy, the bounds arising from Propositions 2.2 and
2.3 computed at near-optimal solutions for (P) and (D) asymptotically equal the symmetrized
bounds arising from (SA1) and (SA2) [12]. The goal of this paper is to
investigate the quality of these bounds in the absence of the nondegeneracy assumption

We first present a nice characterization of the distance of the strictly feasible primal-dual
points strictly complementary optimal solutions in terms of the
duality gap -n. Using this characterization, we derive some bounds on the components
of such points. In what follows, xB , xN , s B and s N denote the partitions of x and
s according to the optimal partition B and N as before. Furthermore, we will use
the bounds O(-), \Omega\Gamma -) and \Theta(-) interchangeably for scalars as well as vectors and
matrices by which we mean each entry satisfies the stated bounds. O(-) will indicate
that the quantity (in absolute value) is bounded above by some positive multiple of
-, where the multiple depends on the primal-dual instance (P) and (D) but does not
depend on the particular strictly feasible point or on -. Similarly, \Omega\Gamma -) will indicate
a lower bound by some positive multiple of - and \Theta(-) will mean a lower and upper
bound by some positive multiples of -.
The following proposition will be useful for the analysis that follows. Actually, the
proposition continues to hold for any feasible solutions and even for a point where
feasibility is violated by O(-). The statement below suffices for the purposes of this
paper.
Proposition 2.4 Let (x; y; s) be a strictly feasible point for (P) and (D) with duality
gap -n. Then, there exists a strictly complementary optimal solution
and (D) such that
Proof:
Optimal solutions of (P) and (D) satisfy the linear system
strictly feasible point satisfies the same
linear system with the third equality replaced by c T
[6] indicates that there exists a solution (-x; -
of the first system such that (-x; -
+O(-). The result follows immediately if (-x; -
s) is strictly complementary. If
not, there exists an arbitrarily small perturbation of (-x; -
s) which leads to a strictly
complementary solution and (2.17) follows since - ? 0.
The following corollary immediately follows from Proposition 2.4 since x
s
optimal solution of (P) and (D).
Corollary 2.1 Let (x; y; s) be a strictly feasible point for (P) and (D) with duality gap
-n. Then,
Note that both Proposition 2.4 and Corollary 2.1 hold for any primal-dual strictly
feasible (x; s). Next, we derive some more bounds by restricting the iterates to lie
in a wide neighborhood given by (2.13).
Proposition 2.5 Let (x; duality gap -n for (P) and (D). Then,
Proof:
similar argument shows
\Omega\Gamma126 Finally, together with s N
imply
O(-). The
proof of SB X \Gamma1
Equivalence
In this section, we show that the interior-point bounds are independent of the problem
formulation. It is well-known that although (P) and (D) do not look symmetric, they
can easily be reformulated so that (D) is in the form of (P) and vice versa. We briefly
review this reformulation. Let (-x; -
s) be such that
us
consider (D) first. The objective function can be rewritten as
where we used and the fact that every feasible pair (y; s) for (D) satisfies
Note that the first term is a constant: therefore maximizing b T y is the
same as minimizing - x T s. Let K 2 IR (n\Gammam)\Thetan be such that its rows form a basis for the
null space of A. Then, premultiplying the equality constraints in (D) by K yields
Moreover, if s satisfies (3.2), then c \Gamma s lies in the null space of K, for which the columns
of A T form a basis by definition of K. Therefore, there exists y such that A T
Consequently, (D) is equivalent to
x T s; subject to
Note in particular that K has full row rank by its definition. If we take the dual of
(D'), we obtain
subject to K T
It is not hard to see that (P) and (P') are also equivalent by a similar argument.
Therefore, the roles of (P) and (D) can be interchanged via this reformulation.
Let us now focus on perturbations of c, i.e., let c be replaced by c+t\Deltac. By the above
reformulation, this is the same as replacing the right-hand side of (D') by - c
Therefore, Proposition 2.2 can be used to evaluate the interior-point bound at a strictly
feasible primal-dual pair (s; x) (note that the roles of x and s are interchanged). We
need to compute
On the other hand, one can also use Proposition 2.3 to compute the interior-point
bound directly at (x; s), which requires the evaluation of
A simple manipulation of (3.3) gives rise to another equivalent formula:
where \Psi is the orthogonal projection matrix onto the range space of X \Gamma1=2 S 1=2 K T .
Similarly, (3.4) is equivalent to
where \Xi is the orthogonal projection matrix onto the null space of AX 1=2 S \Gamma1=2 . There-
fore, in order to prove that (3.3) and (3.4) are equivalent, it suffices to show that \Psi
and \Xi project onto the same subspace, or that the null space of AX 1=2 S \Gamma1=2 equals
the range space of X \Gamma1=2 S 1=2 K T . This is easily proven by an inclusion argument: if w
satisfies AX 1=2 S \Gamma1=2 Thus, w is in
the range space of X \Gamma1=2 S 1=2 K T . Conversely, if
AX This proves the equivalence of the interior-point bounds.
We next argue that the range of t resulting from the optimal partition bounds is
also independent of the formulation. If the two LPs are formulated in the form of (P)
and (D), then (AUX2) yields the range of t for perturbations of c. Premultiplying the
equality constraints of (AUX2) by leads to (AUX1') given by
min
w;-
w;-
which exactly yields the range of t for perturbations of the right-hand side of (D') if
one uses the form (D') and (P'). Similarly, if (w; -) is feasible for (AUX1'), then
lies in the null space of K. Then, by our previous observation, there exists v such
that which is exactly the constraints of (AUX2),
completing the proof of the claim.
Using this observation, we will carry out our analysis for perturbations of b only
in the subsequent sections, and state the corresponding results for changes in c as
corollaries. We begin with a special case of degeneracy first and then consider the
most general case.
4 Unique Primal Solution
Throughout this section, we assume that (P) has a unique but degenerate optimal
solution x   . Note that by Proposition 2.1, we have linearly
independent columns. In this particular case, Proposition 2.4 provides another useful
bound on xB for a strictly feasible primal-dual point (x;
Corollary 4.1 Assume that (P) has a unique optimal solution x   . Let (x; y; s) be
primal-dual strictly feasible for (P) and (D) with duality gap -n. Then,
An analogous corollary follows if (D) has a unique solution.
Corollary 4.2 Assume that (D) has a unique optimal solution (y
be primal-dual strictly feasible for (P) and (D) with duality gap -n. Then,
Next, we will analyze one-dimensional perturbations of b.
4.1 Perturbations of b
In this subsection, we assume that the right-hand side vector b is replaced by b
We also assume that (x;
strictly feasible point for (P) and (D) for some fl 2 (0; 1]. We will compare the interior-point
bounds arising from Proposition 2.2 at with the optimal values of (SA1),
i.e., the symmetrized bounds. The interior-point bounds are given by the L1-norm of
where
Let us now consider (SA1). Since B has full column rank, \Deltab either does not lie in
the range space of B, in which case the optimal values of (SA1) as well as (AUX1) are
all 0, or there exists a unique v 2 IR jBj such that \Deltab, in which case the constraints
of (SA1) reduce to (2.9), from which the symmetrized bounds can be obtained easily.
We will consider both situations in turn.
Let us start with the second case. Without loss of generality, we can assume that
\Deltab has unit L 2 -norm, which implies a bound on v. Then, we need to compute
in order to obtain (4.3). However, (4.4) is equivalent to
where B and N are the partitions of the coefficient matrix A with respect to B and
N as before. Since B has linearly independent columns, there exists a matrix C 2
IR m\Theta(m\GammajBj) such that the augmented matrix [B C] is square and nonsingular: let W
be its inverse. Therefore, premultiplying the second equality in (4.5) by W , we obtain
I#
~
I#
where ~
I is a jBj \Theta jBj identity matrix. Therefore, if we
partition ~
N and ~
accordingly as
~
~
~
~
can then be decomposed in the following way:
~
~
~
~
~
~
v#
where DB and DN are the corresponding partitions of D. By (4.3), we need to compute
For notational convenience, let us define
F := ~
Note that G has full row rank since A does. The bottom equality in (4.7) can be
rewritten as
Substituting (4.9) in the top equality in (4.7) gives
~
~
where PG is the orthogonal projection matrix onto the range space of G T . Therefore,
I \Gamma PG is the orthogonal projection matrix onto the null space of G.
We briefly review the Neumann lemma now [3]. Let U be an invertible matrix and
being used does not really matter:
we will always use k \Delta k for the Euclidean norm or the operator norm arising from it.)
Then, I +U \Gamma1 V is invertible with kI +U 2. Moreover U
given by
Now, we apply this result to (4.10) with U := D 2
2.5 implies that both U \Gamma1 and V are O(-) since I \Gamma PG is a projection matrix and has
unit Euclidean norm. Therefore, assuming the duality gap -n is small,
~
I +D \Gamma2
It then follows that
I +D \Gamma2
However, by Proposition 2.5, F is O(- 1=2 ), D \Gamma2
B is O(-) and X \Gamma1
B is O(1). Consequently,
the second term on the right hand side of (4.13) is O(- 2 ) since kI \Gamma PG k - 1. Finally,
Corollary 4.1 implies X \Gamma1
We have thus obtained the top part of (4.8). For the lower part, we get
where we substituted (4.9) for ~
Proposition 2.5 implies (XN SN
Combining these bounds with
leads to
Using (4.8), we conclude that the L1-norm of the quantity (4.3) we need to evaluate
is given by
O(-)
The reciprocal of (4.17) gives the desired interior-point bound. Consequently, if the duality
gap -n is small, we conclude by comparing (4.17) with (2.9) that the interior-point
approach yields exactly the same bound as the optimal solution to (SA1) asymptotically
in -.
Next, we address the situation where \Deltab does not lie in the range space of B. In this
case, the optimal values of both (AUX1) and (SA1) are clearly 0. \Deltab can be uniquely
written as
where [B C] is nonsingular as before and v C is a nonzero vector. Once again, we need
to compute (4.3). We follow a similar treatment as before, and corresponding to (4.7)
we
~
~
~
~
~
~
The bottom part can be expanded as
~
~
~
However, (4.8) implies that the term in the brackets is exactly the bottom part of the
quantity (4.3) we seek. Let us denote that term by p and let XN
is equivalent to ~
nonzero, the norm of q is bounded below,
that is, kqk - ff ? 0 where ff is the norm of the least squares solution. Therefore,
e.g. [3]). (Note that jBj ! n since
can happen only if case \Deltab is always in the range of B.) However,
k1 kpk1 since XN This implies
kXN k1
where the last equality follows from Corollary 2.1. Therefore, as - tends to 0, kpk1
tends to 1, which implies that the interior-point bound given by its reciprocal tends
to 0 as desired.
We remark that if is the only optimal solution of (P), which can
happen only if In this case, the top part of (4.8) disappears. The interior-point
bound is then given by the reciprocal of kpk1 , where p is as defined after (4.20). By
the preceding argument, the interior-point bound tends to 0 as - approaches 0. This
is still in agreement with the optimal partition bounds since any nonzero perturbation
of b leads to a change in the optimal partition and hence, the optimal partition bounds
in this case are also equal to 0. Therefore, we have proved the following theorem:
Theorem 4.1 Let (x; be a primal-dual strictly feasible point for (P)
and (D). Assume that (P) has a unique but degenerate optimal solution and that b
is replaced by b . Then the interior-point bound
evaluated at yields exactly the same value as the optimal solution of (SA1)
asymptotically in -, where
The following corollary of Theorem 4.1 is an immediate consequence of the equivalence
between (P) and (D) as discussed in Section 3. One uses Corollary 4.2 in place
of Corollary 4.1 in the preceding analysis.
Corollary 4.3 Let (x; be a primal-dual strictly feasible point for (P)
and (D). Assume that (D) has a unique but degenerate optimal solution and that c is
replaced by c+t\Deltac where t 2 IR and \Deltac 2 IR n . Then the interior-point bound evaluated
at yields exactly the same value as the optimal solution of (SA2) asymptotically
in -, where
It does not appear that we can obtain better results for perturbations of c in the
case of a unique primal optimal solution (but not dual optimal solution) than those
arising from the analysis of the general case in the next section. A similar remark holds
for perturbations of b in the case of a unique dual optimal solution (but not primal
optimal solution).
5 General Case
In this section, we turn our attention to the most general case where both (P) and (D)
may have multiple optimal solutions. As the small example given at the end of Section
2.1 reveals, some complications arise in the presence of multiple optimal solutions. For
instance, unlike the previous case, the symmetrized bounds become dependent on the
optimal solution of (P) used in the formulation of (SA1) if (P) has multiple optimal
solutions. Furthermore, they do not necessarily coincide with the "symmetrizations"
of the optimal partition bounds arising from (AUX1). Similar remarks hold for the
relationship between (SA2) and (AUX2) if (D) has multiple optimal solutions.
Despite this complication arising from the presence of multiple optimal solutions,
we aim to be able to say something about the quality of the interior-point bounds at
least in comparison with the symmetrized bounds. In the next subsection, we analyze
perturbations of b in this general setting.
5.1 Perturbations of b
Let (P) have multiple optimal solutions and let b be replaced by b
and \Deltab 2 IR m . Suppose that (x; strictly feasible where
For such a point, Proposition 2.4 guarantees the existence of a strictly
complementary solution whose distance from (x; y; s) is bounded above by
the duality gap n-. We will compare the interior-point bounds evaluated at
with the optimal values of (SA1). Among other optimal solutions of (P), the x   above
will be the particular choice of the primal optimal solution to be used in the formulation
of (SA1). The use of such an optimal solution in the relative interior of the primal
optimal set is likely to leave more room for the decision variables of (SA1) since x
Let us first consider (SA1). The constraints of (SA1) are
k. Clearly we have r - m and r ! k since Proposition 2.1
implies
dim(\Omega which is positive by our assumption. This, in turn, implies
that r ? 0 since (assuming no columns of A are identically
zero). A QR factorization of B yields orthogonal and
R 2 IR m\Thetak is upper triangular with
R 1#
rows. Note that R 1 has full row rank.
Premultiplying the equality constraints in (5.1) by Q T yields
R 1#
f
with f
that (SA1) has a nontrivial optimal solution
-   if and only if f
First, we consider the nontrivial case. (Since f
\Deltab is nonzero, this implies that k ? 0.)
Let (-   ; u   ) be an optimal solution to the maximization problem with -   6= 0. Note
that -   is finite since u   is bounded (this follows since B 6= ;). Then, we have
f
The interior-point approach, on the other hand, requires the evaluation of (4.3) at
s). By (5.4), we then need to evaluate the L1-norm of
Let
Premultiplying the second equality in (5.6) by Q T gives
~
R T
~
~
~
R 1#
where ~
are the appropriate partitions of ~
are those
of ~
us define
F := ~
can then be decomposed into two equations as
Note, in particular, that both G and H have full row rank since R 1 and A do. From
the second equation in (5.9), we obtain
~
Substituting (5.10) in the first equation of (5.9) leads to
where I \Gamma PH is the orthogonal projection matrix onto the null space of H. Proposition
2.5 implies that the second term in parentheses in the second equation above is O(-)
since kI \Gamma PH k - 1. In order to apply Neumann's lemma, we need to show that
Lemma 5.1 (GG
Proof:
We use the "thin" QR factorization of G
columns and Z is upper triangular and nonsingular. Then, (GG
Therefore, it suffices to find an upper bound on Z \Gamma1 . We have
Therefore, (R
(R
Y . However, by
Proposition 2.5, D \Gamma1
which implies that Z completing the
proof.
We can now apply Neumann's lemma to (5.11). Using the same notation as in
(4.11) we have U := GG T and V := F . Note that both U \Gamma1 and V are
O(-). We obtain
~
where we used R
By (5.5) and (5.6), we need
Let us define
For the top part of (5.14) we need to evaluate
where we used (5.13), (5.15) and where PG is the orthogonal projection matrix onto
the range space of G T . Consider the second term in the right hand side of the second
equality. By Proposition 2.5, (SB XB ) \Gamma1=2 is O(- \Gamma1=2 ), V is O(-) and D \Gamma1
B is O(- 1=2 ).
Lemma 5.1 implies that
fore, the whole expression is O(- 2 ). We conclude that the top part of (5.14) is
Let us next consider the lower part of (5.14). We need to compute
~
~
By (5.13) the first term in (5.18) is given by
Note that by the preceding discussion. As for the second term in brack-
ets, we have both (GG are O(-), which implies the whole second term is
O(- 5=2 ). Thus, the expression in brackets is O(- 1=2 ). By Proposition 2.5, (SN XN ) \Gamma1=2
is O(- \Gamma1=2 ), whereas both F T and D \Gamma1
are O(- 1=2 ). We therefore conclude that (5.19)
is O(-).
For the second term in (5.18), we use (5.10) together with (5.13):
\Gamma(S
Note that ~
O(-) by the preceding arguments. The fact that kPH k - 1 together
with (SN XN ) \Gamma1=2 being O(- \Gamma1=2 ) and F T being O(- 1=2 ) implies (5.20) is O(-).
Therefore, we conclude that the lower part of (5.14) is O(-). Combining this result
with (5.17) yields the following:
r := (1=-   )
O(-)
Consequently, we need to evaluate the L1-norm of (5.21) and take its reciprocal.
Observe that X \Gamma1
Proposition 2.4. Using this, we derive an
upper bound on the L1-norm of (5.21).
Thus, . Furthermore, since
e.g. [3]), where k. Finally, since u   is
optimal for (SA1), k(X
Therefore,
/s
We conclude that the interior-point bound, which is the reciprocal of (5.24), is then
bounded below bykrk 1
Note, in particular, that the lower bound tends to 1=
k, independent of n, as
if s) is on the central path.
We next consider the case where \Deltab is not in the range space of B. Again, in this
case, the symmetrized bounds as well as the optimal partition bounds are all 0. The
QR factorization of B can be rewritten as
use (5.2) and [Q 1 is the appropriate partition of Q. Since Q is orthogonal, \Deltab
can uniquely be expressed as
Arguing similarly to Section 4, we need to evaluate (4.3), which
in turn requires the computation of
Premultiplying (5.27) by Q T leads to
~
R T
~
~
~
which looks like (4.19). Essentially the same arguments as in Section 4 reveal that the
interior-point bound tends to 0 as - approaches 0.
Therefore, we have proved the following theorem.
Theorem 5.1 Let (x; be a primal-dual strictly feasible point for (P)
and (D) with duality gap -n. Assume that (P) has multiple optimal solutions and that
b is replaced by b . If the strictly feasible solution
given by Proposition 2.4 is used for symmetrization in (SA1), then the ratio of the
interior-point bound evaluated at (x; y; s) to the value of the optimal solution of (SA1)
is at least p
Note that the presence of multiple primal optimal solutions implies k ? 0, therefore,
the expression (5.29) is well-defined. As in Section 4, Theorem 5.1 leads to the following
corollary by the discussion in Section 3. Due to the interchange of the roles of the basic
and nonbasic variables in the reformulation given in Section 3, k in the denominator of
is replaced by (n \Gamma k). Under the assumption of multiple dual optimal solutions,
Proposition 2.1 indicates that m ? r, which implies k ! n since A has full row rank.
Corollary 5.1 Let (x; be a primal-dual strictly feasible point for (P)
and (D) with duality gap -n. Assume that (D) has multiple optimal solutions and that
c is replaced by c . If the strictly feasible solution
given by Proposition 2.4 is used for symmetrization in (SA2), then the ratio of the
interior-point bound evaluated at (x; y; s) to the value of the optimal solution of (SA2)
is at least p fl
6 Computational Results
In the previous sections, we have provided a theoretical basis for the behavior of the
interior-point bounds evaluated at the near-optimal solutions. We present some computational
results in this section to shed some light on the performance of the interior-point
bounds in practice.
We have generated random LPs with 400. The input parameters
are the number of basic variables (jBj) and dimension of the primal optimal set
(dim(\Omega P )), which together
determinedim(\Omega D ) and rank(B). This allows us to incorporate
all scenarios of primal and dual degeneracies into the random LPs. We first
generate a suitable matrix A, then a strictly complementary pair of solutions, and
finally set b and c to make these feasible and hence optimal.
Having generated a random LP with the prespecified degeneracies, we obtain a
strictly feasible, near-optimal solution by perturbing the known strictly complementary
optimal solution. Next, random perturbations of b and c are generated in the correct
subspaces so that (AUX1) and (AUX2) have nontrivial optimal solutions. We compute
the interior-point bounds evaluated at those near-optimal solutions and compare
them with the optimal solutions to (AUX1) and (AUX2) as well as the optimal solutions
to the symmetrized LPs (SA1) and (SA2), where the initially generated strictly
complementary optimal solution is used to symmetrize the constraints.
We present our results for various degeneracy scenarios in Table 6. Eight instances
with various levels of primal-dual degeneracies are reported. For each instance, the
interior-point bounds are evaluated at two iterates corresponding to each row. DP and
DD are the dimensions of the primal and dual optimal sets, respectively. - is the duality
gap measure given by x T s=n, and fl is the parameter of the narrowest wide central-
path neighborhood containing the iterate. (AUX1) and (AUX2) are the minimum
of the absolute values of the optimal values of the corresponding minimization and
maximization problems (symmetrizations). (SA1) and (SA2) are the optimal values of
the symmetrized maximization problems. Finally, IPB and IPC are the upper interior-point
bounds for changes in b and c evaluated at the corresponding iterates.
The predicted nice theoretical behavior of the interior-point bounds is exhibited
in Instances 1,2 and 4 for changes in b and in Instances 4,6 and 8 for changes in c.
Observe that the bounds converge to the symmetrized bounds even though fl is very
small, which is typical in practice. For the remaining degeneracy scenarios, the interior-point
bounds lie within a factor of the symmetrized bounds as discussed in the previous
section. It is worth noting, however, that the actual ratio seems to be much better
than the theoretical worst-case ratios (5.29) and (5.30). In our extensive computational
tests, the ratio was never worse than a hundredth although the predicted lower bounds
and (5.30) are on the order of 10 \Gamma5 in most of the instances.
Finally, we note that the condition number of AD 2 A T blew up in all of the degenerate
instances as expected. Therefore, the numerically unstable results have been
discarded. Furthermore, the bound for changes in b seems to be computationally much
more stable than its counterpart for c; however, this is most likely due to the fact
that we use (2.15) and (2.16) to compute the bounds. By the equivalence discussed in
Section 3, this problem can be overcome using (3.3) instead of (3.4) at the extra cost
of computing K, which can easily be obtained by a QR factorization of A T .
7 Conclusion
In this paper, we have studied the quality of the bounds arising from the interior-point
perspective on sensitivity analysis developed by the authors in [12]. By relaxing
the strong assumption of nondegeneracy, we have been able to consider all possible
degeneracy scenarios and to investigate how our bounds compare with those arising
from the optimal partition approach to sensitivity analysis.
If the primal problem has a degenerate but unique optimal solution, then our approach
yields the same bounds as the "symmetrized" optimal partition bounds for
perturbations of b. By the equivalence discussed in Section 3, the same relationship
holds for perturbations of c if the dual problem has a degenerate but unique opti-
Table

1:
Computational
Results
(m
200,
Ins
DD
IPB
IPC40160e-5e-65.47264.1633.005e-3e-63.06112080e-5e-614.61327.6653.806e-3e-62.670120140e-5e-52195.607223.65325.957e-3e-525.9572000e-6e-50.6760.008300.00829e-4e-50.00823200100e-5e-54030.46669.4843.086e-3e-53.0992800e-7e-5220.6561.5611.561e-5e-51.547280100e-4e-48512.007115.83438.813e-3e-438.5403600e-6e-4552.0142.6362.638e-4e-4
87.
mal solution. This result directly extends the previous result proved in [12] under the
assumption of a unique and nondegenerate solution.
We then considered general degenerate LPs. In this case, we were able to show that
our interior-point approach would yield bounds that are at least a certain fraction of
the symmetrized bounds, where the fraction depends on certain characteristics of the
problem instance and of the iterate at which the bounds are evaluated. Our extensive
computational tests suggest that the ratio in practice is much better than the predicted
worst-case ratio. Although this result is not as strong as the aforementioned results,
our interior-point bounds still yield some useful information on the range of allowable
perturbations. The fact that the cost of the evaluation of our bounds is simply the
same as that of an interior-point iteration makes it more appealing given the cost of
solving two LPs to obtain the range from the optimal partition approach.



--R

A geometric view of parametric linear program- ming
Theory of linear programming.
Matrix Computations.
Simultaneous primal-dual right-hand-side sensitivity analysis from a strictly complementary solution of a linear program
On the dimension of the set of rim pertubations for optimal partition invariance.
On approximate solutions of systems of linear inequalities.
Sensitivity analysis in linear programming

A general parametric analysis approach and its implication to sensitivity analysis in interior point methods.
Theory and Algorithms for Linear Optimization

Sensitivity analysis in linear programming and semidefinite programming using interior-point methods
--TR
degeneracy;sensitivity analysis;linear programming;interior-point methods