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.

     

A Fritz John optimality condition using the approximate subdifferential

A Fritz John type first-order optimality condition is derived for infinite-dimensional programming problems involving the approximate subdifferential. A discussion of the important properties of the approximate subdifferential for locally Lipschitz functions is included. In addition, an upper semicontinuity condition is obtained for an approximate subdifferential multifunction related to the class of locally compactly Lipschitzian mappings.The authors would like to thank two anonymous referees for their detailed comments which have significantly improved the presentation of this paper. In particular, they thank the first referee for pointing out a number of important references on the approximate subdifferential and the second referee for various corrections and for bringing an important recent reference (Ref. 17) to their attention.     

A chain rule for ?-subdifferentials with applications to approximate solutions in convex Pareto problems

In this work we obtain a chain rule for the approximate subdifferential considering a vector-valued proper convex function and its post-composition with a proper convex function of several variables nondecreasing in the sense of the Pareto order. We derive an interesting formula for the conjugate of a composition in the same framework and we prove the chain rule using this formula. To get the results, we require qualification conditions since, in the composition, the initial function is extended vector-valued. This chain rule extends analogous well-known calculus rules obtained when the functions involved are finite and it gives a complementary simple expression for other chain rules proved without assuming any qualification condition. As application we deduce the well-known calculus rule for the addition and we extend the formula for the maximum of functions. Finally, we use them and a scalarization process to obtain Kuhn-Tucker type necessary and sufficient conditions for approximate solutions in convex Pareto problems. These conditions extend other obtained in scalar optimization problems.     

Local Lipschitz-constant Functions and Maximal Subdifferentials

It is shown that if k(x) is an upper semicontinuous and quasi lower semicontinuous function on a Banach space X, then k(x)B _X* is the Clarke subdifferential of some locally Lipschitz function on X. Related results for approximate subdifferentials are also given. Moreover, on smooth Banach spaces, for every locally Lipschitz function with minimal Clarke subdifferential, one can obtain a maximal Clarke subdifferential map via its local Lipschitz-constant function. Finally, some results concerning the characterization and calculus of local Lipschitz-constant functions are developed.     

A derivative-free approximate gradient sampling algorithm for finite minimax problems

In this paper we present a derivative-free optimization algorithm for finite minimax problems. The algorithm calculates an approximate gradient for each of the active functions of the finite max function and uses these to generate an approximate subdifferential. The negative projection of 0 onto this set is used as a descent direction in an Armijo-like line search. We also present a robust version of the algorithm, which uses the ‘almost active’ functions of the finite max function in the calculation of the approximate subdifferential. Convergence results are presented for both algorithms, showing that either f(x ^k )→?∞ or every cluster point is a Clarke stationary point. Theoretical and numerical results are presented for three specific approximate gradients: the simplex gradient, the centered simplex gradient and the Gupal estimate of the gradient of the Steklov averaged function. A performance comparison is made between the regular and robust algorithms, the three approximate gradients, and a regular and robust stopping condition.     

Subdifferential characterization of approximate convexity: the lower semicontinuous case

It is known that a locally Lipschitz function is approximately convex if, and only if, its Clarke subdifferential is a submonotone operator. The main object of this work is to extend the above characterization to the class of lower semicontinuous functions. To this end, we establish a new approximate mean value inequality involving three points. We also show that an analogue of the Rockafellar maximal monotonicity theorem holds for this class of functions and we discuss the case of arbitrary subdifferentials.     

Distinct differentiable functions may share the same Clarke subdifferential at all points

We construct, using Zahorski's Theorem, two everywhere differentiable real-valued Lipschitz functions differing by more than a constant but sharing the same Clarke subdifferential and the same approximate subdifferential.

     

A generalized karush-kuhn-tucki optimality condition without constraint qualification using tl approximate subdifferential

A generalized Karush-Kuhn-Tucker first order optimality condition is established for an abstract cone-constrained programming problem involving locally Lipschitz functions using the approximate subdifferential. This result is obtained without recourse to a constraint qualification by imposing additional generalized convexity conditions on the constraint functions. A new Fritz John optimality condition is developed as a precursor to the main result. Several examples are provided to illustrate the results along with a discussion of applications to concave minimization problems and to stochastic programming problems with nonsmooth data.     

Characterizations of an approximate minimum in optimal control

By using the classical variational methods based on geodesic coverings of a domain and on Hilbert's independent integral, further characterizations of an approximate solution in problems of control are described. The starting point is the Ekeland-type characterization, the variational principle. As consequences, sufficient conditions for optimality are obtained in a form similar to the Weierstrass conditions from the calculus of variations.The author is grateful to the referee for the valuable counterexamples to the first version of the paper.     

Topological characterization of the approximate subdifferential in the finite-dimensional case

Topological properties of the approximate Subdifferential introduced by Mordukhovich are studied. Apart from formulating a sufficient condition for connectedness, it is shown that, up to homeomorphy, each compact subset of ^p may occur as the approximate subdifferential of some Lipschitz function. Furthermore, even an exact result is possible when considering the partial approximate Subdifferential, which was introduced as a parametric extension by Jourani and Thibault: Given any compact subset of ^p, there is a locally Lipschitzian function realizing this set as its partial approximate Subdifferential at some predefined point.This research is supported by the Schwerpunktprogramm Anwendungsbezogene Optimierung und Steuerung of the Deutsche Forschungsgemeinschaft. The paper is the written version of a lecture given at theMinisymposium on Stochastic Programming which was held at the Humboldt University of Berlin in January 1994.     

Limiting behavior of the approximate second-order subdifferential of a convex function

Hiriart-Urruty and the author recently introduced the notions of Dupin indicatrices for nonsmooth convex surfaces and studied them in connection with their concept of a second-order subdifferential for convex functions. They noticed that second-order subdifferentials can be viewed as limit sets of difference quotients involving approximate subdifferentials. In this paper, we elaborate this point in a more detailed way and discuss some related questions.The author is grateful to the referees for their helpful comments.     

拟凸函数的近似次微分及其在多目标优化问题中的应用

针对拟凸函数提出一类新的近似次微分,研究其性质,并将近似次微分应用到拟凸多目标优化问题近似解的刻画中.首先,对已有的近似次微分进行改进,得到拟凸函数新的近似次微分,并给出其与已有次微分之间的关系及一系列性质.随后,利用新的近似次微分给出拟凸多目标优化问题近似有效解、近似真有效解的最优性条件.     

On Minty variational principle for nonsmooth vector optimization problems with generalized approximate convexity

In this paper, we consider a nonsmooth vector optimization problem involving locally Lipschitz generalized approximate convex functions and find some relations between approximate convexity and generalized approximate convexity. We establish relationships between vector variational inequalities and nonsmooth vector optimization problem using the generalized approximate convexity as a tool.     

Geometric approach to convex subdifferential calculus

In this paper, we develop a geometric approach to convex subdifferential calculus in finite dimensions with employing some ideas of modern variational analysis. This approach allows us to obtain natural and rather easy proofs of basic results of convex subdifferential calculus in full generality and also derive new results of convex analysis concerning optimal value/marginal functions, normals to inverse images of sets under set-valued mappings, calculus rules for coderivatives of single-valued and set-valued mappings, and calculating coderivatives of solution maps to parameterized generalized equations governed by set-valued mappings with convex graphs.     

Subdifferential estimate of the directional derivative,optimality criterion and separation principles

We provide an inequality relating the radial directional derivative and the subdifferential of proper lower semicontinuous functions, which extends the known formula for convex functions. We show that this property is equivalent to other subdifferential properties of Banach spaces, such as controlled dense subdifferentiability, optimality criterion, mean value inequality and separation principles. As an application, we obtain a first-order sufficient condition for optimality, which extends the known condition for differentiable functions in finite-dimensional spaces and which amounts to the maximal monotonicity of the subdifferential for convex lower semicontinuous functions. Finally, we establish a formula describing the subdifferential of the sum of a convex lower semicontinuous function with a convex inf-compact function in terms of the sum of their approximate ?-subdifferentials. Such a formula directly leads to the known formula relating the directional derivative of a convex lower semicontinuous function to its approximate ?-subdifferential.     

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.     

Extensions of Fréchet ?-Subdifferential Calculus and Applications

In this paper, we establish some calculus rules for the limiting Fréchet ?-subdifferentials of marginal functions and composite functions. Necessary conditions for approximate solutions of a constrained optimization problem are derived.     

On global subdifferentials with applications in nonsmooth optimization

The notions of global subdifferentials associated with the global directional derivatives are introduced in the following paper. Most common used properties, a set of calculus rules along with a mean value theorem are presented as well. In addition, a diversity of comparisons with well-known subdifferentials such as Fréchet, Dini, Clarke, Michel–Penot, and Mordukhovich subdifferential and convexificator notion are provided. Furthermore, the lower global subdifferential is in fact proved to be an abstract subdifferential. Therefore, the lower global subdifferential satisfies standard properties for subdifferential operators. Finally, two applications in nonconvex nonsmooth optimization are given: necessary and sufficient optimality conditions for a point to be local minima with and without constraints, and a revisited characterization for nonsmooth quasiconvex functions.

     

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.     

The conjugate of a difference of functions defined on different spaces

Using a generalization of the chain rule of subdifferential calculus we derive expressions for the conjugate of the difference of functions defined on different spaces. As a consequence we are able to extend PSCHENICHNYI'S formula for (M - N)* such as generalized by HIRIART-URRUTY.