On Weighted Linear Least-Squares Problems Related to Interior Methods for Convex Quadratic Programming.
It is known that the norm of the solution to a weighted linear least-squares problem is uniformly bounded for the set of diagonally dominant symmetric positive definite weight matrices. This result is extended to weight matrices that are nonnegative linear combinations of symmetric positive semidefinite matrices. Further, results are given concerning the strong connection between the boundedness of weighted projection onto a subspace and the projection onto its complementary subspace using the inverse weight matrix. In particular, explicit bounds are given for the Euclidean norm of the projections. These results are applied to the Newton equations arising in a primal-dual interior method for convex quadratic programming and boundedness is shown for the corresponding projection operator.
Introduction
. In this paper we study certain properties of the weighted linear
least-squares problem
where A is an m n matrix of full row rank and W is a positive denite symmetric
whose matrix square root is denoted by W 1=2 . (See, e.g., Golub and
Loan [14, p. 149] for a discussion on matrix square roots.) Linear least-squares
problems are fundamental within linear algebra, see, e.g., Lawson and Hanson [20],
Golub and Van Loan [14, Chapter 5] and Gill et al. [12, Chapter 6]. An individual
problem of the form (1.1) can be converted to an unweighted problem by substituting
e
g. However, our interest is in sequences of weighted
problems, where the weight matrix W changes and A is constant. The present paper
is a continuation of the paper by Forsgren [10], in which W is assumed to be diagonally
dominant. Our concern is when the weight matrix is of the form
where H is a constant positive semidenite symmetric matrix and D is an arbitrary
positive denite diagonal matrix. Such matrices arise in interior methods for convex
quadratic programming. See Section 1.1 below for a brief motivation.
The solution of (1.1) is given by the normal equations
To appear in SIAM Journal on Matrix Analysis and Applications.
y Optimization and Systems Theory, Department of Mathematics, Royal Institute of Technology,
44 Stockholm, Sweden (anders.forsgren@math.kth.se). Research supported by the Swedish
Natural Science Research Council (NFR).
z Optimization and Systems Theory, Department of Mathematics, Royal Institute of Technology,
44 Stockholm, Sweden (goran.sporre@math.kth.se). Research supported by the Swedish
Natural Science Research Council (NFR).
A. FORSGREN AND G. SPORRE
or alternatively as the solution to the augmented system (or KKT system)

r

In some situations, we will prefer the KKT form (1.4), since we
are interested in the case when M is a positive semidenite symmetric and singular
matrix. In this situation, W 1 and (1.3) are not dened, but (1.4) is well dened.
This would for example be the case in an equality-constrained weighted linear least-squares
problem, see, e.g., Lawson and Hanson [20, Chapter 22]. For convenience, we
will mainly use the form (1.3).
mathematically, (1.3) and (1.4) are equivalent. From a computational
point of view, this need not be the case. There is a large number of papers
giving reasons for solving systems of one type or the other, starting with Bartels et
al. [1], followed by, e.g., Du et al. [9], Bjorck [4], Gulliksson and Wedin [17],
Wright [29, 31], Bjorck and Paige [5], Vavasis [26], Forsgren et al. [11], and Gill et al.
[13]. The focus of the present paper is linear algebra, and we will not discuss these
important computational aspects.
If A has full row rank and if W+ is dened as the set of n  n positive denite
symmetric matrices, then for any W 2 W+ , the unique solution of (1.1) is given by
In a number of applications, it is of interest to know if the solution remains in a
compact set as the weight matrix changes, i.e., the question is whether
sup
remains bounded for a particular subset W of W+ . It should be noted that boundedness
does not hold for an arbitrary subset W of W+ . Take for example
let
for  > 0. Then W
This implies that k(AWA T ) 1 AWk is not bounded when W is allowed to vary in
W+ . See Stewart [24] for another example of unboundedness and related discussion.
For the case where W is the set of positive denite diagonal matrices, Dikin [8] gives
an explicit formula for the optimal  in (1.1) as a convex combination of the basic
solutions formed by satisfying m linearly independent equations. From this result, the
boundedness is obvious. If A does not have full row rank, it is still possible to show
boundedness, see Ben-Israel [2, p. 108]. Later, Wei [28] has also studied boundedness
in absence of a full row rank assumption on A, and has furthermore given some
stability results. Bobrovnikova and Vavasis [6] have given boundedness results for
complex diagonal weight matrices. The geometry of the set (AWA T
varies over the set of positive denite diagonal matrices has been studied by Hanke
LEAST-SQUARES PROBLEMS RELATED TO QUADRATIC PROGRAMMING 3
and Neumann [18]. Based on the formula derived by Dikin [8], Forsgren [10] has
given boundedness results when W is the set of positive denite diagonally dominant
matrices.
We show boundedness for the set of weight matrices that are arbitrary nonnegative
combinations of a set of xed positive semidenite symmetric matrices, and the set of
inverses of such matrices. As a special case, we then obtain the set of weight matrices
of the form (1.2), which was our original interest. The boundedness is shown in the
following way. In Section 2, we review results for the characterization of  as W
varies over the set of symmetric matrices such that AWA T is nonsingular. Section 3
establishes the boundedness when W is allowed to vary over a set of matrices that are
nonnegative linear combinations of a number of xed positive semidenite matrices
such that AWA T is positive denite. In Section 4, results that are needed to handle
the projection using the inverse weight matrix are given. In Section 5, we combine
results from the previous two sections to show boundedness for the  that solves (1.4)
when M is allowed to vary over the nonnegative linear combinations of a set of xed
positive semidenite symmetric matrices.
The research was initiated by a paper by Gonzaga and Lara [15]. The link to
that paper has subsequently been superseded, but we include a discussion relating
our results to the result of Gonzaga and Lara in Appendix A.
1.1. Motivation. Our interest in weighted linear least-squares problems is from
interior methods for optimization, and in particular for convex quadratic program-
ming. There is a vast number of papers on interior methods, and here is only given a
brief motivation for the weighted linear least-squares problems that arise. Any convex
quadratic programming problem can be transformed to the form
minimize
subject to
x  0;
where H is a positive semidenite symmetric n n matrix and A is an m n matrix
of full row rank. For x 2 IR n ,  2 IR m and s 2 IR n such that x > 0 and s > 0, an
iteration of a primal-dual path-following interior method for solving (1.6) typically
takes a Newton step towards the solution of the equations
(1.7a)
(1.7c)
where  is a positive barrier parameter, see, e.g., Monteiro and Adler [21, page 46].
similarly below diag(s). Strict positivity of x and s is
implicitly required and typically maintained by limiting the step length. If  is set
equal to zero in (1.7) and the implicit requirements x > 0 and s > 0 are replaced
by x  0 and s  0, the optimality conditions for (1.6) are obtained. Consequently,
equations (1.7) and the implicit positivity of x and s may be viewed as a perturbation
of the optimality conditions for (1.6). In a primal-dual path-following interior method,
the perturbation is driven to zero to make the method converge to an optimal solution.
The equations (1.7) are often referred to as the primal-dual equations. Forming
the Newton equations associated with (1.7) for the corrections x, , s, and
4 A. FORSGREN AND G. SPORRE
eliminating s gives

x

If x and s are strictly feasible, i.e., x and s are strictly positive and x satises
then a comparison of (1.4) and (1.8) shows that the Newton equations (1.8) can be
associated with a weighted linear least-squares problem with a positive denite weight
matrix (H +X 1 S) 1 . A sequence of strictly feasible iterates fx k g 1
k=0 gives rise to a
sequence of weighted linear least-squares problems, where the weight matrix changes
but A is constant.
In a number of convergence proofs for linear programming, a crucial step is to
ensure boundedness of the step (x; s), see, e.g., Vavasis and Ye [27, Lemma 4]
and Wright [30, Lemmas 7.2 and A.4]. Since linear programming is the special case
of convex quadratic programming where are interested in extending this
boundedness result to convex quadratic programming. Therefore, the boundedness of
as X 1 S varies over the set of diagonal positive denite matrices is of interest. This
boundedness property of (1.9) is shown in Section 5.
1.2. Notation. When we refer to matrix norms, and make no explicit reference
to what type of norm is considered, it can be any matrix norm that is induced from
a vector norm such that k(x T holds for any vector x. To denote the ith
eigenvalue and the ith singular value, we use  i and  i respectively. For symmetric
matrices A and B of equal dimension, A  B means that A B is positive semidenite.
Similarly, A  B means that A B is positive denite.
The remainder of this section is given in Forsgren [10]. It is restated here for
completeness. For an m n matrix A of full row rank, we shall denote by J (A) the
collection of sets of column indices associated with the nonsingular mm submatrices
of A. For J 2 J (A), we denote by A J the mm nonsingular submatrix formed by
the columns of A with indices in J . Associated with J 2 J (A), for a diagonal n  n
matrix D, we denote by D J the mm diagonal matrix formed by the elements of D
that have row and column indices in J . Similarly, for a vector g of dimension n, we
denote by g J the vector of dimension m with the components of g that have indices in
J . The slightly dierent meanings of A J , D J and g J are used in order not to make the
notation more complicated than necessary. For an example clarifying the concepts,
see Forsgren [10, p. 766].
The analogous notation is used for an m  n matrix A of full row rank and an
n r matrix U of full row rank in that we associate J (AU) with the collection of sets
of column indices corresponding to nonsingular mm submatrices of AU . Associated
with J 2 J (AU), for a diagonal r r matrix D, we denote by D J the mm diagonal
matrix formed by the elements of D that have row and column indices in J . Similarly,
for a vector g of dimension r, we denote by g J the vector of dimension m with the
components of g that have indices in J . Since column indices of AU are also column
indices of U , for J 2 J (AU ), we denote by U J the n  m submatrix of full column
rank formed by the columns of U with indices in J . Note that each element of J (A)
as well as each element of J (AU) is a collection of m indices.
LEAST-SQUARES PROBLEMS RELATED TO QUADRATIC PROGRAMMING 5
2. Background. In this section, we review some fundamental results. The following
theorem, which states that the solution of diagonally weighted linear least-squares
problem can be expressed as a certain convex combination, is the basis for
our results. As far as we know, it was originally given by Dikin [8] who used it
in the convergence analysis of the interior point method for linear programming he
proposed [7]. The proof of the theorem is based on the Cauchy-Binet formula and
Cramer's rule.
Theorem 2.1 (Dikin [8]). Let A be an m n matrix of full row rank, let g be a
vector of dimension n, and let D be a positive denite diagonal n  n matrix. Then,

A T
is the collection of sets of column indices associated with nonsingular
mm submatrices of A.
Proof. See, e.g., Ben-Tal and Teboulle [3, Corollary 2.1].
Theorem 2.1 implies that if the weight matrix is diagonal and positive denite,
then the solution to the weighted least-squares problem (1.1) lies in the convex hull of
the basic solutions formed by satisfying m linearly independent equations. Hence, this
theorem provides an expression on the supremum of k(ADA T diagonal
and positive denite, as the following corollary shows.
Corollary 2.2. Let A be an m n matrix of full row rank, and let D+ denote
the set of positive denite diagonal n  n matrices. Then,
sup
is the collection of sets of column indices associated with nonsingular
mm submatrices of A.
Proof. See, e.g., Forsgren [10, Corollary 2.2].
The boundedness has been discussed by a number of authors over the years, see,
e.g., Ben-Tal and Teboulle [3], O'Leary [22], Stewart [24], and Todd [25]. Theorem 2.1
can be generalized to the case where the weight matrix is an arbitrary symmetric, not
necessarily diagonal, matrix such that AWA T is nonsingular. The details are given
in the following theorem.
Theorem 2.3 (Forsgren [10]). Let A be an m  n matrix of full row rank and
let W be a symmetric n  n matrix such that AWA T is nonsingular. Suppose
UDU T , where D is diagonal. Then,

where J (AU) is the collection of sets of column indices associated with nonsingular
mm submatrices of AU .
Proof. See Forsgren [10, Theorem 3.1].
3. Nonnegative combinations of positive semidenite matrices. Let A
be an mn matrix of full row rank and assume that we are given an nn symmetric
weight matrix W (), which depends on a vector  2 IR t for some t. If W () can
be decomposed as W does not depend on  and D() is
diagonal, Theorem 2.3 can be applied, provided AW ()A T is nonsingular, and the
6 A. FORSGREN AND G. SPORRE
matrices (AU J
J involved do not depend on . If, in addition D()  0, then the
linear combination of Theorem 2.3 is a convex combination. Consequently, the norm
remains bounded as long as the supremum is taken over a set of values of  for which
In particular, we are interested in the case where a set
of positive semidenite and symmetric matrices, W i , t, are given and W ()
is dened as W
. The following two lemmas and associated corollary
concern the decomposition of W (). The rst lemma concerns the set of all possible
decompositions of a positive semidenite matrix W as the relation
between dierent decompositions of this type.
Lemma 3.1. Let W be a symmetric positive semidenite n  n matrix of rank r,
and let
U is nonempty and compact. Further, if
U and e
U belong to
U , then there is an r  r orthogonal matrix Q such that
UQ.
Proof. It is possible to decompose W as is an n  r matrix
of full column rank, for example using a Cholesky factorization with symmetric inter-
changes, see, e.g., Golub and Van Loan [14, Section 4.2.9]. Therefore,
U is nonempty.
If U and e
U T both belong to
U , then
U
U
U
Hence, U T and e
U T have the same null space, which implies that the range spaces of
U and e
U are the same. Therefore, there is a nonsingular r  r matrix M such that
UM , from which it follows that e
U T . Premultiplying this equation
by e
U T and postmultiplying it by e
U gives
e
U is nonsingular, (3.1) gives MM I . Compactness is established by
proving boundedness and closedness. Boundedness holds because kU T e
is the ith unit vector. Let fU (i) g 1
be a sequence converging
to U  , such that U (i) 2
U for all i. From the continuity of matrix multiplication, U
belongs to
U , and the closedness of
U follows.
A consequence of this lemma is that we can decompose each W i , t, as
stated in the following corollary.
Corollary 3.2. For t, let W i be an nn symmetric positive semidefinite
matrix of rank r i . Let
is a well-dened compact subset of IR nr . Furthermore, if U and e
U belong to U , then,
t, there are orthogonal r i  r i matrices Q i , such that U
Proof. The result follows by applying Lemma 3.1 to each W i .
It should be noted that U depends on the matrices W i . This dependence will be
suppressed in order not to make the notation more complicated than necessary. From
Corollary 3.2, we get a decomposition result for matrices that are nonnegative linear
combinations of symmetric positive semidenite matrices, as is stated in the following
lemma. It shows that if we are given a set of positive semidenite and symmetric
matrices, t, and W () is dened as W
then we can
decompose W () into the form W does not depend on
and D() is diagonal.
Lemma 3.3. For  2 IR t , let W
are
symmetric positive semidenite n  n matrices. Further, let U be associated with
LEAST-SQUARES PROBLEMS RELATED TO QUADRATIC PROGRAMMING 7
t, according to Corollary 3.2, and for each i, let r i denote rank(W i )
and let I i be an identity matrix of dimension r i . Then W () may be decomposed as
where U is any matrix in U and
Proof. Corollary 3.2 shows that we may write
where U is an arbitrary matrix in U and
Note that D() is positive semidenite if   0. An application of Theorem 2.3
to the decomposition of Lemma 3.3 now gives the boundedness result for nonnegative
combinations of positive semidenite matrices, as stated in the following proposition.
Proposition 3.4. Let A be an mn matrix of full row rank. For  2 IR t ,   0,
let W
are symmetric positive semidenite
nn matrices. If W () is decomposed as W according to Lemma 3.3,
then for   0 and AW ()A T  0,

Furthermore,
sup
0:
U2U
where J (AU) is the collection of sets of column indices associated with nonsingular
submatrices of AU , and U is associated with t, according to
Corollary 3.2.
Proof. If AW ()A T  0, Theorem 2.3 immediately gives

Since   0, it follows that D()  0. Consequently, det(D J ())  0 for all J 2
J (AU ). Thus, the above expression gives
sup
Since this result holds for all U 2 U , it holds when taking the inmum over U 2 U .
To show that the inmum is attained, let
for every J that is a subset of ng such that jJ m. For a xed J , f J is
continuous at every e
U such that det(A e
Further, at e
U such that A e
U J is
8 A. FORSGREN AND G. SPORRE
singular, f J is a lower semi-continuous function, see, e.g., Royden [23, p. 51]. Hence,
f J is lower semi-continuous everywhere. Due to the construction of f J (U ),
J:jJj=m
The maximum of a nite collection of lower semi-continuous functions is lower semi-
continuous, see, e.g., Royden [23, p. 51], and the set U is compact by Corollary 3.2.
Therefore, the inmum is attained, see, e.g., Royden [23, p. 195], and the proof is
complete.
Note that Proposition 3.4 as special cases includes two known cases: (i) the
diagonal matrices, where W
and (ii) the diagonally dominant
matrices, where
In both these cases, the supremum bound of (3.2) is sharp. This is because all the
matrices whose nonnegative linear combinations form the weight matrices are of rank
one. In that case, the minimum over U in (3.2) is not necessary since it follows from
Corollary 3.2 that the columns of U are unique up to multiplication by 1. Hence,
D() may be adjusted so as to give weight one to the submatrix AU J for which the
maximum of the right hand side of (3.2) is achieved, and negligible weight to the other
submatrices. In general, when not all matrices whose nonnegative linear combinations
form the weight matrix have rank one, it is an open question if the supremum bound
is sharp.
4. Inversion of the weight matrix. For a constant positive semidenite matrix
H , our goal is to obtain a bound on k(A(H
D is an arbitrary positive denite diagonal matrix. One major obstacle in applying
Theorem 2.3 is the inverse in the weight matrix (H +D) 1 . The following proposition
and its subsequent corollary and lemma provide a solution to this problem.
Proposition 4.1. Suppose that an n  n orthogonal matrix Q is partitioned as
is an n  s matrix, and 2s  n. Further, let W be a symmetric
nonsingular n  n matrix such that Z T W 1 Z and Y T WY are nonsingular. Then
and
s:
Proof. The orthogonality of Q ensures that Y T I . This
gives
and hence
LEAST-SQUARES PROBLEMS RELATED TO QUADRATIC PROGRAMMING 9
proving the rst part of the proposition.
are nonsingular, we may write
(Z
I (Z T W 1
(4.2a)
(4.2b)
The orthogonality of Q ensures that
s:
We also have
I (Z T W 1
(Z
combination of (4.2a), (4.3) and (4.4) gives
s:
An analogous argument applied to (4.2b), taking into account that 2s  n gives
(4.6a)
s:
(4.6b)
The second part of the proposition follows by a combination of (4.1), (4.5) and (4.6).
In particular, Proposition 4.1 gives the equivalence between the Euclidean norms
of a projection and the projection onto the complementary space using the inverse
weight matrix, given that the matrices used to represent the spaces are orthogonal.
This is shown in the following corollary.
Corollary 4.2. Suppose that an n  n orthogonal matrix Q is partitioned as
is an nm matrix. Further, let W be a symmetric nonsingular
matrix such that Z T W 1 Z and Y T WY are nonsingular. Then
Further, let W+ denote the set of n  n positive denite symmetric matrices, and let
W  W+ . Then,
sup
k(Z
Proof. If m  n=2, the rst statement follows by letting Proposition 4.1.
The second statement is a direct consequence of the rst one. If m < n=2, we may
similarly apply Proposition 4.1 after interchanging the roles of Y and Z, and W and
As noted above, Corollary 4.2 states the equality between the Euclidean norms of
two projections, given that the matrices describing the spaces onto which we project
are orthogonal. The following lemma relates the Euclidean norms of the projections
when the matrices are not orthogonal.
A. FORSGREN AND G. SPORRE
Lemma 4.3. Let A be an m  n matrix of full row rank, and let N be a matrix
whose columns form a basis for the null space of A. Further, let W be a symmetric
nonsingular n  n matrix such that N T W 1 N and A T WA are nonsingular. Then
k(N
Proof. Let be an orthogonal matrix such that the columns of Z form
a basis for the null space of A. Then, there are nonsingular matrices RZ and R Y such
that a matrix norm which is induced from a vector
norm is submultiplicative, see, e.g., Horn and Johnson [19, Thm. 5.6.2], this giveskRZ k
k(N
k(Z
Z k;
Y k:
(4.7b)
If the Euclidean norm is used, the bounds in (4.7) can be expressed in terms of singular
values of A and N since Y and Z are orthogonal matrices, i.e.
(4.8a)
(4.8b)
A combination of Corollary 4.2, (4.7), and (4.8) gives the stated result.
If the weight matrix is allowed to vary over some subset of the positive denite
symmetric matrices, it follows from Lemma 4.3 that the norm of the projection onto
a subspace is bounded if and only if the norm of the projection onto the orthogonal
complement is bounded when using inverses of the weight matrices. This is made
precise in the following corollary.
Corollary 4.4. Let W+ denote the set of n  n positive denite symmetric
matrices, and let W  W+ . Let A be an m n matrix of full row rank and let N be
a matrix whose columns form a basis for the null space of A. Then
sup
only if sup
k(N
In particular,
sup
k(N
sup
sup
k(N
Proof. The second statement follows by multiplying the inequalities in Lemma 4.3
by k(N and then taking the supremum of the three expressions.
The rst statement of the corollary then follows from the equivalence of matrix norms
that are induced from vector norms, see, e.g., Horn and Johnson [19, Thm. 5.6.18].
5. Inversion and nonnegative combination. Let A be an m  n matrix of
full row rank, and let Z be a matrix whose columns form an orthonormal basis for
the null space of A. Further, let
are
LEAST-SQUARES PROBLEMS RELATED TO QUADRATIC PROGRAMMING 11
given symmetric positive semidenite n  n matrices. In Section 3 the weight matrix
was assumed to be the nonnegative combination of symmetric positive semidenite
matrices. This section concerns weight matrices that are the inverse of such combi-
nations, i.e., where the weight matrix is the inverse of M(). Further, if the problem
is originally posed as the KKT-system, cf. (1.4),


it makes sense to study the problem under the assumption that Z T M()Z  0, since
in our situation, Z T M()Z  0 if and only if the matrix of (5.1) is nonsingular,
see Gould [16, Lemma 3.4]. Note that Z T M()Z  0 is a weaker assumption than
M()  0, which is necessary if the least-squares formulation is to be valid. A
combination of Proposition 3.4 and Lemma 4.3 shows that () remains bounded
under the abovementioned assumptions. This is stated in the following theorem,
which is the main result of this paper.
Theorem 5.1. Let A be an m  n matrix of full row rank and let g be an n-
vector. Further, let Z be a matrix whose columns form an orthonormal basis for the
null space of A. For  2 IR t ,   0, let
are symmetric positive semidenite nn matrices. Further, let r() and () satisfy


Then,
sup
0:
In particular, if Z T M()Z  0, then
Finally, if M() is decomposed according to Lemma 3.3, then
sup
0:
where J (Z T U) is the collection of sets of column indices associated with nonsingular
submatrices of Z T U , and U is associated with M i , t, according to
Corollary 3.2.
Proof. For I  0. Therefore,
is well-dened. By Lemma 4.3 it follows that
(5.
A. FORSGREN AND G. SPORRE
For  such that Z T M()Z  0, the matrix in the system of equations dening ()
and r() is nonsingular, see Gould [16, Lemma 3.4]. Then, the implicit function
theorem implies that lim !0 Therefore, letting
(5.3). Taking the supremum over  such that   0 and Z T M()Z  0, and using
Proposition 3.4 gives (5.4), from which (5.2) follows upon observing that all norms on
a real nite-dimensional vector space are equivalent, see, e.g., Horn and Johnson [19,
As a consequence of Theorem 5.1, we are now able to prove the boundedness of
the projection operator for the application of primal-dual interior methods to convex
quadratic programming described in Section 1.1.
Corollary 5.2. Let H be a positive semidenite symmetric nn matrix, let A
be an m n matrix of full row rank, and let D+ denote the space of positive denite
diagonal n  n matrices. Then,
sup
Proof. If M()  0, then () of Theorem 5.1 satises
Theorem 5.1 implies that ()
is bounded. This holds for any vector g, and hence
sup
0:M()0
The stated result follows by applying (5.6) with
and letting
For convenience in notation, it has been assumed that all variables of the convex
quadratic program are subject to bounds. It can be observed that the analogous
results hold when some variables are not subject to bounds. In this situation, M of
may be partitioned as


where H is symmetric and positive semidenite and D 11 is diagonal and positive
denite. Let A be partitioned conformally with M as
. Then, (1.4)
has a unique solution as long as there is no nonzero p 2 such that A 2
Gould [16, Lemma 3.4]. Hence, under this additional assumption,
Theorem 5.1 can be applied to bound k()k as D 11 varies over the set of positive
denite diagonal matrices.
6.

Summary

. It has been shown that results concerning the boundedness of
for A of full row rank and W diagonal, or diagonally dominant, and
symmetric positive denite can be extended to a more general case where W is a
nonnegative linear combination of a set of symmetric positive semidenite matrices
such that AWA T  0. Further, boundedness has been shown for the projection
onto the null space of A using as weight matrix the inverse of a nonnegative linear
combination of a number of symmetric positive semidenite matrices. This result
LEAST-SQUARES PROBLEMS RELATED TO QUADRATIC PROGRAMMING 13
has been used to show boundedness of a projection operator arising in a primal-dual
interior method for convex quadratic programming.
The main tools for deriving these results have been the explicit formula for the
solution of a weighted linear least-squares problem given by Dikin [8], and the relation
between a projection onto a subspace with a certain weight matrix and the projection
onto the orthogonal complement using the inverse weight matrix.
An interesting question that is left open is whether the explicit bounds that are
given are sharp or not. In the case where all the matrices whose nonnegative linear
combination form the weight matrix are of rank one, the bounds are sharp. In the
general case, this is an open question. On a higher level, an interesting question
is whether the results of this paper can be utilized to give new complexity bounds
for quadratic programming, analogous to the case of linear programming, see, e.g.,
Vavasis and Ye [27, Section 9].


Appendix

A. Relationship to partitioned orthogonal matrices. In this
appendix we review a result by Gonzaga and Lara [15] concerning diagonally weighted
projections onto orthogonally complementary subspaces, and combine this result with
a result concerning singular values of submatrices of orthogonal matrices. It was in
fact these results which lead to the more general results relating weighted projection
onto a subspace and the projection onto its complementary subspace using the inverse
weight matrix, as described in Section 4.
Gonzaga and Lara [15] state that if Y is an n m orthogonal matrix and Z is a
matrix whose columns form an orthonormal basis for the null space of Y T , then
sup
where D+ is the set of positive denite diagonal nn matrices. They use a geometric
approach to prove this result. We note that Corollary 4.2, specialized to the case of
diagonal positive denite weight matrices, allows us to state the same result. Fur-
thermore, we obtain an explicit expression for the supremum by Corollary 2.2. The
following corollary summarizes this result.
Corollary A.1. Suppose that an n  n orthogonal matrix Q is partitioned as
is an n m matrix. Let D+ denote the set of diagonal positive
denite n  n matrices. Then,
sup
~
where J (Z T ) is the collection of sets of column indices associated with nonsingular
(n m)  (n m) submatrices of Z T and J (Y T ) is the collection of sets of column
indices associated with nonsingular mm submatrices of Y T .
Proof. Since D 2 D+ if and only if D 1 2 D+ , Corollary 4.2 shows that
sup
The explicit expressions for the two suprema follow from Corollary 2.2.
Hence, in our setting, we would rather state the result of Gonzaga and Lara [15]
in the equivalent form
sup
14 A. FORSGREN AND G. SPORRE
with the expressions for the suprema stated in Corollary A.1.
Note that an implication of Corollary A.1 is that if an nn orthogonal matrix Q is
partitioned as
, where Y has m columns, there is a certain relationship
between the smallest singular value of all nonsingular (n m)(n m) submatrices of
Z and the smallest singular value of all nonsingular mm submatrices of Y . This is
in fact a consequence of a more general result, namely that if Q is partitioned further
as

where Z 1 is (n m)  (n m), then all singular values of Z 1 and Y 2 that are less
than one are identical. This in turn is a consequence of properties of singular values
of submatrices of orthogonal matrices that can be obtained by the CS-decomposition
of an orthogonal matrix, see, e.g., Golub and Van Loan [14, Section 2.6.4].
This result relating the singular values of Z 1 and Y 2 of (A.1) implies the existence
of J and ~
J , that are complementary subsets of which the maxima in
Corollary A.1 are achieved. This observation lead us to the result that
for any positive denite diagonal D. Subsequently, this result was superseded by the
more general analysis presented in Section 4.

Acknowledgement

. We thank the two anonymous referees for their constructive
and insightful comments, which signicantly improved the presentation.



--R

Numerical techniques in mathematical programming
A Volume
A geometric property of the least squares solution of linear equations


A norm bound for projections with complex weights
Iterative solution of problems of linear and quadratic programming

The factorization of sparse symmetric inde
On linear least-squares problems with diagonally dominant weight matrices
Stability of symmetric ill-conditioned systems arising in interior methods for constrained optimization
Numerical Linear Algebra and Optimization
On the stability of the Cholesky factorization for symmetric quasi-de nite systems
Matrix Computations
A note on properties of condition numbers
On practical conditions for the existence and uniqueness of solutions to the general equality quadratic programming problem

The geometry of the set of scaled projections
Matrix Analysis

Interior path-following primal-dual algorithms
On bounds for scaled projections and pseudoinverses
Real Analysis
On scaled projections and pseudoinverses
A Dantzig-Wolfe-like variant of Karmarkar's interior-point linear programming algorithm
Stable numerical algorithms for equilibrium systems
A primal-dual interior point method whose running time depends only on the constraint matrix
Upper bound and stability of scaled pseudoinverses
Stability of linear equations solvers in interior-point methods


--TR
quadra- tic programming;weighted least-squares problem;interior method;unconstrained linear least-squares problem