Comparison Between Quasidifferentials and Exhausters

Directional derivatives play one of the major roles in optimization. Optimality conditions can be described in terms of these objects. These conditions, however, are not constructive. To overcome this problem, one has to represent the directional derivative in special forms. Two such forms are quasidifferentials and exhausters proposed by V.F. Demyanov. Quasidifferentials were introduced in 1980s. Optimality conditions in terms of these objects were developed by L.N. Polyakova and V.F. Demyanov. It was described how to find directions of steepest descent and ascent when these conditions are not satisfied. This paved a way for constructing new optimization algorithms. Quasidifferentials allow one to treat a wide class of functions. V.F. Demyanov introduced the notion of exhausters in 2000s to expand the class of functions that can be treated. It should be noted that a great contribution to the emergence of this notion was made by B.N. Pshenichny and A.M. Rubinov. In this work it is shown that exhausters not only allow one to treat a wider class of functions than quasidifferentials (since every quasidifferentiable function has exhausters) but is also preferable even for quasidifferentiable functions when solving nonsmooth optimization problems.     

Multidirectional Mean Value Inequalities in Quasidifferential Calculus

In the current paper, a Clarke–Ledyaev type mean value inequality is proved for semicontinuous functions defined in a Banach space that are quasidifferentiable in the sense of Demyanov–Rubinov. A stronger variant valid under compactness assumption in separable spaces and extensions for functions with semicontinuous Dini derivatives in locally uniformly convex Banach spaces and with merely bounded Dini derivatives are then established. Subsequently, applications of these mean value inequalities to solvability of nonsmooth parametric equations and to the estimation of local and global Hoffman error bound for inequalities are investigated via a decrease principle.     

Convex Difference Criteria for the Quantitative Stability of Parametric Quasidifferentiable Systems

In this paper solvability and Lipschitzian stability properties for a special class of nonsmooth parametric generalized systems defined in Banach are studied via a variational analysis approach. Verifiable sufficient conditions for such properties to hold under scalar quasidifferentiability assumptions are formulated by combining *-difference and Demyanov difference of convex compact subsets of the dual space with classic quasidifferential calculus constructions. Applications to the formulation of sufficient conditions for metric regularity/open covering of nonsmooth maps, along with their employment in deriving optimality conditions for quasidifferentiable extremum problems, as well as an application to the study of semicontinuity of the optimal value function in parametric optimization are discussed. In memory of Aleksandr Moiseevich Rubinov (1940–2006).     

Generalized derivatives and nonsmooth optimization, a finite dimensional tour

During the early 1960’s there was a growing realization that a large number of optimization problems which appeared in applications involved minimization of non-differentiable functions. One of the important areas where such problems appeared was optimal control. The subject of nonsmooth analysis arose out of the need to develop a theory to deal with the minimization of nonsmooth functions. The first impetus in this direction came with the publication of Rockafellar’s seminal work titledConvex Analysis which was published by the Princeton University Press in 1970. It would be impossible to overstate the impact of this book on the development of the theory and methods of optimization. It is also important to note that a large part of convex analysis was already developed by Werner Fenchel nearly twenty years earlier and was circulated through his mimeographed lecture notes titledConvex Cones, Sets and Functions, Princeton University, 1951. In this article we trace the dramatic development of nonsmooth analysis and its applications to optimization in finite dimensions. Beginning with the fundamentals of convex optimization we quickly move over to the path breaking work of Clarke which extends the domain of nonsmooth analysis from convex to locally Lipschitz functions. Clarke was the second doctoral student of R.T. Rockafellar. We discuss the notions of Clarke directional derivative and the Clarke generalized gradient and also the relevant calculus rules and applications to optimization. While discussing locally Lipschitz optimization we also try to blend in the computational aspects of the theory wherever possible. This is followed by a discussion of the geometry of sets with nonsmooth boundaries. The approach to develop the notion of the normal cone to an arbitrary set is sequential in nature. This approach does not rely on the standard techniques of convex analysis. The move away from convexity was pioneered by Mordukhovich and later culminated in the monographVariational Analysis by Rockafellar and Wets. The approach of Mordukhovich relied on a nonconvex separation principle called theextremal principle while that of Rockafellar and Wets relied on various convergence notions developed to suit the needs of optimization. We then move on to a parallel development in nonsmooth optimization due to Demyanov and Rubinov called Quasidifferentiable optimization. They study the class of directionally differentiable functions whose directional derivatives can be represented as a difference of two sublinear functions. On other hand the directional derivative of a convex function and also the Clarke directional derivatives are sublinear functions of the directions. Thus it was thought that the most useful generalizations of directional derivatives must be a sublinear function of the directions. Thus Demyanov and Rubinov made a major conceptual change in nonsmooth optimization. In this section we define the notion of a quasidifferential which is a pair of convex compact sets. We study some calculus rules and their applications to optimality conditions. We also study the interesting notion of Demyanov difference between two sets and their applications to optimization. In the last section of this paper we study some second-order tools used in nonsmooth analysis and try to see their relevance in optimization. In fact it is important to note that unlike the classical case, the second-order theory of nonsmoothness is quite complicated in the sense that there are many approaches to it. However we have chosen to describe those approaches which can be developed from the first order nonsmooth tools discussed here. We shall present three different approaches, highlight the second order calculus rules and their applications to optimization.     

广义拟可微函数的微分

本文给出一种广义拟可微函数类,它是Demyanov与Rlubinov(1980)意义下拟可微函数的推广,通过凸集类对的空间的某些理论,建立了这类广义拟可微函数的微分学理论,包括加法运算、数乘运算、乘法运算、除法运算、极大值运算,极小值运算以及复合运算的微分公式和中值定理。这些结果为广义拟可微类函数优化研究提供了基本工具．     

The directed and Rubinov subdifferentials of quasidifferentiable functions, Part II: Calculus

We continue the study of the directed subdifferential for quasidifferentiable functions started in [R. Baier, E. Farkhi, V. Roshchina, The directed and Rubinov subdifferentials of quasidifferentiable functions, Part I: Definition and examples (this journal)]. Calculus rules for the directed subdifferentials of sum, product, quotient, maximum and minimum of quasidifferentiable functions are derived. The relation between the Rubinov subdifferential and the subdifferentials of Clarke, Dini, Michel-Penot, and Mordukhovich is discussed. Important properties implying the claims of Ioffe’s axioms as well as necessary and sufficient optimality conditions for the directed subdifferential are obtained.     

关于一个次线性逼近定理的新证法

Ｄｅｍｙａｎｏｖ和Ｒｕｂｉｎｏｖ在［１］中给出了一个次线性逼近定理．本文对该定理的证明进行了修正．     

Characterization Theorem for Best Polynomial Spline Approximation with Free Knots,Variable Degree and Fixed Tails

In this paper, we derive a necessary condition for a best approximation by piecewise polynomial functions of varying degree from one interval to another. Based on these results, we obtain a characterization theorem for the polynomial splines with fixed tails, that is the value of the spline is fixed in one or more knots (external or internal). We apply nonsmooth nonconvex analysis to obtain this result, which is also a necessary and sufficient condition for inf-stationarity in the sense of Demyanov–Rubinov. This paper is an extension of a paper where similar conditions were obtained for free tails splines. The main results of this paper are essential for the development of a Remez-type algorithm for free knot spline approximation.     

A Chain Rule for Upper Semicontinuous (CF)-Mappings

A chain rule for calculating convexificators of composite functions of the type f = h∘g, with the inner factor g being a transformation of , is proposed. The proof is based on a double application of a mean value theorem for (CF)-mappings due to V.F. Demyanov and V. Jeyakumar (see [4]), along with a stability property for the support of a certain ɛ-perturbation of (CF)-mappings.     

Representative of Quasidifferentials and Its Formula for a Quasidifferentiable Function

The quasidifferential of a quasidifferentiable function in the sense of Demyanov and Rubinov is not uniquely defined. Xia proposed the notion of the kernelled quasidifferential, which is expected to be a representative for the equivalent class of quasidifferentials. In the 2-dimensional case, the existence of the kernelled quasidifferential was shown. In this paper, the existence of the kernelled quasidifferential in the n-dimensional space (n>2) is proved under the assumption that the Minkowski difference and the Demyanov difference of subdifferential and minus superdifferential coincide. In particular, given a quasidifferential, the kernelled quasidifferential can be formulated. Applications to two classes of generalized separable quasidifferentiable functions are developed. Mathematics Subject Classifications (2000) 49J52, 54C60, 90C26. This work was supported by Shanghai Education Committee (04EA01).     

Difference of two sets and estimation of clarke generalized Jacobian via quasidifferential

The notion of difference for two convex compact sets inR ⁿ , proposed by Rubinovet al, is generalized toR ^m×n . A formula of the difference for the two sets, which are convex hulls of a finite number of points, is developed. In the light of this difference, the relation between Clarke generalized Jacobian and quasidifferential, in the sense of Demyanov and Rubinov, for a nonsnooth function, is established. Based on the relation, the method of estimating Clarke generalized Jacobian via quasidifferential for a certain class of functions, is presented.     

Newton-Type Methods for Quasidifferentiable Equations

In this paper, we present two Newton-type methods for solving quasidifferentiable equations in the sense of Demyanov and Rubinov (Ref. 1). Method I is well defined and is a natural extension of the classical Newton method, based on a generalized Kakutani fixed-point theorem. Method II is a simplified version and requires less computation than Method I. Under some mild assumptions, we establish a locally quadratic convergent theorem for Method I and prove a semilocal convergence theorem for Method II.     

Reduction and Minimality of Coexhausters

V.F. Demyanov introduced exhausters for the study of nonsmooth functions. These are families of convex compact sets that enable one to represent the main part of the increment of a considered function in a neighborhood of the studied point as MaxMin or MinMax of linear functions. Optimality conditions were described in terms of these objects. This provided a way for constructing new algorithms for solving nondifferentiable optimization problems. Exhausters are defined not uniquely. It is obvious that the smaller an exhauster, the less are the computational expenses when working with it. Thus, the problem of reduction of an available family arises. For the first time, this problem was considered by V.A. Roshchina. She proposed conditions for minimality and described some methods of reduction in the case when these conditions are not satisfied. However, it turned out that the exhauster mapping is not continuous in the Hausdorff metrics, which leads to the problems with convergence of numerical methods. To overcome this difficulty, Demyanov proposed the notion of coexhausters. These objects enable one to represent the main part of the increment of the considered function in a neighborhood of the studied point in the form of MaxMin or MinMax of affine functions. One can define a class of functions with the continuous coexhauster mapping. Optimality conditions can be stated in terms of these objects too. But coexhausters are also defined not uniquely. The problem of reduction of coexhausters is considered in this paper for the first time. Definitions of minimality proposed by Roshchina are used. In contrast to ideas proposed in the works of Roshchina, the minimality conditions and the technique of reduction developed in this paper have a clear and transparent geometric interpretation.     

Higher order optimality conditions with an arbitrary non-differentiable function

In this paper, we introduce a higher order directional derivative and higher order subdifferential of Hadamard type of a given proper extended real function. We obtain necessary and sufficient optimality conditions of order n (n is a positive integer) for unconstrained problems in terms of them. We do not require any restrictions on the function in our results. In contrast to the most known directional derivatives, our derivative is harmonized with the classical higher order Fréchet directional derivative of the same order in the sense that both of them coincide, provided that the last one exists. A notion of a higher order critical direction is introduced. It is applied in the characterizations of the isolated local minimum of order n. Higher order invex functions are defined. They are the largest class such that the necessary conditions for a local minimum are sufficient for global one. We compare our results with some previous ones. As an application, we improve a result due to V. F. Demyanov, showing that the condition introduced by this author is a complete characterization of isolated local minimizers of order n.     

On the Fourier-Laplace transform of functionals on a space of infinitely differentiable functions on a convex compact

Classes of ultradifferentiable functions are classically defined by imposing growth conditions on the derivatives of the functions. Following this approach we consider a Fréchet-Schwartz space of infinitely differentiable functions on a closure of a bounded convex domain of multidimensional real space with uniform bounds on their partial derivatives. Our aim is to obtain Paley-Wiener-Schwartz type theorem connecting properties of linear continuous functionals on this space with the behaviour of their Fourier-Laplace transforms. Very similar problems were considered by M. Neymark, B.A. Taylor, M. Langenbruch, A.V. Abanin.     

Proper and adjoint exhausters in nonsmooth analysis: optimality conditions

The notions of upper and lower exhausters represent generalizations of the notions of exhaustive families of upper convex and lower concave approximations (u.c.a., l.c.a.). The notions of u.c.a.’s and l.c.a.’s were introduced by Pshenichnyi (Convex Analysis and Extremal Problems, Series in Nonlinear Analysis and its Applications, 1980), while the notions of exhaustive families of u.c.a.’s and l.c.a.’s were described by Demyanov and Rubinov in Nonsmooth Problems of Optimization Theory and Control, Leningrad University Press, Leningrad, 1982. These notions allow one to solve the problem of optimization of an arbitrary function by means of Convex Analysis thus essentially extending the area of application of Convex Analysis. In terms of exhausters it is possible to describe extremality conditions, and it turns out that conditions for a minimum are expressed via an upper exhauster while conditions for a maximum are formulated in terms of a lower exhauster (Abbasov and Demyanov (2010), Demyanov and Roshchina (Appl Comput Math 4(2): 114–124, 2005), Demyanov and Roshchina (2007), Demyanov and Roshchina (Optimization 55(5–6): 525–540, 2006)). This is why an upper exhauster is called a proper exhauster for minimization problems while a lower exhauster is called a proper one for maximization problems. The results obtained provide a simple geometric interpretation and allow one to construct steepest descent and ascent directions. Until recently, the problem of expressing extremality conditions in terms of adjoint exhausters remained open. Demyanov and Roshchina (Appl Comput Math 4(2): 114–124, 2005), Demyanov and Roshchina (Optimization 55(5–6): 525–540, 2006) was the first to derive such conditions. However, using the conditions obtained (unlike the conditions expressed in terms of proper exhausters) it was not possible to find directions of descent and ascent. In Abbasov (2011) new extremality conditions in terms of adjoint exhausters were discovered. In the present paper, a different proof of these conditions is given and it is shown how to find steepest descent and ascent conditions in terms of adjoint exhausters. The results obtained open the way to constructing numerical methods based on the usage of adjoint exhausters thus avoiding the necessity of converting the adjoint exhauster into a proper one.     

Cubic spline solution of singularly perturbed boundary value problems with significant first derivatives

We develop a numerical technique for a class of singularly perturbed two-point singular boundary value problems on an uniform mesh using polynomial cubic spline. The scheme derived in this paper is second-order accurate. The resulting linear system of equations has been solved by using a tri-diagonal solver. Numerical results are provided to illustrate the proposed method and to compared with the methods in [R.K. Mohanty, Urvashi Arora, A family of non-uniform mesh tension spline methods for singularly perturbed two-point singular boundary value problems with significant first derivatives, Appl. Math. Comput., 172 (2006) 531–544; M.K. Kadalbajoo, V.K. Aggarwal, Fitted mesh B-spline method for solving a class of singular singularly perturbed boundary value problems, Int. J. Comput. Math. 82 (2005) 67–76].     

Exact calculus of Fréchet subdifferentials for Hadamard directionally differentiable functions

We continue the study of the calculus of the generalized subdifferentials started in [V.F. Demyanov, V. Roshchina, Exhausters and subdifferentials in nonsmooth analysis, Optimization (2006) (in press)] and [V. Roshchina, Relationships between upper exhausters and the basic subdifferential in Variational Analysis, Journal of Mathematical Analysis and Applications 334 (2007) 261–272] and provide some basic calculus rules for the Fréchet subdifferentials via collections of compact convex sets associated with Hadamard directional derivative. The main result of this paper is the sum rule for the Fréchet subdifferential in the form of an equality, which holds for Hadamard directionally differentiable functions, and is of significant interest from the points of view of both theory and applications.     

A Solution Method for a Special Class of Nondifferentiable Unconstrained Optimization Problems

We consider quasidifferentiable functions in the sense of Demyanov and Rubinov, i. e. functions, which are directionally differentiable and whose directional derivative can be expressed as a difference of two sublinear functions, so that its subdifferential, called the quasidifferential, consists of a pair of sets. For these functions a generalized gradient algorithm is proposed. Its behaviour is studied in detail for the special class of continuously subdifferentiable functions. Numerical test results are given. Finally, the general quasidifferentiable case is simulated by means of perturbed subdifferentials, where we make use of the non-uniqueness in the quasidifferential representation.     

Fenchel-Lagrange Duality Versus Geometric Duality in Convex Optimization

We present a new duality theory to treat convex optimization problems and we prove that the geometric duality used by Scott and Jefferson in different papers during the last quarter of century is a special case of it. Moreover, weaker sufficient conditions to achieve strong duality are considered and optimality conditions are derived. Next, we apply our approach to some problems considered by Scott and Jefferson, determining their duals. We give weaker sufficient conditions to achieve strong duality and the corresponding optimality conditions. Finally, posynomial geometric programming is viewed also as a particular case of the duality approach that we present. Communicated by V. F. Demyanov The first author was supported in part by Gottlieb Daimler and Karl Benz Stiftung 02-48/99. The second author was supported in part by Karl und Ruth Mayer Stiftung.