|
Article Excerpt
We develop a new regularity concept, unifying metric regularity, Robinson's constraint qualification, and directional regularity. We present the directional stability theorem and the related concept of directional metric regularity. On one hand, our directional stability theorem immediately implies Robinson's stability theorem [Arutyunov, A. V. 2005. Covering of nonlinear maps on cone in neighborhood of abnormal point. Math. Notes 77 447-460.] as a particular case, while on the other hand, our theorem easily implies various stability results under the directional regularity condition, widely used in sensitivity analysis. Some applications of this kind are also presented.
Key words: metric regularity; Robinson's constraint qualification; directional regularity; directional metric regularity; feasible arc; sensitivity
MSC2000 subject classification: Primary: 49K40, 49K27; secondary: 90C31
OR/MS subject classification: Primary: programming/nonlinear
History: Received June 6, 2005; revised October 7, 2005.
1. Introduction. Throughout this paper, let X be a normed linear space, let Y = [R.sup.l], and let Q be a fixed closed convex set in Y. Let F: X [right arrow] Y be a smooth mapping (our smoothness hypotheses will be specified below). Recall that the mapping F is called metrically regular with respect to Q at [bar.x] [member of] [F.sup.-1] (Q) if the estimate
dist(x, [F.sup.-1] (Q - y)) = O(dist(F(x) + y, Q))
holds for (x, y) [member of] X x Y close to ([bar.x], 0) (Bonnans and Shapiro [6, p. 65]). This notion dates from Robinson [16] (or even from the classical works (Lyusternik [12], Graves [9]); see also Dmitruk et al. [7]). For more recent developments and extensions of the metric regularity theory, see Mordukhovich [13], Mordukhovich and Shao [14], Mordukhovich and Wang [15], Ioffe [10], and references therein.
As is well known (see, e.g., Bonnans and Shapiro [6, Proposition 2.89[), metric regularity is equivalent to the so-called Robinson's constraint qualification (CQ) at [bar.x], which consists of saying that
[member of] int(F([bar.x]) + im F'([bar.x]) - Q).
The fact that Robinson's CQ implies metric regularity is a consequence of the so-called Robinson's stability theorem [17] (see also Bonnans and Shapiro [6, Theorem 2.87]). To state the latter, let [summation] be a topological space (the space of parameters), let F: [summation] x X [right arrow] Y be a mapping satisfying the appropriate continuity and smoothness requirements, and for each [sigma] [member of] [summation], set
(1) D([sigma]) = {x [member of] X | F([sigma], x) [member of] Q}.
For a given (base) parameter value [bar.[sigma]] [member of] [summation], Robinson's CQ at [bar.x] [member of] D([bar.[sigma]]) takes the form
(2) [member of] int (F([bar.[sigma]], [bar.x]) + im [differential]F/[differential]x ([bar.[sigma]], [bar.x]) - Q),
and this condition implies that the estimate
(3) dist(x, D([sigma])) = O(dist(F([sigma], x), Q))
holds for ([sigma], x) [member of] [summation] x X close to ([bar.[sigma]], [bar.x]).
Another very useful regularity concept is the so-called directional regularity at [bar.x] with respect to a given direction d [member of] [summation], which becomes relevant when [summation] is a normed linear space. This condition has the form
(4) [member of] int (F([bar.[sigma]], [bar.x] + im [differential]F/[differential]x + cone {[differential]F/[differential][sigma] ([bar.[sigma]], [bar.x])d} - Q),
and it finds numerous applications, especially in sensitivity analysis for optimization problems (Bonnans and Shapiro [6]). In the context of mathematical programming problems, directional regularity is known as Gollan's condition [8], and it was extended to the general setting in Bonnans and Cominetti [4].
In this paper, we present the directional stability theorem (with a quite simple and self-contained proof), of which Robinson's stability theorem [17] is a particular case. The significance of this result is in that it enables unification of the diverse regularity concepts playing a crucial role in modem optimization theory and variational analysis. Specifically, the results employing Robinson's CQ and those employing the directional regularity condition were previously derived separately (see, e.g., Bonnans and Shapiro [6]). For example, each new result about the existence of a feasible arc of a needed given form under the directional regularity condition required a new (and usually highly nontrivial) proof. Now, the results of this kind can be derived directly from Theorem 4.1 presented below, and without any auxiliary technical tools, e.g., from the multifunctions theory.
In addition, our directional stability theorem suggests a new form of weakened (restricted) metric regularity, which may be a meaningful concept for the cases when the usual metric regularity does not hold. We believe that this concept may find multiple applications in the future, but of course, these applications could be mainly expected in the field of nonsmooth problems.
It is important to stress that in our setting, Y is a finite-dimensional space. This is strongly related to the method of proof being used, because it relies on (completely finite-dimensional) Brouwer's fixed point theorem. On the other hand, this setting (with finite-dimensional Y but possibly infinite-dimensional X) is rich enough to cover many applications (e.g., in optimal control, not to mention mathematical programming, semidefinite programming, semi-infinite programming, etc.).
This paper is organized as follows. In [section] 2, we present some auxiliary lemmas. In [section] 3, we prove our basic stability theorem for constraint systems comprised by equality constraints and set constraints. Section 4 contains the directional stability theorem, and in [section] 5, we develop the related directional metric regularity concept. Section 6 deals with the case of directional regularity. Finally, in [section] 7, we present some applications to sensitivity analysis of optimization problems, in the cases of directionally regular constraints, Holder stable solutions, and empty sets of Lagrange multipliers.
Some comments on our (fairly standard) notation are in order. For a given normed linear space X, [X.sup.*] is its (topologically) dual space, and [B.sub.[delta]](x) = {[xi] [member of] X | [parallel][xi] - x[parallel] [less than or equal to] [delta]} is a ball centered at x [member of] X and of radius [delta] > 0. If K [subset] X is a cone, [K.sup.[??]] = {l [member of] [X.sup.*] | [less than or equal to] [for all] [xi] [member of] K} stands for its polar cone. For a given set S [subset] X, int S stands for its interior, cl S stands for its closure, span S stands for the linear space spanned by S (span S is not necessarily closed), conv S (cone S, aft S) stands for its convex (conic, affine) hull, i.e., the smallest convex set (cone, affine set) containing S, and [S.sup.[perpendicular to]] = {l [member of] [X.sup.*] | = [for all] x [member of] S} is the annihilator of S. Furthermore, if [member of] S, then ri S is the relative interior of S, i.e., its interior with respect to span S. The convex hull of a finite set will be referred to as a finitely generated set. Furthermore, dist(x, S) = [inf.sub.[xi][member of]S] [parallel][xi] - x [parallel] is the distance from x [member of] X to S, and if S is a closed convex set in a finite-dimensional X, [[pi].sub.S](x) stands for the projection of x onto S, i.e., the (uniquely defined) point [xi] [member of] S such that [parallel]x - [xi][parallel] = dist(x, S). For a given point x [member of] S, [R.sub.s](x) = cone(S - x), is the so-called radial cone to S at x,
[T.sub.S] (x) = {h [member of] X | [there exists]{[t.sub.k]} [subset] [R.sub.+]\{0} such that {[t.sub.k]} [right arrow] 0, dist(x + [t.sub.k]h, S) = o([t.sub.k])}
is the contingent cone to S at x, and [N.sub.S](x) = [([T.sub.S](x)).sup.[??]] is the normal cone to S at x (if x [not member of] S, then [N.sub.S](x) = [empty set] by definition). Recall that for a convex S, [T.sub.S] (x) = cl [R.sub.S] (x).
If Y is another normed linear space, L(X, Y) stands for the space of continuous linear operators from X to Y. For a given linear operator A: X [right arrow] Y, im A stands for its range (image space).
2. Auxiliary lemmas. The proof of our basic stability theorem employs the following lemmas. Let Z be a normed linear space.
The first lemma can be regarded as a far-reaching extension of some well-known results on the right inverse mapping, to the case when a linear operator is considered only on a given convex cone in Z rather than on the entire Z. In the case of infinite-dimensional Y, such results are closely related to the Banach open mapping theorem and its generalizations (see Arutyunov [1]). Note also that here, we establish not only the "restricted" covering property but the existence of a continuous inverse function as well.
LEMMA 2.1. Let K [subset] Z be a closed convex cone, and let [bar.A] [member of] L(Z, Y).
If [bar.y] [member of] Y satisfies the inclusion [bar.y] [member of] int [bar.A](K), then there exist [delta] > and c > such that for each A [member of] L(X, Y) close enough to [bar.A], there exists a continuous mapping [[phi].sub.A]: cone [B.sub.[delta]] ([bar.y]) [right arrow] K satisfying the following requirements:
(5) A[[phi].sub.A](y) = y, [parallel][[phi].sub.A][parallel] [less than or equal to] c [parallel]y[parallel]
[for all] y [member of] cone [B.sub.[delta]] ([bar.y]). (5)
PROOF. Let [[eta].sup.i] = [bar.y] + [epsilon][e.sup.i], i = 1, ..., l, [[eta].sup.l+1] = [bar.y] - [epsilon] [[summation].sup.l.sub.i=1] [e.sup.i], where [e.sup.1], ..., [e.sup.l] is a standard basis in Y = [R.sup.l], with [epsilon] >...
|
