|
Article Excerpt
When is the linear image of a closed convex cone closed? We present very simple and intuitive necessary conditions that (1) unify, and generalize seemingly disparate, classical sufficient conditions such as polyhedrality of the cone, and Slater-type conditions; (2) are necessary and sufficient, when the dual cone belongs to a class that we call nice cones (nice cones subsume all cones amenable to treatment by efficient optimization algorithms, for instance, polyhedral, semidefinite, and p-cones); and (3) provide similarly attractive conditions for an equivalent problem: the closedness of the sum of two closed convex cones.
Key words: closedness; linear image; closed convex cone; sum of closed convex cones; duality; common root of Slater's condition and polyhedrality
1. Introduction. One of the most fundamental questions of convex analysis is also the simplest: When is the linear image of a closed convex set closed? Essential applications include: finding out, when the sum and convolution of closed convex functions are closed; and uniform duality in conic linear systems. For the first, see, for instance, Chapter 9 in Rockafellar's classic text (Rockafellar [22]), which is entirely devoted to closedness criteria. For the application to uniform duality, see Duffin et al. [14].
We study the case when the convex set is a cone, using the following framework:
* given a linear map M between two finite dimensional spaces, and its adjoint [M.sup.*];
* a closed, convex cone K, and its dual cone [K.sup.*] = {y | (y, x) [greater than or equal to] [for all] x [member of] K},
(*) When is [M.sup.*][K.sup.*] closed?
Our main motivation is the following question: Is there a common root of the following three well-known, seemingly quite unrelated sufficient conditions?
ri K [intersection] R(M) [not equal to] [empty set], (IMG-RI)
K [intersection] R(M) = lspace(K) [intersection] R(M), (IMG-LSPACE)
K is polyhedral, (POL)
where lspace(K) stands for K [intersection] (-K), the lineality space of K.
1.1. A sample of the main results. The main result of this paper gives a yes answer in a surprisingly simple form (see the ensuing explanation for less common notation):
THEOREM 1.1 (MAIN THEOREM). Let [bar.x] [member of] ri(R(M) [intersection] K), and F the minimal face of K that contains [bar.x]. The following conditions:
(i) R(M) [intersection] dir([bar.x], K) = R(M) [intersection] cl dir([bar.x], K);
(ii) [M.sup.*][F.sup.[DELTA]] = [M.sup.*][F.sup.[perpendicular to]];
(iii) ri [F.sup.[DELTA]] [intersection] N([M.sup.*]) [not equal to] [empty set], and R(M) [intersection] [F.sup.[DELTA][perpendicular to]] = R(M) [intersection] lin F;
(iv) R(M) [intersection] [F.sup.[DELTA]*] = R(M) [intersection] lin F;
are equivalent and necessary for the closedness of [M.sup.*][K.sup.*]. If [K.sup.*] + [F.sup.[perpendicular to]] is closed, then they are necessary and sufficient.
Here, dir([bar.x], K) = {y | [bar.x] + ty [member of] K for some t > 0} is the set of feasible directions at [bar.x] in K, [F.sup.[perpendicular to]] is the orthogonal complement of the linear span of F,
[F.sup.[DELTA]] = [K.sup.*] [intersection] [F.sup.[perpendicular to]], [F.sup.[DELTA]*] = [([F.sup.[DELTA]).sup.*], [F.sup.[DELTA][perpendicular to]] = [([F.sup.[DELTA]).sup.[perpendicular to]].
It is easy to confirm why, for instance, (i) subsumes the three classical conditions:
* If (IMG-RI) holds, then [bar.x] [empty set] ri K, and dir([bar.x], K) is the linear span of K, which is a closed set.
* If (IMG-LSPACE) holds, then [bar.x] lspace(K), and dir([bar.x], K) = K, which is closed by definition.
* If (POL) holds, then dir([bar.x], K) is closed, regardless of where [bar.x] is in K.
The class of cones, for which the Main Theorem provides a necessary and sufficient condition for an arbitrary M, is, in fact, quite large.
DEFINITION 1.1. A closed convex cone C is called nice if
the set [C.sup.*] + [E.sup.[perpendicular to]] is closed for all E faces of C.
Polyhedral cones are obviously nice; later on we will show that so are the cone of positive semidefinite matrices, and p-cones. The above property of cones is first mentioned in a paper of Borwein and Wolkowicz [11], although they do not use this property to study our main problem.
REMARK 1.1. Condition (ii) has an interesting geometric interpretation. If K is nice, then it implies
[M.sup.*][K.sup.*] [subset or not equal to] cl[M.sup.*][K.sup.*] [??] [M.sup.*][F.sup.[DELTA]] [subset or not equal to] [M.sup.*][F.sup.[perpendicular to]]. (1)
Also,
[M.sup.*][F.sup.[DELTA]] [subset or equal to] [M.sup*.][K.sup.*], and [M.sup.*][F.sup.[perpendicular to]] [subset or equal to] cl [M.sup.*][K.sup.*], (2)
with the first inclusion being obvious, and the second following from (19), shown in the proof of the Main Theorem.
Thus, on the one hand, [M.sup.*][F.sup.[DELTA]] and [M.sup.*][F.sup.[perpendicular to]] act as "substitutes" for [M.sup.*][K.sup.*] and cl[M.sup.*][K.sup.*] to check their equality. On the other hand, since [M.sup.*][F.sup.[perpendicular to]] is a subspace, the last statement in (1) is equivalent to
cl [M.sup.*][F.sup.[DELTA]] [subset or equal to] [M.sup.*][F.sup.[perpendicular to]],
which is the same as
[there exists]w [member of] [M.sup.*][F.sup.[perpendicular to]] which can be strictly separated from [M.sup.*][F.sup.[DELTA]].
We show in Corollary 3.1 that any such w is also in cl [M.sup.*][K.sup.*]\[M.sup.*][K.sup.*]. However, it provides a stronger certificate of nonclosedness than an arbitrary point in cl [M.sup.*][K.sup.*]\[M.sup.*][K.sup.*]: the latter cannot be strictly separated from [M.sup.*][K.sup.*], while w can be strictly separated from the "substitute" of [M.sup.*][K.sup.*], namely [M.sup.*][F.sup.[perpendicular to]].
Our problem frequently appears in a different guise: given closed, convex cones [K.sub.1] and [K.sub.2],
([DELTA]) When is [K.sup.*.sub.1] + [K.sup.*.sub.2] closed?
A necessary and/or sufficient condition for either one of (*) and ([DELTA]) yields such a condition for the other, as explained in [section] 5.
1.2. Literature review. The first reference that we are aware of that implies the sufficiency of (IMG-RI) is Theorem 2 in Duffin [13]. (The proof in Duffin [13] works only in the case when K is full-dimensional for the general case, one needs to modify it.) The sufficiency of (POL) follows from the fact that a polyhedral cone is finitely generated, so its linear image is also polyhedral. We are not aware of a reference for condition (IMG-LSPACE), so we give a simple proof later on as part of Theorem 2.2 in [section] 2.
Conditions (IMG-RI), (IMG-LSPACE), and (POL) have their dual counterparts; they are equivalent to
[K.sup.*] [intersection] N ([M.sup.*]) = [K.sup.[perpendicular to]] [intersection] N ([M.sup.*]), (IMG-LSPACE-DUAL)
ri [K.sup.*] [intersection] N([M.sup.*]) [not equal to] [empty set], (IMG-RI-DUAL)
[K.sup.*] is polyhedral, (POL-DUAL)
respectively. The equivalence of (IMG-RI) and (IMG-LSPACE-DUAL) (and of the symmetric pair (IMG-LSPACE) and (IMG-RI-DUAL)) will be explained and proved as part of Theorem 2.2, as well.
Theorem 9.1 in Rockafellar [22] implies that for an arbitrary closed convex set C, and linear map A the following condition is sufficient for the closedness of AC:
rec(C) [intersection] N(A) = lspace(rec(C)) [intersection] N(A). (ROCK)
Here
rec(C) = {y | x + ty [member of] C, [for all] x [member of] C, [for all] t [greater than or equal to] 0}
is the recession cone of C. This conditon generalizes (IMG-LSPACE-DUAL); it does not seem to have a "primal" counterpart when C is not a cone. (Theorem 9.1. is, in fact, more general; it gives a sufficient condition for cl AC = A(cl C) to hold, even when C is not closed.)
Besides the classical results listed above, several more are available for (*) and/or ([DELTA]). We list all that are known to us:
* A sufficient condition for ([DELTA]) was given by Waksman and Epelman [25, p. 95], which for (*) translates into
[for all] y [member of] N([M.sup.*]) [intersection] [K.sup.*]: dir(y, [K.sup.*]) is closed. (WE)
* Auslender [2] gave a necessary and sufficient condition for the linear image of an arbitrary closed convex set to be closed.
* Bauschke and Borwein [7] present a necessary and sufficient condition for the continuous image of a closed convex cone to be closed in terms of the strong conical hull intersection property.
* Ramana's [19] extended dual has the following connection to our work: when K = [K.sup.*] is the cone of positive semidefinite matrices, and b a given vector, then his results imply: we can check b [not member of] [M.sup.*][K.sup.*] by verifying the feasibility of a semidefinite system, whose size is polynomial in terms of the original data.
Of these four results, the one closest to ours in spirit is the provision (WE); it is an elegant weakening of (IMG-LSPACE-DUAL) and (POL-DUAL). However, in contrast to our conditions, no interesting class of cones has been identified for which (WE) would be necessary and sufficient. For many relevant cones, such as the semidefinite and second order cones, (WE) reduces to (IMG-LSPACE-DUAL) or to a restricted version of (IMG-RI-DUAL): we show this in [section] 5. The results of Auslender and of Bauschke and Borwein are more general than ours; however, their conditions on closedness are also more involved.
The rest of the article is structured as follows. Section 2 deals with notation and surveys the necessary, mostly known results to be used later on. For better insight, we provide some proofs in [section] 2. Section 3 presents the main results on problem (*) and shows how from a "certificate" of nonclosedness of [M.sup.*][K.sup.*] one can actually produce a vector in cl [M.sup.*][K.sup.*]\[M.sup.*][K.sup.*]. Section 4 gives a variety of examples and discusses some of the complexity implications of the Main Theorem; we prove that closedness of the linear image of the semidefinite cone can be verified in polynomial time in the real number model of computing. Section 5...
|
