On Metric Pseudo-(sub)Regularity of Multifunctions and Optimality Conditions for Degenerated Mathematical Programs

This paper is devoted to the analysis of a special kind of regularity of a multifunction which we call metric pseudo-(sub)regularity, when the multifunction is not metrically (sub)regular at a given point but is metrically (sub)regular at certain points in a neighborhood with moduli possibly tending to infinity with a certain order. By using advanced techniques of generalized differentiation we derive conditions both necessary and sufficient for this property. As a byproduct we obtain a new sufficient condition for metric subregularity. Then we apply these results to multifunctions composed by a smooth mapping and a generalized polyhedral multifunction and obtain explicit formulas for this case. Finally we show how the theory can be used to obtain necessary optimality conditions when the constraint qualification condition of metric (sub)regularity is violated.     

Metric Subregularity in Generalized Equations

In this article, we study the metric subregularity of generalized equations using a new tool of nonsmooth analysis. We obtain a sufficient condition for a generalized equation to be metrically subregular, which is not a necessary condition for metric regularity, using a subtle adjustment of the Mordukhovich coderivative. We apply these results to the study of the metric subregularity in a Cournot duopoly game.     

Lipschitz-like property of an implicit multifunction and its applications

The aim of this work is twofold. First, we use the advanced tools of modern variational analysis and generalized differentiation to study the Lipschitz-like property of an implicit multifunction. More explicitly, new sufficient conditions in terms of the Fréchet coderivative and the normal/Mordukhovich coderivative of parametric multifunctions for this implicit multifunction to have the Lipschitz-like property at a given point are established. Then we derive sufficient conditions ensuring the Lipschitz-like property of an efficient solution map in parametric vector optimization problems by employing the above implicit multifunction results.     

Stability of Implicit Multifunctions in Banach Spaces

This paper is devoted to present new sufficient conditions for both the metric regularity in the Robinson??s sense and the Lipschitz-like property in the Aubin??s sense of implicit multifunctions in general Banach spaces. The basic tools of our analysis involve the Clarke subdifferential, the Clarke coderivative of set-valued mappings, and the Ekeland variational principle. The metric regularity of implicit multifunction is compared with the Lipschitz-like property.     

Metric Regularity of the Sum of Multifunctions and Applications

The metric regularity of multifunctions plays a crucial role in modern variational analysis and optimization. This property is a key to study the stability of solutions of generalized equations. Many practical problems lead to generalized equations associated to the sum of multifunctions. This paper is devoted to study the metric regularity of the sum of multifunctions. As the sum of closed multifunctions is not necessarily closed, almost all known results in the literature on the metric regularity for one multifunction (which is assumed usually to be closed) fail to imply regularity properties of the sum of multifunctions. To avoid this difficulty, we use an approach based on the metric regularity of so-called epigraphical multifunctions and the theory of error bounds to study the metric regularity of the sum of two multifunctions, as well as some related important properties of variational systems. Firstly, we establish the metric regularity of the sum of a regular multifunction and a pseudo-Lipschitz multifunction with a suitable Lipschitz modulus. These results subsume some recent results by Durea and Strugariu. Secondly, we derive coderivative characterizations of the metric regularity of epigraphical multifunctions associated with the sum of multifunctions. Applications to the study of the behavior of solutions of variational systems are reported.     

Metric subregularity for proximal generalized equations in Hilbert spaces

In this paper, we introduce and consider the concept of the prox-regularity of a multifunction. We mainly study the metric subregularity of a generalized equation defined by a proximal closed multifunction between two Hilbert spaces. Using proximal analysis techniques, we provide sufficient and/or necessary conditions for such a generalized equation to have the metric subregularity in Hilbert spaces. We also establish the results of Robinson-Ursescu theorem type for prox-regular multifunctions.     

Covering properties at positive-order rates of multifunctions and some related topics

We obtain equivalences among the covering property at a positive-order rate of a multifunction, the metric regularity property of a positive order, and the Hölder-like continuity property of the inverse mapping. Our results develop some aspects of the preceding results of J.-P. Penot, J.M. Borwein and D.M. Zhuang, H. Frankowska, B.S. Mordukhovich, and L.I. Minchenko. Necessary conditions for having these properties are given in terms of positive-order variational coderivative, a concept used here for the first time. We also discuss some known sufficient conditions for the validity of the three properties in terms of the positive-order variation in the sense of H. Frankowska. Illustrative examples are considered.     

Point-based sufficient conditions for metric regularity of implicit multifunctions

We obtain some point-based sufficient conditions for the metric regularity in Robinson’s sense of implicit multifunctions in a finite-dimensional setting. The new implicit function theorem (which is very different from the preceding results of Ledyaev and Zhu [Yu.S. Ledyaev, Q.J. Zhu, Implicit multifunctions theorems, Set-Valued Anal. 7 (1999) 209–238], Ngai and Théra [H.V. Ngai, M. Théra, Error bounds and implicit multifunction theorem in smooth Banach spaces and applications to optimization, Set-Valued Anal. 12 (2004) 195–223], Lee, Tam and Yen [G.M. Lee, N.N. Tam, N.D. Yen, Normal coderivative for multifunctions and implicit function theorems, J. Math. Anal. Appl. 338 (2008) 11–22]) can be used for analyzing parametric constraint systems as well as parametric variational systems. Our main tools are the concept of normal coderivative due to Mordukhovich and the corresponding theory of generalized differentiation.     

Implicit Multifunction Theorems

We prove a general implicit function theorem for multifunctions with a metric estimate on the implicit multifunction and a characterization of its coderivative. Traditional open covering theorems, stability results, and sufficient conditions for a multifunction to be metrically regular or pseudo-Lipschitzian can be deduced from this implicit function theorem. We prove this implicit multifunction theorem by reducing it to an implicit function/solvability theorem for functions. This approach can also be used to prove the Robinson–Ursescu open mapping theorem. As a tool for this alternative proof of the Robinson–Ursescu theorem, we also establish a refined version of the multidirectional mean value inequality which is of independent interest.     

Coderivative calculus and metric regularity for constraint and variational systems

This paper provides new developments in generalized differentiation theory of variational analysis with their applications to metric regularity of parameterized constraint and variational systems in finite-dimensional and infinite-dimensional spaces. Our approach to the study of metric regularity for these two major classes of parametric systems is based on appropriate coderivative constructions for set-valued mappings and on extended calculus rules supporting their computation and estimation. The main attention is paid in this paper to the so-called reversed mixed coderivative, which is of crucial importance for efficient pointwise characterizations of metric regularity in the general framework of set-valued mappings between infinite-dimensional spaces. We develop new calculus results for the latter coderivative that allow us to compute it for large classes of parametric constraint and variational systems. On this basis we derive verifiable sufficient conditions, necessary conditions as well as complete characterizations for metric regularity of such systems with computing the corresponding exact bounds of metric regularity constants/moduli. This approach allows us to reveal general settings in which metric regularity fails for major classes of parametric variational systems. Furthermore, the developed coderivative calculus leads us also to establishing new formulas for computing the radius of metric regularity for constraint and variational systems, which characterize the maximal region of preserving metric regularity under linear (and other types of) perturbations and are closely related to conditioning aspects of optimization.     

Strong metric subregularity of mappings in variational analysis and optimization

Although the property of strong metric subregularity of set-valued mappings has been present in the literature under various names and with various (equivalent) definitions for more than two decades, it has attracted much less attention than its older “siblings”, the metric regularity and the strong (metric) regularity. The purpose of this paper is to show that the strong metric subregularity shares the main features of these two most popular regularity properties and is not less instrumental in applications. We show that the strong metric subregularity of a mapping F acting between metric spaces is stable under perturbations of the form $f+F$, where f is a function with a small calmness constant. This result is parallel to the Lyusternik–Graves theorem for metric regularity and to the Robinson theorem for strong regularity, where the perturbations are represented by a function f with a small Lipschitz constant. Then we study perturbation stability of the same kind for mappings acting between Banach spaces, where f is not necessarily differentiable but admits a set-valued derivative-like approximation. Strong metric q-subregularity is also considered, where q is a positive real constant appearing as exponent in the definition. Rockafellar's criterion for strong metric subregularity involving injectivity of the graphical derivative is extended to mappings acting in infinite-dimensional spaces. A sufficient condition for strong metric subregularity is established in terms of surjectivity of the Fréchet coderivative, and it is shown by a counterexample that surjectivity of the limiting coderivative is not a sufficient condition for this property, in general. Then various versions of Newton's method for solving generalized equations are considered including inexact and semismooth methods, for which superlinear convergence is shown under strong metric subregularity. As applications to optimization, a characterization of the strong metric subregularity of the KKT mapping is obtained, as well as a radius theorem for the optimality mapping of a nonlinear programming problem. Finally, an error estimate is derived for a discrete approximation in optimal control under strong metric subregularity of the mapping involved in the Pontryagin principle.     

Openness properties for parametric set-valued mappings and implicit multifunctions

The aim of this paper is to obtain some openness results in terms of normal coderivative for parametric set-valued mappings acting between infinite dimensional spaces. Then, implicit multifunction results are obtained by simply specializing the openness results. Moreover, we study a kind of metric regularity of the implicit multifunction. The results of the paper generalize several recent results in literature.     

On the Convergence of Coderivative of SAA Solution Mapping for a Parametric Stochastic Generalized Equation

The aim of this paper is to investigate the convergence properties for Mordukhovich’s coderivative of the solution map of the sample average approximation (SAA) problem for a parametric stochastic generalized equation. It is demonstrated that, under suitable conditions, both the cosmic deviation and the ρ-deviation between the coderivative of the solution mapping to SAA problem and that of the solution mapping to the parametric stochastic generalized equation converge almost surely to zero as the sample size tends to infinity. Moreover, the exponential convergence rate of coderivatives of the solution maps to the SAA parametric generalized equations is established. The results are used to develop sufficient conditions for the consistency of the Lipschitz-like property of the solution map of SAA problem and the consistency of stationary points of the SAA estimator for a stochastic mathematical program with complementarity constraints.     

Coderivative Analysis of Variational Systems

The paper mostly concerns applications of the generalized differentiation theory in variational analysis to Lipschitzian stability and metric regularity of variational systems in infinite-dimensional spaces. The main tools of our analysis involve coderivatives of set-valued mappings that turn out to be proper extensions of the adjoint derivative operator to nonsmooth and set-valued mappings. The involved coderivatives allow us to give complete dual characterizations of certain fundamental properties in variational analysis and optimization related to Lipschitzian stability and metric regularity. Based on these characterizations and extended coderivative calculus, we obtain efficient conditions for Lipschitzian stability of variational systems governed by parametric generalized equations and their specifications.     

Local convergence of quasi-Newton methods under metric regularity

We consider quasi-Newton methods for generalized equations in Banach spaces under metric regularity and give a sufficient condition for q-linear convergence. Then we show that the well-known Broyden update satisfies this sufficient condition in Hilbert spaces. We also establish various modes of q-superlinear convergence of the Broyden update under strong metric subregularity, metric regularity and strong metric regularity. In particular, we show that the Broyden update applied to a generalized equation in Hilbert spaces satisfies the Dennis–Moré condition for q-superlinear convergence. Simple numerical examples illustrate the results.     

On Metric and Calmness Qualification Conditions in Subdifferential Calculus

The paper contains two groups of results. The first are criteria for calmness/subregularity for set-valued mappings between finite-dimensional spaces. We give a new sufficient condition whose subregularity part has the same form as the coderivative criterion for “full” metric regularity but involves a different type of coderivative which is introduced in the paper. We also show that the condition is necessary for mappings with convex graphs. The second group of results deals with the basic calculus rules of nonsmooth subdifferential calculus. For each of the rules we state two qualification conditions: one in terms of calmness/subregularity of certain set-valued mappings and the other as a metric estimate (not necessarily directly associated with aforementioned calmness/subregularity property). The conditions are shown to be weaker than the standard Mordukhovich–Rockafellar subdifferential qualification condition; in particular they cover the cases of convex polyhedral set-valued mappings and, more generally, mappings with semi-linear graphs. Relative strength of the conditions is thoroughly analyzed. We also show, for each of the calculus rules, that the standard qualification conditions are equivalent to “full” metric regularity of precisely the same mappings that are involved in the subregularity version of our calmness/subregularity condition. The research of Jiří V. Outrata was supported by the grant A 107 5402 of the Grant Agency of the Academy of Sciences of the Czech Republic.     

On the Stability of the Directional Regularity

In this paper we select two tools of investigation of the classical metric regularity of set-valued mappings, namely the Ioffe criterion and the Ekeland Variational Principle, which we adapt to the study of the directional setting. In this way, we obtain in a unitary manner new necessary and/or sufficient conditions for directional metric regularity. As an application, we establish stability of this property at composition and sum of set-valued mappings. In this process, we introduce directional tangent cones and the associated generalized primal differentiation objects and concepts. Moreover, we underline several links between our main assertions by providing alternative proofs for several results.

     

Implicit multifunction theorems for the sensitivity analysis of variational conditions

We study implicit multifunctions (set-valued mappings) obtained from inclusions of the form 0∈M(p,x), whereM is a multifunction. Our basic implicit multifunction theorem provides an approximation for a generalized derivative of the implicit multifunction in terms of the derivative of the multifunctionM. Our primary focus is on three special cases of inclusions 0∈M(p,x) which represent different kinds of generalized variational inequalities, called “variational conditions”. Appropriate versions of our basic implicit multifunction theorem yield approximations for generalized derivatives of the solutions to each kind of variational condition. We characterize a well-known generalized Lipschitz property in terms of generalized derivatives, and use our implicit multifunction theorems to state sufficient conditions (and necessary in one case) for solutions of variational conditions to possess this Lipschitz, property. We apply our results to a general parameterized nonlinear programming problem, and derive a new second-order condition which guarantees that the stationary points associated with the Karush-Kuhn-Tucker conditions exhibit generalized Lipschitz continuity with respect to the parameter.     

Coderivatives in parametric optimization

We consider parametric families of constrained problems in mathematical programming and conduct a local sensitivity analysis for multivalued solution maps. Coderivatives of set-valued mappings are our basic tool to analyze the parametric sensitivity of either stationary points or stationary point-multiplier pairs associated with parameterized optimization problems. An implicit mapping theorem for coderivatives is one key to this analysis for either of these objects, and in addition, a partial coderivative rule is essential for the analysis of stationary points. We develop general results along both of these lines and apply them to study the parametric sensitivity of stationary points alone, as well as stationary point-multiplier pairs. Estimates are computed for the coderivative of the stationary point multifunction associated with a general parametric optimization model, and these estimates are refined and augmented by estimates for the coderivative of the stationary point-multiplier multifunction in the case when the constraints are representable in a special composite form. When combined with existing coderivative formulas, our estimates are entirely computable in terms of the original data of the problem. Key words.parametric optimization – variational analysis – sensitivity – Lipschitzian stability – generalized differentiation – coderivativesThis research was partly supported by the National Science Foundation under grant DMS-0072179.     

BCQ and Strong BCQ for Nonconvex Generalized Equations with Applications to Metric Subregularity

In this paper, based on basic constraint qualification (BCQ) and strong BCQ for convex generalized equation, we are inspired to further discuss constraint qualifications of BCQ and strong BCQ for nonconvex generalized equation and then establish their various characterizations. As applications, we use these constraint qualifications to study metric subregularity of nonconvex generalized equation and provide necessary and/or sufficient conditions in terms of constraint qualifications considered herein to ensure nonconvex generalized equation having metric subregularity.