BIB-VERSION:: CS-TR-v2.0
ID:: CORNELLCS//TR93-1398
ENTRY:: 1994-03-17
ORGANIZATION:: Cornell University, Computer Science Department
LANGUAGE:: English
TITLE:: Condition Numbers for Polyhedra with Real Number Data
AUTHOR:: Vavasis, Stephen A.
AUTHOR:: Ye, Yinyu 
DATE:: November 1993
PAGES:: 9
ABSTRACT::
We develop a condition-based complexity analysis for homogenous polyhedra 
with real number data. We analyze the dependency of primal-dual interior point 
algorithm efficiency on this condition number for finding a point in a 
polyhedron.

Key Words: polyhedron, interior point algorithms, condition-based 
complexity.
END:: CORNELLCS//TR93-1398
BODY::
Condition Numbers for Polyhedra
With Real Number Data
Stephen Vavasis*
Yinyu Ye**
TR 93-1398
November 1993
Department of Computer Science
Cornell University
Ithaca, NY 14853-7501
* Department of Computer Science, Cornell University, Ithaca, NY. Email
vavasis?cs.cornell.edu. This work supported in part by the National Science
Foundation, the Air Force Office of Scientific Research, and the Office of Naval
Research, through NSF grant DMS-8920550. Also supported in part by an NSF
Presidential Young Investigator award with matching funds received from AT&T and
Xerox Corp. Part of this work was done while the author was visiting Sandia National
Laboratories, supported by the U.S. Department of Energy under contract DE-AC04-
76DP00789.
** Department of Management Sciences, The University of Iowa, Iowa City, Iowa
52242. Research was supported in part by NSF grant DDM-9207347. Part of this
work was done while the author was on a sabbatical leave from the University of Iowa
and visiting Cornell Theory Center, Cornell University, Ithaca, NY 14853, supported in
part by the Cornell Center for Applied Mathematics and by the Advanced Computing
Research Institute, a unit of the Cornell Theory Center, which receives major funding
from the Naional Science Foundation and IBM Corporation, with additional support
from New York State and members of its Corporate Research Institute.
Condition Numbers for Polyhedra with Real
Number Data
Stephen VAVASIS* and Yinyu YEt
September 1993
Abstract: We develop a condition-based complexity analysis for homogeneous poly-
hedra with real number data. We analyze the dependency of primal-dual interior point
algorithm efficiency on this condition number for finding a point in a polyhedron.
Key words: polyhedron, interior point algorithms, condition-based complexity.
*Department of Computer Science, Cornell University, Ithaca, NY. Email: vavasis?cs.cornell.edu. This
work supported in part by the National Science Foundation, the Air Force Office of Scientific Research,
and the Office of Naval Research, through NSF grant DMS-8920550. Also supported in part by an NSF
Presidential Young Investigator award with matching funds received from AT&T and Xerox Corp. Part
of this work was done while the author was visiting Sandia National Laboratories, supported by the U.S.
Department of Energy under contract DE-AC04-76DP00789.
tDepartment of Management Sciences, The University of Iowa, Iowa City, Iowa 52242, USA. Research
was supported in part by NSF grant DDM-9207347. Part of this work was done while the author was on
a sabbatical leave from the University of Iowa and visiting the Cornell Theory Center, Cornell University,
Ithaca, NY 14853, supported in part by the Cornell Center for Applied Mathematics and by the Advanced
Computing Research Institute, a unit of the Cornell Theory Center, which receives major funding from
the National Science Foundation and IBM Corporation, with additional support from New York State and
members of its Corporate Research Institute.
0
1 Introduction
Consider the following polyhedron:
= fx: Ax --H 0 e?x = 1, x > 01,
where A E ?mxn with rank m is given, e is the vector of all ones, and T denotes transpose.
This is the homogeneous form proposed by Karmarkar [1]. ? is said to be feasible if and
only if ? # ?. Given an A, there is unique partition of the columns of A, A = (B, N), such
that the set
= ?xB: BxB = 0, eTx? = 1, XB > 01,
has a strictly feasible point or an interior point in the positive orthant, and the dual set
??=[(y,s): BTy=o, NTy<0, eT(?NTy)=1, s=?ATy1,
has a strictly feasible point, i.e., a feasible (y, s) with sN = ?NTy <0. (We use s, the slack
vector, to simplify notations.) It is also known that XN = 0 for any x ? ?. Thus, ? is
infeasible if and only if A =
The assumption that ? is in homogeneous form is without loss of generality (although see
the concluding remark). Consider the standard nonhomogeneous linear feasibility system:
= [x: Ax = b, x > 01.
We can construct a related homogeneous system ? using
A = (A, -b).
Then, ? is feasible if and only if column b is in B, the unique partition identified for ?.
Suppose we want to answer the following question using an interior point method:
(P) Is ? feasible?
In this note, we develop a condition-based complexity analysis of problem (P), and show how
a condition number of A may affect algorithm efficiency in solving problem (P). Then, we
show how this condition number relates to another condition number of A defined by [6] and
[7]. Other condition numbers of A were used in error bound analysis [3] [2] and convergence
analysis [5].
2 An interior-point algorithm for solving (P)
First, we propose to apply an interior-point algorithm to solve a related linear programming
(LP) problem:
(LP) minimize x0
subject to --H(Ae)xo + Ax --H 0 eTx < 1, (xo,x) > 0,
The dual of (LP) is
(LD) maximize Yo
subject to eyo + ATy < 0,			eTATy < 1, Yo <0
We use so = 1+eTATy and s = eyo?ATy to denote the slack variables of (LD). Obviously,
x00 = 1/(n + 1) and x0 = e/(n + 1), y0 = 0 and Yo0 = --H1 with slack so = 1 and s0 = e are
feasible points for the (LP) and (LD), respectively. Moreover, they are on the central path
with initial duality gap
= x00s0o+(xO)TsO+(1--HeTx0)(?y00) _ 1
n+2			n+1
Starting from this point, an O(7nL) (primal-dual) interior-point algorithm will generate a
sequence of f(xk, yk)?, starting from (x0, y0), such that
min (x,k.s,k.) > o?k and 1tk < (1 --H p/vm2)?k?1 (1)
o<j<n
for some constants 0 <a, P < 1.
Consider a condition number of A, defined as
x?: XB ?
:			(y,s) E ?d1			(2)
a? =mini??tmax
ad = mini??tmax
a(A) = min(ap,a?).
(we assign a? (a?) to 1 if B (N) is null.) It has been shown that the interior-point algorithm
generates a sequence of partitions (Bk, Nk) --H A such that, after O(?(I log a(A)I + log n))
iterations, we have convergence to Bk = B and Nk --H N (see Ye [11]). It seems that this
result could be used to answer question (P) to determine whether A = N or not. However,
this requires a(A) as a priori information. Without knowledge of a(A), we have to provide
a witness whether A = N or not.
Here is an example of the analysis in [11j. It has been shown that if A = N, then for any
k, the sequence (xk, yh) satisfies
5k.>as*./(n+2), 1<5 <n
for any (y*, s*) in ?d (for example, see Ye [11]). Thus,
s3k >aa(A)/(n+2), 1<5<n.
Consider a least-squares projection at the kth iteration of the algorithm
minimize			lid5 ii
subject to			ATdy + skd8 --H eyok,
where 5k is diag(sh). We have a closed form for d8 that is
d5 = yokP?(s?)?i(sk)?le
2
(3)
(4)
where PA is the projection matrix to the null space of A. Let
= yk + dy and s+ --H sk + Skd5 = ?AT(y + dy) = ATy+
Note that from (3) and (4)
Thus, if
then lid5 ii < 1 and
Ild5il < lyti II(Sk)?1 II hell < (n+2)1.5			k
aa(A)			lYol.
lyti = yk <xk?y? = (n+2)ik ? (n+2)15,
= S?(e+d5) >0.
That is, after a constant-factor scaling, y+ is an interior point in ?d with A = N, therefore,
proving A = N. Thus, a witness that (P) is infeasible can be also found in O(#n(I log ?(A)I+
log n)) iterations. Similarly, the case A = B can be proved in the same number of iterations.
In fact, all other cases can be completed in about the same number of iterations to obtain
(B, N), and to generate feasible points in ?? and ?d, respectively. Thus, o(A) represents a
measure of difficulty in solving (P): the smaller a(A), the harder the problem.
3 Relation to another condition number
Let A be an m >c n matrix, and let be some pnorm. Let D be the set of all positive
definite n X n diagonal matrices. Let
5 = E R?: Ilsil = 1 and s = ATY for some y E R?J.
Let
Define
X =			e			: ADx = 0 for some D E VJ.
po(A) = inftlls --Hxli: x E X,s E S?.			(5)
Theorem 1 (Stewart [6]) For any nonzero matrix A, p0(A) > 0.
We now define x(A) = 1/po(A). In the case that A is full rank, there is an alternative
definition:
Theorem 2 (Stewart [6], O'Leary [4]) Let A be an m X n matrix of rank n. Then
= suptiiAT(ADAT)?lADii : D e DJ.			(6)
3
This quantity has been independently analyzed by Todd [7].
Suppose ZA is a basis for the nulispace of A, that, is AZA = 0 and any x such that
Ax = 0 can be written as x = Z?q. Then one checks that 1/x(ZAT) is precisely equal to the
infimum of the distance between
and
= fs ? : s = DATw for some w E R?, D E DJ,
= ?x E ?? : Ax = 0 and lixil = 1J.
Notice that this fact means that x?(ZAT) does not depend on which nulispace basis is chosen.
In this section, we explore the relation between a(A) and x?(A). More specifically, we
show
x(A)+1			(7)
Therefore, to solve problem (P) we need at most O(?(log x(A) + log n)) interior-point
algorithm iterations.
We first have the following lemma.
Leinma 1 Let A be an m x n nonzero matrix, and suppose the columns of A are partitioned
arbitrarily as [B, N]. Then
1. x(A) > 1;
2. Assuming A has rank m, ix?(A) --H x(ZAT)i < 1;
3, k(ZBT) < k(ZAT), where ZB, ZA are nulispace bases for the nulispaces of B, A respec-
tively.
PROOF. The first two inequalities are proved in Vavasis [9]. We now prove the third one.
Let the size of B be m x p. For simplicity, assume B is composed of the initial p columns
of A. Suppose u,v C are chosen so that u = DBTw for some D ? V and w E ?m, and
so that lvii = 1 and Bv = 0. We must prove that Ilu --H vii > 1/x?(ZAT). Let u' E ?? be
defined by
= DlATw
where D' = diag(D, el). Here, 1 denotes the (n --H p) >c (n --H p) identity and e > 0 is a small
parameter. Observe that
can be made arbitrarily small as we let e tend to zero. Let v' be the extension of v to
an n-vector obtained by filling in zeros. Observe that liv'll = liv ii = 1. Observe also that
Av = 0. Thus, by definition,
iiu' --H v'ii > 1/x?(ZAT).
But this implies that the same inequality must hold for u and v because the last n --H p
components of u' --H v' are arbitrarily small. 1
4
We now prove several relations between a(.) and x?(.)
Theorem 3 Assume ?p has an interior feasible point. Then
> 1/x?(ZBT).
PROOF. Assume B has n1 columns. For each i e B and any 1 > 0, consider the optimization
problem
max Xj + [t ? log(x5), subject to XB E ??.
jEB
This problem has a unique solution satisfying
X?(?ei --H BTy --H eA) =
where XB is diag(x?), e? is the ith unit vector. Thus, upon taking the inner product with
and
--HA = fl1? + Xj
xB?xBBTy= _____			1
X?ei,
n1?+x?			n1jt+x?
where y = y/(n1? + xi). Note that as 0, Xj approaches the maximizer X*j of
max Xj? subject to XB ?
which is positive since ?? has nonempty interior. Thus, XB --H XBBTy tends to zero as 0
except for the ith entry. Choose a diagonal matrix D such that D hasit in the ith diagonal
position and l's elsewhere. Then IIxB --H DxBBTyiI H Xj as 0. Hence,
1			space
Xi>?x(zBT)			DXBBTy, is in the nu
since XB in the range of ZBT, IIxBIIl = 1, and (DXB)?1w, w =
of ZB. Thus,
> Xj > -			for each i E B,
x(ZBT)?
that is
x?(ZBT)
We have similar result for the dual
Theorem 4 Assume ?d has an interior feasible point. Then
ad >
5
PROOF. Assume N has n1 columns. For each i ? N and any it> 0, consider the optimization
problem
max 5j +`t ? log(s?), subject to (y, s) c Pd.
jEN
This problem has a unique solution satisfying
S?(?ei --HXN --HAe) = ite, sN+NTy= 0, 5B = 0 and BxB+NxN = 0
where XN, XB are Lagrange multipliers, 5N is diag(s?), and e? is the ith unit vector. Since
sNTxN = sTx = 0, we again have
--HA = fl1't + Sj
and
SNkN + SN = SNkN --H NTy =			ite +			1
fliit + Sj			fliit + Sj SN?i,
where x = --Hx/(niit + s?). Note also that as it H 0, Sj approaches the maximizer St* of
max Sj? subject to (y,s) Ei
Choose a diagonal matrix D such that DB = it' and DN has it in the ith diagonal position
and l's elsewhere. Then
D0B DN%N k?ATy HSj
as it H 0 Hence,
--H			> 1
> Sj
since Ak = 0 and 5 = ATy with Ilsili = 1. This implies
ad --H
Finally, for any A, we have
Theorem 5
x(A)+1
PROOF. For any partition A = (B, N), we have from Lemma 1 and Theorem 3
>1>1>			1
a?			x(ZBT) --H x?(ZAT) --H 1+x?(A)
where ZB is the null space basis for B. Moreover, from Theorem 4 we have
Therefore, we have desired result for a(A) = min(a?, a?). I
6
4 A bound on x?(A) for polyhedra with rational data
Finally, if A is rational, we provide a bound for x(A) in terms of size of A. A similar result
is due to Tuncel [8].
Theorem 6 Let A be rational and L be its bit size. Then
< 20(L)
PROOF. Consider the least squares problem
n??n IID(ATy --H c)tI.
For all D e D, its minimizer
= (AD2AT)?lAD2c,
and y is in a bounded polyhedron of the form
P(D) = [y: ATY <?, =, or >
where the actual relation for each inequality depends on D (Todd [7]). Thus, y can be
written as a convex combination from m + 1 vertices of P(D), i.e,
m+1
y= Z?(BT)?1ci, Sai=l, Q>O, i--Hi ,m+1.
t=1
where Bi is a basis of A and Cj is the subvector of c corresponding Bi. Thus, II(BT.)?1 <20(L)
for i = 1,...,m+1,and
Therefore,
Ilyll =
m+i
II Z ai(BtT)?iciII
i=i
m+i
? ?iII(BT)?1ciII
i=i
m+i
Z QII(BT)?1II Ilcill
m+1
? ?iII(BT)?1 II lid
i=i
m+1
? ai2O(L)11c11
i=i
20(L)11c11.
IIAT(AD2AT)?iAD2cII = ?ATy?j = IlATIl . Ilyll < 20(L)IIcII,
7
which implies the theorem.
5 Remarks
We have shown that the complexity of finding an interior point for a homogeneous polyhedron
is bounded by k(A). As mentioned in the introduction, this result can be generalized to
nonhomogenous polyhedra. The difficulty with this generalization is that appending b as
a column of A could increase the value of x?(A). This increase is particularly undesirable
for problems like flow problems, in which the constraints have the form Ax = b with small
integers entries for A but arbitrary real numbers in the right-hand side vector. It is not
hard to construct nonhomogeneous problems with near-degeneracies that make a? and ad
arbitrarily small, independent of A.
A different approach to nonhomogeneous problems is to apply a new kind of interior
point method insensitive to such near-degeneracies. This is the subject of a longer paper
[10] by the authors.
References
[1] N. Karmarkar, "A new polynomial-time algorithm for linear programming," Combina-
torica 4(1984) 373--H395.
[2]
Z. Q. Luo and P. Tseng, "Error bounds and convergence analysis of matrix splitting
algorithms for the affine variational inequality problem," SlAM J. on Optimization 2
(1992) 43-54.
[3] 0. L. Mangasarian, "Simple computable bounds for solutions of linear complementarity
problems and linear programs," Mathematical Programming Study 15 (1985)1-12.
[4] D. P. O'Leary, "On bounds for scaled projections and pseudoinverses," Linear Algebra
and its Applications 132 (1990) 115-117.
[5] R. Polyak, "Modified barrier functions (theory and methods)," Mathematical Program-
ming 54 (1992)177-222.
[6] G. W. Stewart, "On scaled projections and pseudoinverses," Linear Algebra and its
Applications 112(1989)189-193.
[7] M. J. Todd, "A Dantzig-Wolfe-like variant of Karmarkar's interior-point linear pro-
gramming algorithm," Operations Research 38 (1990)1006-1018.
[8]
[9]
L. Tuncel. A pseudo-polynomial complexity analysis for interior-point algorithms. Tech-
nical Report CCOR 93-16, Department of Combinatorics and Optimization, University
of Waterloo (Waterloo, Ontario, Canada, 1993).
5. A. Vavasis, "Stable numerical algorithms for equilibrium systems, Technical Report
No. 1280, Computer Science Department Cornell University, (Ithaca, NY, 1992) and
SlAM J. Matr. Anal. Appl. (1993), to appear.
8
[10]
5. Vavasis and Y. Ye, "An accelerated interior point method whose running time depends
only on A," TR 93-1391, Department of Computer Science, Cornell University (Ithaca,
NY, 1993).
Y. Ye, "Toward probabilistic analysis of interior-point algorithms for linear program-
ming," Working Paper, Department of Management Science, The University of Iowa
(Iowa City, IA, 1991) and Mathematics of Operations Research (1993), to appear.
9
[11]
