Linearly perturbed generalized polyhedral normal cone mappings and applications

Under a mild regularity assumption, we derive an exact formula for the Fréchet coderivative and some estimates for the Mordukhovich coderivative of the normal cone mappings of perturbed generalized polyhedra in reflexive Banach spaces. Assume in addition that the generating elements are linearly independent and some qualification condition holds, the Lipschitzian stability of the parameterized variational inequalities over the right-hand side perturbed generalized polyhedra is characterized using the initial data.     

Stability of generalized equations under nonlinear perturbations

This paper studies solution stability of generalized equations over polyhedral convex sets. An exact formula for computing the Mordukhovich coderivative of normal cone operators to nonlinearly perturbed polyhedral convex sets is established based on a chain rule for the partial second-order subdifferential. This formula leads to a sufficient condition for the local Lipschitz-like property of the solution maps of the generalized equations under nonlinear perturbations.     

Linearly perturbed polyhedral normal cone mappings and applications

Under a mild regularity assumption, we derive an exact formula for the Fréchet coderivative and some estimates for the Mordukhovich coderivative of the normal cone mappings of perturbed polyhedra in reflexive Banach spaces. Our focus point is a positive linear independence condition, which is a relaxed form of the linear independence condition employed recently by Henrion et al. (2010) [1], and Nam (2010) [3]. The formulae obtained allow us to get new results on solution stability of affine variational inequalities under linear perturbations. Thus, our paper develops some aspects of the work of Henrion et al. (2010) [1] Nam (2010) [3] Qui (in press) [12] and Yao and Yen (2009) [6] and [7].     

New results on linearly perturbed polyhedral normal cone mappings

This paper establishes an exact formula for the Fréchet coderivative and some estimates for the Mordukhovich coderivative of the linearly perturbed normal cone mappings in reflexive Banach spaces. In comparison with Nam (2010) [5], Qui (in press) [8], Qui (2011) [7], Trang (2010) [9], the major advantage of our investigation is that here neither the linear independence condition nor the positively linear independence condition are used. Thus, no assumption on the normal vectors of the active constraints at the point in question is needed. Some aspects of the preceding results (Henrion, Mordukhovich and Nam (2010) [3], Nam (2009) [5], Qui (2011) [7], Yao and Yen (2009) [10], Yao and Yen (2009) [11]) are developed.     

Nonconvex differential calculus for infinite-dimensional multifunctions

The paper is concerned with generalized differentiation of set-valued mappings between Banach spaces. Our basic object is the so-called coderivative of multifunctions that was introduced earlier by the first author and has had a number of useful applications to nonlinear analysis, optimization, and control. This coderivative is a nonconvex-valued mapping which is related to sequential limits of Fréchet-like graphical normals but is not dual to any tangentially generated derivative of multifunctions. Using a variational approach, we develop a full calculus for the coderivative in the framework of Asplund spaces. The latter class is sufficiently broad and convenient for many important applications. Some useful calculus results are also obtained in general Banach spaces.This research was partially supported by the National Science Foundation under grants DMS-9206989 and DMS-9404128, by the USA-Israel grant 94-00237, and by the NATO contract CRG-950360.     

Quantitative stability of linear infinite inequality systems under block perturbations with applications to convex systems

The original motivation for this paper was to provide an efficient quantitative analysis of convex infinite (or semi-infinite) inequality systems whose decision variables run over general infinite-dimensional (resp. finite-dimensional) Banach spaces and that are indexed by an arbitrary fixed set J. Parameter perturbations on the right-hand side of the inequalities are required to be merely bounded, and thus the natural parameter space is l _??(J). Our basic strategy consists of linearizing the parameterized convex system via splitting convex inequalities into linear ones by using the Fenchel?CLegendre conjugate. This approach yields that arbitrary bounded right-hand side perturbations of the convex system turn on constant-by-blocks perturbations in the linearized system. Based on advanced variational analysis, we derive a precise formula for computing the exact Lipschitzian bound of the feasible solution map of block-perturbed linear systems, which involves only the system??s data, and then show that this exact bound agrees with the coderivative norm of the aforementioned mapping. In this way we extend to the convex setting the results of Cánovas et?al. (SIAM J. Optim. 20, 1504?C1526, 2009) developed for arbitrary perturbations with no block structure in the linear framework under the boundedness assumption on the system??s coefficients. The latter boundedness assumption is removed in this paper when the decision space is reflexive. The last section provides the aimed application to the convex case.     

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.     

Approximate subgradients and coderivatives in R n

We show that in two dimensions or higher, the Mordukhovich-Ioffe approximate subdifferential and Clarke subdifferential may differ almost everywhere for real-valued Lipschitz functions. Uncountably many Fréchet differentiable vector-valued Lipschitz functions differing by more than constants can share the same Mordukhovich-Ioffe coderivatives. Moreover, the approximate Jacobian associated with the Mordukhovich-Ioffe coderivative can be nonconvex almost everywhere for Fréchet differentiable vector-valued Lipschitz functions. Finally we show that for vector-valued Lipschitz functions the approximate Jacobian associated with the Mordukhovich-Ioffe coderivative can be almost everywhere disconnected.     

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.     

Lipschitzian stability of parametric variational inequalities over generalized polyhedra in Banach spaces

This paper concerns the study of solution maps to parameterized variational inequalities over generalized polyhedra in reflexive Banach spaces. It has been recognized that generalized polyhedral sets are significantly different from the usual convex polyhedra in infinite dimensions and play an important role in various applications to optimization, particularly to generalized linear programming. Our main goal is to fully characterize robust Lipschitzian stability of the aforementioned solution maps entirely via their initial data. This is done on the basis of the coderivative criterion in variational analysis via efficient calculations of the coderivative and related objects for the systems under consideration. The case of generalized polyhedra is essentially more involved in comparison with usual convex polyhedral sets and requires developing elaborated techniques and new proofs of variational analysis.     

Approximate subgradients and coderivatives in Rn

We show that in two dimensions or higher, the Mordukhovich-Ioffe approximate subdifferential and Clarke subdifferential may differ almost everywhere for real-valued Lipschitz functions. Uncountably many Fréchet differentiable vector-valued Lipschitz functions differing by more than constants can share the same Mordukhovich-Ioffe coderivatives. Moreover, the approximate Jacobian associated with the Mordukhovich-Ioffe coderivative can be nonconvex almost everywhere for Fréchet differentiable vector-valued Lipschitz functions. Finally we show that for vector-valued Lipschitz functions the approximate Jacobian associated with the Mordukhovich-Ioffe coderivative can be almost everywhere disconnected.Research supported by NSERC and the Shrum Endowment at Simon Fraser University.     

Metric regularity of a positive order for generalized equations

This paper focuses on the metric regularity of a positive order for generalized equations. More concretely, we establish verifiable sufficient conditions for a generalized equation to achieve the metric regularity of a positive order at its a given solution. The provided conditions are expressed in terms of the Fréchet coderivative/or the Mordukhovich coderivative/or the Clarke one of the corresponding multifunction formulated the generalized equation. In addition, we show that such sufficient conditions turn out to be also necessary for the metric regularity of a positive order of the generalized equation in the case where the multifunction established the generalized equation is closed and convex.     

On Stability of M-stationary Points in MPCCs

We consider parameterized Mathematical Programs with Complementarity Constraints arising, e.g., in modeling of deregulated electricity markets. Using the standard rules of the generalized differential calculus we analyze qualitative stability of solutions to the respective M-stationarity conditions. In particular, we provide characterizations and criteria for the isolated calmness and the Aubin properties of the stationarity map. To this end, we introduce the second-order limiting coderivative of mappings and provide formulas for this notion and for the graphical derivative of the limiting coderivative in the case of the normal cone mapping to \(\mathbb {R}^{n}_{+}\) .     

Chain rules for coderivatives of multivalued mappings in Banach spaces

Our basic object in this paper is to establish calculus rules for coderivatives of multivalued mappings between Banach spaces. We consider the coderivative which is associated to some geometrical approximate subdifferential for functions.

     

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.     

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.     

On the Convergence of Coderivative of SAA Solution Mapping for a Parametric Stochastic Variational Inequality

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 variational inequality with equality and inequality constraints. The notion of integrated deviation is introduced to characterize the outer limit of a sequence of sets. It is demonstrated that, under suitable conditions, both the cosmic deviation and the integrated deviation between the coderivative of the solution mapping to SAA problem and that of the solution mapping to the parametric stochastic variational inequality 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 stochastic variational inequality 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 bilevel program.     

Necessary optimality conditions for weak sharp minima in set-valued optimization

The aim of the present paper is to get necessary optimality conditions for a general kind of sharp efficiency for set-valued mappings in infinite dimensional framework. The efficiency is taken with respect to a closed convex cone and as the basis of our conditions we use the Mordukhovich generalized differentiation. We have divided our work into two main parts concerning, on the one hand, the case of a solid ordering cone and, on the other hand, the general case without additional assumptions on the cone. In both situations, we derive some scalarization procedures in order to get the main results in terms of the Mordukhovich coderivative, but in the general case we also carryout a reduction of the sharp efficiency to the classical Pareto efficiency which, in addition with a new calculus rule for Fréchet coderivative of a difference between two maps, allows us to obtain some results in Fréchet form.     

Stability of Saddle Points Via Explicit Coderivatives of Pointwise Subdifferentials

We derive stability criteria for saddle points of a class of nonsmooth optimization problems in Hilbert spaces arising in PDE-constrained optimization, using metric regularity of infinite-dimensional set-valued mappings. A main ingredient is an explicit pointwise characterization of the regular coderivative of the subdifferential of convex integral functionals. This is applied to several stability properties for parameter identification problems for an elliptic partial differential equation with non-differentiable data fitting terms.     

Differentiability and regularity of Lipschitzian mappings

We introduce new differentiability properties of functions between Banach spaces and establish their relationships with graphical regularity of Lipschitzian single-valued and set-valued mappings. The proofs are based on advanced tools of nonsmooth variational analysis including new results on coderivative scalarization and normal cone calculus.