Set Regularities and Feasibility Problems

Introduction

In recent years there has been a tremendous interest in first-order methods for solving variational problems. As the name suggests, these methods only use information that, in some way, encodes the gradient of a function to be minimized. Often one has in mind the following universal optimization problem for such methods

All of the (nonconvex) convergence results concerning local linear convergence that we have seen in the literature involve implicitly or explicitly assumptions on the regularity of the functions $f_{j}$ and on the relation of the functions to each other at critical points. Prominent examples of this are the assumption that the functions satisfy the Kurdyka-Łojasiewicz property Loj63; Kur98; BolDanLew06; BolDanLeyMaz10 or that certain constraint qualifications are satisfied at critical points, like interiority of the constraints and invertability of the Jacobian of the objective in directions normal to the constraints.

Our goal in this note is to identify common ideas and properties for a special case of (1) and to develop a general framework that both encapsulates all of these ideas and is robust enough to be applied in other settings. We focus our attention on the feasibility problem

which is the specialization of (1) to the case

In the setting of the feasibility problem, regularity properties of individual sets (elemental regularity – see Section 3) and of their intersections (transversality and subtransversality of collections of sets – see Section 4) come into play. Both types of regularity have long history. A typical classical elemental regularity assumption is the convexity of the sets, while the traditional assumption that sets have a point in common on their interiors provides an example of transversal regularity in the convex setting. Another classical example of the second type of regularity is the concept of transversality of smooth manifolds.

In the last decade there has been a great deal of interest in extending the classical notions of regularity to include nonconvex and nonsmooth sets, motivated to a large extent by nonsmooth and nonconvex optimization and attendant subdifferential and coderivative calculus, optimality and stationarity conditions and convergence analysis of algorithms. Examples of modern elemental regularity concepts include Clarke regularity RocWet98, prox-regularity (Poliquin, Rockafellar, and Thibault PolRocThi00), super-regularity (Lewis, Luke, and Malick LewLukMal09), $(A^{\prime},\varepsilon,\delta)$-regularity and $(\varepsilon,\delta)$-regularity (Bauschke, Luke, Phan, and Wang BauLukPhaWan13.2), relative ($A^{\prime},\varepsilon,\delta$)-subregularity (Hesse and Luke HesLuk13), relative $\sigma$-Hölder regularity (Noll and Rondepierre NolRon15). Among the numerous transversal regularity (regularity of intersections) concepts we mention Jameson properties (N) and (G) Jam72), the conical hull intersection property (CHIP) (Chui, Deutsch, and Ward ChuDeuWar90), (local, bounded) linear regularity (Bauschke and Borwein BauBor93 and Zheng and Ng ZheNg08), the strong conical hull intersection property (strong CHIP) (Deutsch, Li, and Ward DeuLiWar97), metric regularity (Li Li97), metric inequality (Ngai and Théra NgaThe01), the closed intersection property, the normal property, the weak, uniform and dual normal properties, the normal conical hull intersection property (normal CHIP) (Bakan, Deutsch, and Li BakDeuLi05), the normal qualification condition (Mordukhovich Mor06), regularity, strong regularity, or uniform regularity (Kruger Kru05; Kru06; Kru09), the linearly regular intersection (Lewis, Luke, and Malick LewLukMal09), linear coherence, alliedness (Penot Pen13), the $(A,B)$-qualification condition (Bauschke, Luke, Phan, and Wang BauLukPhaWan13.2), inherent and intrinsic transversality (Drusvyatskiy, Ioffe, and Lewis DruIofLew14; DruIofLew15), separable intersection (Noll and Rondepierre NolRon15), transversality and subtransversality (Ioffe Iof15). Some of the above concepts used under different names by different authors actually coincide.

A short survey of the recent developments in this area in the general nonsmooth and nonconvex setting with the emphasis on convergence analysis is provided in Section 2. The elemental and transversal regularity properties are further studied in Sections 3 and 4, respectively.

Section 3 introduces a general framework for elemental regularity of sets that provides a common language for the many different definitions that have appeared to date. This new framework makes the cascade of implications between the different types of regularity more transparent, namely that convexity $\implies$ prox-regularity $\implies$ super-regularity $\implies$ Clarke regularity $\implies$ $(\varepsilon,\delta)$-regularity $\implies$ $(\varepsilon,\delta)$-subregularity $\implies$ $\sigma$-Hölder regularity see Theorem 4. The last of these implications is new.

Section 4 focuses on two local regularity properties of collections of sets which we call here subtransversality and transversality. Both properties admit several representations and characterizations: metric, dual, angle, etc, and because of that or just historically are known under various names, e.g. (local) linear regularity, metric regularity, linear coherence, and metric inequality for the first property, and strong regularity, uniform regularity, alliedness, normal qualification condition for the second one. They correspond (are in a sense equivalent) to subregularity and metric regularity of set-valued mappings, respectively. At the same time, the properties are related to certain ‘good’ mutual arrangement of several objects (sets) in space, and after a discussion with experts in variational analysisWe are particulary indebted to Alex Ioffe for thoughtful and persuasive discussions., we have decided to adopt the classical ‘transversality’ terminology.

For ease of exposition, our discussion is limited to the case of just two closed subsets of Euclidean space with nonempty intersection, though most of the regularity properties discussed are easily extended to collections of more than two sets with nonempty intersection. We compare the various representations of these properties and discuss also some recently introduced ‘restricted’ regularity properties. A number of characterizations of the properties are formulated. Some characterizations are new, see Theorem 4.1(iii), Theorem LABEL:t:svm(LABEL:NewThe1i), Theorem 4.2(ii) and (vi), Theorem LABEL:t:tsr_suff(LABEL:t:tsr_suff_iv) and (LABEL:t:separable_and_hoelder). We emphasize the important dual characterization of subtransversality in Theorem LABEL:t:tsr_suff(LABEL:t:tsr_suff_iv) which expands and improves (in the setting adopted in the current article) (KruTha15, Theorem 4.1). The proof of this assertion is going to appear in the forthcoming article KruLukTha. In contrast to dual characterizations for transversality which are necessary and sufficient, this note underscores the fact that the known dual characterizations for subtransversality are sufficient. This raises the question whether necessary dual characterizations exist.

A projection is a selection from the projector. This exists for any closed set $A$ in Euclidean space, as can be deduced by the continuity and coercivity of the norm. Note that the projector is not, in general, single-valued, and indeed uniqueness of the projector defines a type of regularity of the set $A$: local uniqueness characterizes prox-regularity PolRocThi00 while in finite dimensional settings global uniqueness characterizes convexity Bun34. The inverse of the projector is well defined:

Following BauLukPhaWan13.2, we use this object to define the various normal cone mappings, which in turn lead to the subdifferential of the indicator function $\iota_{A}$. This brings the theory presented here to the edge of a much broader context of descent methods for solving (1). We will, however, focus exclusively on the feasibility problem for two sets.

In the above and throughout this paper, $x\stackrel{{\scriptstyle A}}{{\to}}\overline{x}$ means that $x\to\overline{x}$ with $x\in A$.

All these three sets are clearly cones. Unlike the first two cones, the third one can be nonconvex. It is easy to verify that $N^{\text{\rm prox}}_{A}(\overline{x})\subseteq N^{F}_{A}(\overline{x})$. Furthermore, if $A$ is closed, then

The last formula can serve as a definition of the limiting normal cone in general normed linear spaces when the original definition (5) in terms of proximal normals is not applicable. If $\overline{x}\in{\rm bd}\,A$, then ${N}_{A}({\overline{x}})\neq\{0\}$. If $A$ is a convex set, then all three cones (3)–(5) coincide and reduce to the normal cone in the sense of convex analysis:

The normal space to $A$ at ${\overline{x}}$ is defined as the orthogonal complement of $T_{A}({\overline{x}})$ and can be written as

It is in a sense a dual space object. If $A$ is a smooth manifold, then cones (3), (5) and (7) reduce to the normal space (8).

That normals to one of the sets should take into account the location of the other set was first recognized by Bauschke, Luke, Phan and Wang BauLukPhaWan13.2; BauLukPhaWan13.1 and has been used by Drusvyatskiy, Ioffe and Lewis DruIofLew14; DruIofLew15 We refer on several occasions to the preprint DruIofLew14 because some definitions and results present there and used in the current article are not included in the published version DruIofLew15., and Noll and Rondepierre NolRon15, leading to weaker “restricted” regularity conditions. The most straightforward idea is to consider only those normals to each of the sets which are directed towards the other set. Given two closed sets $A$ and $B$ and a point $\overline{x}\in{\rm bd}\,A\cap{\rm bd}\,B$, one can define (see BauLukPhaWan13.2; BauLukPhaWan13.1) the following restricted analogues of the cones (3)–(5):

$F$ is metrically subregular at ${\overline{x}}$ for ${\overline{y}}$ if there exist $\delta>0$ and $\alpha>0$ such that

If, additionally, ${\overline{x}}$ is an isolated point of $F^{-1}({\overline{y}})$, then $F$ is called strongly metrically subregular at ${\overline{x}}$ for ${\overline{y}}$.

$F$ is metrically regular at ${\overline{x}}$ for ${\overline{y}}$ if there exist $\delta>0$ and $\alpha>0$ such that

We use the notation ${\rm sr}[F](\overline{x},\overline{y})$ and ${\rm r}[F](\overline{x},\overline{y})$ to denote the supremum of all $\alpha$ such that conditions (11) and (12), respectively, hold for some $\delta>0$. Properties (i) and (ii) in Definition 1 are equivalent to conditions ${\rm sr}[F](\overline{x},\overline{y})>0$ and ${\rm r}[F](\overline{x},\overline{y})>0$, respectively, and the values ${\rm sr}[F](\overline{x},\overline{y})$ and ${\rm r}[F](\overline{x},\overline{y})$ characterize the corresponding properties quantitatively. Some authors use for that purpose the reciprocals of the above constants (cf. DonRoc09):

which are referred to as subregularity modulus and regularity modulus, respectively. One obviously has $0\leq{\rm r}[F](\overline{x},\overline{y})\leq{\rm sr}[F](\overline{x},\overline{y})$, which means that metric regularity is in general a stronger property than metric subregularity.

Both regularity properties in Definition 1 are fundamental for variational analysis (especially the second one) and have found numerous applications in optimization and other fields. Several useful characterizations of these properties and the fundamental equivalences

have been established. We refer the readers to the monographs Mor06; DonRoc09 and surveys Aze06; Iof15; Iof00; ApeDurStr13 for a comprehensive exposition of the properties. Note that metric subregularity of $F$ at $\overline{x}$ for $\overline{y}\in F(\overline{x})$ is equivalent to the local error bound property of the real-valued function $x\mapsto d({\overline{y}},F(x))$ at $\overline{x}$, while metric regularity of $F$ means that the mentioned error bound property holds uniformly with respect to $y$ in a neighborhood of $\overline{y}$.

Regularity notions and convergence results

In the definitions below, we keep the terminology coming from the original publications although the use of words obviously lacks consistency.

The following definition is a compilation of some of the main definitions of regularities of sets.

(RocWet98, Definition 6.4) $A$ is Clarke regular at ${\overline{x}}\in A$ if ${N}_{A}(\overline{x})=N^{F}_{A}(\overline{x})$.

(LewLukMal09, Definition 4.3) $A$ is super-regular at ${\overline{x}}\in A$ if for any $\varepsilon>0$, there is a $\delta>0$ such that

(PolRocThi00, Definition 1.1) $A$ is prox-regular at ${\overline{x}}\in A$ for ${\overline{v}}\in{N}_{A}({\overline{x}})$ if there exist $\varepsilon,\delta>0$ such that

If $A$ is prox-regular at ${\overline{x}}\in A$ for all $v\in{N}_{A}({\overline{x}})$, then $A$ is said to be prox-regular at ${\overline{x}}$.

Convexity, of course, implies all properties in Definition 2 globally.

2 Regularity of collections of sets

The origins of the concept of regular arrangement of sets in space can be traced back to that of transversality in differential geometry which deals of course with smooth manifolds (see, for instance, GuiPol74; Hir76).

This notion has been used in LewMal08; GuiPol74; Iof15. Under this assumption, $A\cap B$ is a smooth manifold around ${\overline{x}}$ and the following equalities hold (cf. LewMal08; GuiPol74; Iof15):

Equality (15) is only a necessary condition and is in general weaker than condition (16). When $A$ and $B$ are convex sets, it is known as the conical hull intersection property (CHIP) ChuDeuWar90 (cf. (BakDeuLi05, Definition 5.1)).

The transversality property of a collection of two smooth manifolds can be characterized quantitatively in terms of the angle between their tangent (or normal) spaces. One can use for that purpose the Friedrichs angle (cf. Deutsch Deu01).

Given two nonempty subspaces $V_{1}$ and $V_{2}$, the Friedrichs angle is a number between 0 and $\pi/2$ whose cosine is given by

The following properties provide some insight into the geometry of the intersection (cf. (BauLukPhaWan13.2, Fact 7.10), (LewMal08, Lemmas 3.2 and 3.3)):

The angle between two smooth manifolds $A$ and $B$ around a point ${\overline{x}}\in A\cap B$ is defined in (LewMal08, Definition 3.1) as the Friedrichs angle between the two tangent subspaces $T_{A}({\overline{x}})$ and $T_{B}({\overline{x}})$, or equivalently, in view of (18), the Friedrichs angle between the two normal subspaces $N_{A}({\overline{x}})$ and $N_{B}({\overline{x}})$:

Observe that, with $V_{1}=N_{A}(\overline{x})$ and $V_{2}=N_{B}(\overline{x})$, condition $V_{1}\cap V_{2}=\{0\}$ in (19) is equivalent to (16), and thus, to the transversality of $\{A,B\}$ at ${\overline{x}}$.

(ClaLedSteWol98, Page 99) The transversality condition holds at the intersection of two sets $A$ and $B$ if

(ZheNg08, Page 62) The collection of sets $\{A,B\}$ is locally linearly regular at $\overline{x}\in A\cap B$ if there exist numbers $\delta>0$ and $\alpha>0$ such that

(BauLukPhaWan13.2, Definition 6.6) The $(A,B)$-qualification condition holds at $\overline{x}$ if one of the following equivalent formulations holds:

(DruIofLew14, Definition 4.4) $A$ and $B$ are inherently transversal at $\overline{x}$ if there exist numbers $\alpha<1$ and $\delta>0$ such that

(NolRon15, Definition 1) $B$ intersects $A$ separably at $\overline{x}$ if there exist numbers $\alpha<1$ and $\delta>0$ such that

If $A$ also intersects $B$ separably at $\overline{x}$, then $\{A,B\}$ is said to intersect separately at $\overline{x}$.

(DruIofLew15, Definition 3.1) $A$ and $B$ are intrinsically transversal at $\overline{x}$ if one of the following equivalent conditions holds:

there exist numbers $\alpha>0$ and $\delta>0$ such that

there exist numbers $\alpha>0$ and $\delta>0$ such that

Using the Euclidean space geometry, each of the properties in Definition 4 can be reformulated equivalently in several different ways; see some reformulations in KruTha16 including the angle characterization of intrinsic transversality in (KruTha16, Proposition 19). Analytically, this means quantifying each of these properties. As observed in (LewMal08, Theorem 18), for two smooth manifolds the equalities (14) and (16) are actually equivalent. Properties (i) and (ii) are shown in Theorems 4.1 and 4.2 below to be equivalent to what we call in this article (Definition 6) transversality and subtransversality, respectively.

A more general Hölder-type setting of property (v) with exponent $\omega\in[0,2)$ is considered in NolRon15. Definition 4(v) corresponds to the ‘linear’ case $\omega=0$. Note also that this notion is not symmetric: $B$ may intersect $A$ separably, but $A$ need not intersect $B$ separably.

The known relationships between the properties in Definition 4 are as follows:

(iii) $\Rightarrow$ (iv) $\Rightarrow$ (v).

Property (vi) is in general independent of each of the properties (iii) and (iv).

When both sets are super-regular (Definition 2(v)) at the reference point, (iv) $\Rightarrow$ (vi).

Implications (a) and (b) follow from the description of the properties in Definition 4. The observation (c) was demonstrated in (KruTha16, Examples 23 and 24). Implication (d) was shown in (DruIofLew14, Proposition 4.5). ∎

3 Convergence results

We catalog next some of the main nonconvex convergence results making use of certain combinations of the above regularities.

For $A$ and $B$ closed with nonempty intersection and $\overline{x}\in A\cap B$, the alternating projections algorithm converges locally linearly if one of the following collection of conditions holds.

(LewMal08, Theorem 4.3) $A$ and $B$ are smooth manifolds around ${\overline{x}}$ and $\{A,B\}$ is transversal at ${\overline{x}}$.

(LewLukMal09, Theorem 5.16) $A$ is super-regular at ${\overline{x}}$ and the transversality condition (21) holds at ${\overline{x}}$.

(BauLukPhaWan13.2, Theorem 3.17) $A$ is $(B,\varepsilon,\delta)$-regular at ${\overline{x}}$ and the $(A,B)$-qualification condition holds at ${\overline{x}}$.

(HesLuk13, Theorem 3.11) $A$ and $B$ are $(\varepsilon,\delta)$-subregular relative to $A\cap B$ at ${\overline{x}}$ and $\{A,B\}$ is locally linearly regular at ${\overline{x}}$.

(DruIofLew14, Theorem 2.3) $\{A,B\}$ is intrinsically transversal at ${\overline{x}}$.

(NolRon15, Theorem 2) $A$ is -Hölder regular relative to $B$ at ${\overline{x}}$ and $\{A,B\}$ intersects separably at ${\overline{x}}$.

For $A$ and $B$ closed with nonempty intersection and $\overline{x}\in A\cap B$, the Douglas-Rachford algorithm converges locally linearly if one of the following collection of conditions holds.

(HesLuk13, Theorem 3.18) $\{A,B\}$ satisfies the transversality condition (21) at ${\overline{x}}$, the set $B$ is an affine subspace, and $A$ is $(\varepsilon,\delta)$-subregular relative to $A\cap B$ at ${\overline{x}}$.

(Pha15, Theorem 4.3) $\{A,B\}$ satisfies the transversality condition (21) at ${\overline{x}}$, and $A$ and $B$ are $(\varepsilon,\delta)$-subregular at ${\overline{x}}$.

Elemental set regularity

Elemental (sub)regularity defined next provides a unifying framework for the other notions of set regularity given in Definition 2.

$A$ is elementally regular of order $\sigma$ at ${\overline{x}}$ for $\left(a,v\right)$ with constant $\varepsilon$ if there exists a neighborhood $V$ of $v$ such that, for all $u\in{N}_{A}(a)\cap V$, $A$ is elementally subregular of order $\sigma$ relative to $B:=A$ at ${\overline{x}}$ for $\left(a,u\right)$ with constant $\varepsilon$.

$A$ is uniformly elementally regular of order $\sigma$ at ${\overline{x}}$ for $\left(a,v\right)$ if there exists a neighborhood $V$ of $v$ such that, for all $u\in{N}_{A}(a)\cap V$, $A$ is uniformly elementally subregular of order $\sigma$ relative to $B:=A$ at ${\overline{x}}$ for $\left(a,u\right)$.

If $B=\{{\overline{x}}\}$ in (i) and (ii), then the respective qualifier, “relative to” is dropped. If $\sigma=0$, then the respective qualifier, “of order” is dropped in the description of the properties. The modulus of elemental (sub)regularity is the infimum over all $\varepsilon$ for which (22) holds.

In all properties in Definition 5, ${\overline{x}}$ need not be in $B$ and $a$ need not be in $U$, although these are the main cases of interest for us. When $\sigma=0$, the properties are trivial for any constant $\varepsilon\geq 1$, so the only case of interest is elemental (sub)regularity with constant $\varepsilon<1$.

The set $A$, however, is not elementally regular at ${\overline{x}}=0$ for any $(0,v)\in\operatorname{gph}{{N}_{A}}$ because by choosing $x=tv\in A$ (where $0\neq v\in A\cap{N}_{A}(0)$, $t\downarrow 0$), we get $\left\langle v,x\right\rangle=\|v\|\|x\|>0$.

Let $A\cap B\neq\emptyset$ and suppose that there is a neighborhood $W$ of ${\overline{x}}\in A\cap B$ and a constant $\varepsilon>0$ such that for each

Then, $A$ is $\sigma$-Hölder regular relative to $B$ at ${\overline{x}}$ with constant $c=\varepsilon^{2}$ and neighborhood $W$ of ${\overline{x}}$ if and only if $A$ is elementally subregular of order $\sigma$ relative to $A\cap P^{-1}_{B}\left(a+v\right)$ at ${\overline{x}}$ for each $(a,v)\in V$ with constant $\varepsilon=\sqrt{c}$ and the respective neighborhood $U(a,v)$.

The set $A$ is Clarke regular at ${\overline{x}}\in A$ if and only if $A$ is uniformly elementally regular at ${\overline{x}}$ for all $({\overline{x}},v)$ with $v\in{N}_{A}({\overline{x}})$. Consequently, Clarke regularity implies $(\varepsilon,\delta)$-regularity.

(i). The set $A$ is $\sigma$-Hölder regular at ${\overline{x}}$ relative to $B$ with constant $c=\varepsilon^{2}$ and neighborhood $W$ if and only if

holding for each $(a,v)\in V$ and $x\in\left(A\cap P_{B}^{-1}(a+v)\right)\cap U(a,v)$. Thanks to assumption (24), this is equivalent to $A$ being elementally subregular of order $\sigma$ relative to $A\cap P_{B}^{-1}(a+v)$ at ${\overline{x}}$ for each $(a,v)\in V$ with constant $\varepsilon$ and neighborhood $U(a,v)$.

(iii). The first part is a particular case of (ii) for $B=A$. For the latter part, we suppose $A$ is $(A^{\prime},\varepsilon,\delta)$-regular at ${\overline{x}}$ and let $0\neq v\in N^{\text{\rm prox}}_{A|A^{\prime}}({\overline{x}})$. We can assume without loss of generality that ${\overline{x}}\in P_{A}(z)$ for $z:={\overline{x}}+v$ (otherwise one could rescale $v$ so that this holds). From the variational characterization of the Euclidean projector, ${\overline{x}}\in P_{A}(z)$ if and only if

(iv). The set $A$ is Clarke regular at ${\overline{x}}$ if and only if for any $v\in{N}_{A}({\overline{x}})$ and $\varepsilon>0$, there is a $\delta>0$ such that

This means that $A$ is uniformly elementally subregular relative to $A$ at ${\overline{x}}$ for all $({\overline{x}},v)\in\operatorname{gph}{{N}_{A}}$.

(v). By (LewLukMal09, Proposition 4.4), $A$ is super-regular at ${\overline{x}}$ if and only if for any $\varepsilon>0$, there is a $\delta>0$ such that

(vi). By (PolRocThi00, Proposition 1.2), $A$ is prox-regular at ${\overline{x}}\in A$ if and only if $A$ is prox-regular at ${\overline{x}}$ for . This means that there exist $\bar{\varepsilon},\bar{\delta}>0$ such that

(vii). Since we are in a finite dimensional setting, $A$ is nonempty closed and convex if and only if the projector is everywhere single-valued (Chebyshev (BauCom11, Theorem 3.14), Bun34, (Deu01, Theorem 12.7)) and

Assumption (24) seems to be a technical one. However, it is satisfied, for example, when the collection of sets $\{A,B\}$ is strongly subtransversal at ${\overline{x}}$ with constant $\alpha\geq\tfrac{1}{1+\varepsilon^{2}}$, where $\alpha$ is given below in Theorem 4.1(iii), since

As a consequence, 0-Hölder regularity and elemental subregularity as specified in Proposition 4 (i) are equivalent under the additional assumption of strong subtransversality of the collection of sets. This observation falls within our interest of investigating relationships amongst various regularity notions of individual sets and collections of sets. $\triangle$

Regularity of collections of sets

The following definition captures two of the central notions found (under various aliases and disguises) in the literature.

$\{A,B\}$ is subtransversal at ${\overline{x}}$ if there exist numbers $\alpha>0$ and $\delta>0$ such that

If, additionally, ${\overline{x}}$ is an isolated point of $A\cap B$, then $\{A,B\}$ is called strongly subtransversal at ${\overline{x}}$. The (possibly infinite) supremum of all $\alpha$ above is denoted ${\rm sr}[A,B](\overline{x})$ with the convention that the supremum of the empty set is zero.

$\{A,B\}$ is transversal at ${\overline{x}}$ if there exist numbers $\alpha>0$ and $\delta>0$ such that

Definition 6(i) was introduced recently in KruTha15 and can be viewed as a local analogue of the global uniform normal property introduced in the convex setting in (BakDeuLi05, Definition 3.1(4)) as a generalization of the property (N) of convex cones by Jameson Jam72. A particular case of the Jameson property (N) for convex cones $A$ and $B$ such that $B=-A$ and $A\cap(-A)=\{0\}$ was studied by M. Krein in the 1940s. Definition 6(ii) first appeared in Kru05 (see also Kru06; Kru09) in the normed linear space setting, where the property was referred to as simply regularity (and later as strong regularity and uniform regularity). In LewLukMal09, the property is called linearly regular intersection.

If $\overline{x}\in{\rm int}\,(A\cap B)$, then $\{A,B\}$ is trivially transversal (and consequently subregular) at ${\overline{x}}$ with any $\alpha>0$. Thus, ${\rm r}[A,B](\overline{x})={\rm sr}[A,B](\overline{x})=\infty$. $\triangle$

Note that, under the conditions of Example 4, $\{A,B\}$ does not have to be transversal at ${\overline{x}}$.

The next two results are a catalog of the main characterizations of subtransversality and transversality, respectively.

The following statements are equivalent to $\{A,B\}$ being subtransversal at ${\overline{x}}$.

There exist numbers $\delta>0$ and $\alpha>0$ such that

There exist numbers $\delta>0$ and $\alpha>0$ such that

Moreover, ${\rm sr}[A,B](\overline{x})$ is the exact upper bound of all numbers $\alpha$ such that (29) is satisfied.

There exist numbers $\delta>0$ and $\alpha>0$ such that

where ${\rm sr}^{\prime}[A,B](\overline{x})$ is the exact upper bound of all numbers $\alpha$ such that condition (30) is satisfied.

Characterization (i). This is easily checked.

Characterization (ii). This follows from (KruTha15, Theorem 3.1).

Characterization (iii). The inequality (29) implies (30), hence, thanks to characterization (ii), subregularity of $\{A,B\}$ implies property (30) with the same numbers $\alpha>0$ and $\delta>0$, and the second inequality in (31) holds true.

and consequently, after passing to the limit as $\alpha^{\prime}\to\alpha/(\alpha+2)$,

Hence, thanks to characterization (ii), property (30) implies subtransversality of $\{A,B\}$ with numbers $\alpha/(\alpha+2)$ and $\delta/3$. Because $\alpha$ can be chosen arbitrarily close to ${\rm sr}^{\prime}[A,B](\overline{x})$, the first inequality in (31) holds true. This completes the proof. ∎

Thanks to characterization (ii) of Theorem 4.1, subtransversality of a collection of sets can be recognized as a well known regularity property that has been around for more than 20 years under the names of (local) linear regularity, metric regularity, linear coherence, metric inequality, and subtransversality; cf. BakDeuLi05; BauBor93; BauBor96; Iof89; Iof00; Iof15; KlaLi99; HesLuk13; LiNgPon07; NgaThe01; Pen13; ZheNg08; ZheWeiYao10; DruIofLew15; Pan15. It has been used as the key assumption when establishing linear convergence of sequences generated by cyclic projection algorithms and a qualification condition for subdifferential and normal cone calculus formulae. This property is implied by the bounded linearly regularity BauBor96. If $A$ and $B$ are closed convex sets and the collection $\{A,B\}$ is subtransversal at any point in $A\cap B$, then it is boundedly linear regular; cf. (BakDeuLi05, Remark 6.1(d)). Characterization (iii) of Theorem 4.1 can be considered as a nonconvex extension of (NgYan04, Theorem 3.1).

One can also observe that condition (29) is equivalent to the function $x\mapsto\max\{d(x,A),d(x,B)\}$ having a local error bound Aze03; FabHenKruOut10; Kru15/weak sharp minimum BurDen02; BurDen05; BurFer93 at $\overline{x}$ with constant $\alpha$. One can think of condition (32) as a kind of uniform local error bound/relaxed weak sharp minimum property; cf. Kru06.

The following statements are equivalent to $\{A,B\}$ being transversal at ${\overline{x}}$.

There exist numbers $\delta>0$ and $\alpha>0$ such that

Moreover, ${\rm r}[A,B](\overline{x})$ is the exact upper bound of all numbers $\alpha$ such that (32) is satisfied.

There exist numbers $\delta>0$ and $\alpha>0$ such that

where ${\rm r}^{\prime}[A,B](\overline{x})$ is the exact upper bound of all numbers $\alpha$ such that condition (33) is satisfied.

There exists a number $\alpha>0$ such that $\|v_{1}+v_{2}\|>\alpha$ for all $v_{1}\in{N}_{A}(a)$ and $v_{2}\in{N}_{B}(b)$ with $\|v_{1}\|+\|v_{2}\|=1$. Moreover, ${\rm r}[A,B](\overline{x})$ is the exact upper bound of all such numbers $\alpha$.

${N}_{A}({\overline{x}})\cap(-{N}_{B}({\overline{x}}))=\{0\}$.

There is a number $\alpha<1$ such that $-\left\langle v_{1},v_{2}\right\rangle<\alpha$ for all $v_{1}\in{N}_{A}(\overline{x})$ and $v_{2}\in{N}_{B}(\overline{x})$ with $\|v_{1}\|=\|v_{2}\|=1$. Moreover, the exact lower bound of all such numbers $\alpha$, denoted ${\rm r}_{a}[A,B](\overline{x})$, satisfies ${\rm r}_{a}[A,B](\overline{x})+2({\rm r}[A,B](\overline{x}))^{2}=1$.