Exhausters af a positively homogeneous function *

Notions of upper exhauster and lower exhauster of a positively homogeneous (of the first degree) function h: ? ⁿ →? are introduced. They are linked to exhaustive families of upper convex and lower concave approximations of the function h. The pair of an upper exhauster and a lower exhauster is called a biexhauster of h. A calculus for biexhausters is described (in particular, a composition theorem is formulated). The problem of minimality of exhausters is stated. Necessary and sufficient conditions for a constrained minimum and a constrained maximum of a directionally differentiable function f: ? ⁿ →? are formulated in terms of exhausters of the directional derivative of f. In general, they are described by means of exhausters of the Hadamard upper and lower directional derivatives of the function f. To formulate conditions for a minimum, an upper exhauster is employed while conditions for a maximum are formulated via a lower exhauster of the respective directional derivative (the Hadamard lower derivative for a minimum and the Hadamard upper derivative for a maximum).

If a point x _o is not stationary then directions of steepest ascent and descent can also be calculated by means of exhausters.     

Exhausters, optimality conditions and related problems

The notions of exhausters were introduced in (Demyanov, Exhauster of a positively homogeneous function, Optimization 45, 13–29 (1999)). These dual tools (upper and lower exhausters) can be employed to describe optimality conditions and to find directions of steepest ascent and descent for a very wide range of nonsmooth functions. What is also important, exhausters enjoy a very good calculus (in the form of equalities). In the present paper we review the constrained and unconstrained optimality conditions in terms of exhausters, introduce necessary and sufficient conditions for the Lipschitzivity and Quasidifferentiability, and also present some new results on relationships between exhausters and other nonsmooth tools (such as the Clarke, Michel-Penot and Fréchet subdifferentials).     

Adjoint Coexhausters in Nonsmooth Analysis and Extremality Conditions

In the classical (“smooth”) mathematical analysis, a differentiable function is studied by means of the derivative (gradient in the multidimensional space). In the case of nondifferentiable functions, the tools of nonsmooth analysis are to be employed. In convex analysis and minimax theory, the corresponding classes of functions are investigated by means of the subdifferential (it is a convex set in the dual space), quasidifferentiable functions are treated via the notion of quasidifferential (which is a pair of sets). To study an arbitrary directionally differentiable function, the notions of upper and lower exhausters (each of them being a family of convex sets) are used. It turns out that conditions for a minimum are described by an upper exhauster, while conditions for a maximum are stated in terms of a lower exhauster. This is why an upper exhauster is called a proper one for the minimization problem (and an adjoint exhauster for the maximization problem) while a lower exhauster will be referred to as a proper one for the maximization problem (and an adjoint exhauster for the minimization problem). The directional derivatives (and hence, exhausters) provide first-order approximations of the increment of the function under study. These approximations are positively homogeneous as functions of direction. They allow one to formulate optimality conditions, to find steepest ascent and descent directions, to construct numerical methods. However, if, for example, the maximizer of the function is to be found, but one has an upper exhauster (which is not proper for the maximization problem), it is required to use a lower exhauster. Instead, one can try to express conditions for a maximum in terms of upper exhauster (which is an adjoint one for the maximization problem). The first to get such conditions was Roshchina. New optimality conditions in terms of adjoint exhausters were recently obtained by Abbasov. The exhauster mappings are, in general, discontinuous in the Hausdorff metric, therefore, computational problems arise. To overcome these difficulties, the notions of upper and lower coexhausters are used. They provide first-order approximations of the increment of the function which are not positively homogeneous any more. These approximations also allow one to formulate optimality conditions, to find ascent and descent directions (but not the steepest ones), to construct numerical methods possessing good convergence properties. Conditions for a minimum are described in terms of an upper coexhauster (which is, therefore, called a proper coexhauster for the minimization problem) while conditions for a maximum are described in terms of a lower coexhauster (which is called a proper one for the maximization problem). In the present paper, we derive optimality conditions in terms of adjoint coexhausters.     

Proper exhausters and coexhausters in nonsmooth analysis

There exist many tools to analyze nonsmooth functions. For convex and max-type functions, the notion of subdifferential is used, for quasidifferentiable functions – that of quasidifferential. By means of these tools, one is able to solve, e.g. the following problems: to get an approximation of the increment of a functional, to formulate conditions for an extremum, to find steepest descent and ascent directions and to construct numerical methods. For arbitrary directionally differentiable functions, these problems are solved by employing the notions of upper and lower exhausters and coexhausters, which are generalizations of such notions of nonsmooth analysis as sub- and superdifferentials, quasidifferentials and codifferentials. Exhausters allow one to construct homogeneous approximations of the increment of a functional while coexhausters provide nonhomogeneous approximations. It became possible to formulate conditions for an extremum in terms of exhausters and coexhausters. It turns out that conditions for a minimum are expressed by an upper exhauster, and conditions for a maximum are formulated via a lower one. This is why an upper exhauster is called a proper one for the minimization problem (and adjoint for the maximization problem) while a lower exhauster is called a proper one for the maximization problem (and adjoint for the minimization problem). The conditions obtained provide a simple geometric interpretation and allow one to find steepest descent and ascent directions. In this article, optimization problems are treated by means of proper exhausters and coexhausters.     

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.     

Weak subdifferential/superdifferential,weak exhausters and optimality conditions

In this work, the notion of weak superdifferential is presented. Some calculation rules are given to evaluate weak subdifferential and weak superdifferential of some classes of functions represented by support functions. Moreover, some methods are obtained to calculate weak subdifferential of convex functions. In addition, the concept of weak lower and weak upper exhausters of positively homogeneous functions are introduced by using weak subdifferential and weak superdifferential, respectively. In terms of weak exhausters, some optimality conditions are given to find local or global minimizers/maximizers of some classes of functions.     

Reduction of finite exhausters

In this paper we introduce the notation of shadowing sets which is a generalization of the notion of separating sets to the family of more than two sets. We prove that \({\bigcap_{i\in I}A_{i}}\) is a shadowing set of the family \({\{A_{i}\}_{i\in I}}\) if and only if \({\sum_{i\in I}A_{i}=\bigvee_{i\in I}\sum_{k\in I\setminus \{i\}}A_{i} + \bigcap_{i\in I}A_{i}}\). It generalizes the theorem stating that \({A\cap B}\) is separating set for A and B if and only if \({A+B=A\cap B+A\vee B}\). In terms of shadowing sets, we give a criterion for an arbitrary upper exhauster to be an exhauster of sublinear function and a criterion for the minimality of finite upper exhausters. Finally we give an example of two different minimal upper exhausters of the same function, which answers a question posed by Vera Roshchina (J Convex Anal, to appear).     

Extremum conditions for a nonsmooth function in terms of exhausters and coexhausters

The notions of upper and lower exhausters and coexhausters are discussed and necessary conditions for an unconstrained extremum of a nonsmooth function are derived. The necessary conditions for a minimum are formulated in terms of an upper exhauster (coexhauster) and the necessary conditions for a maximum are formulated in terms of a lower exhauster (coexhauster). This involves the problem of transforming an upper exhauster (coexhauster) into a lower exhauster (coexhauster) and vice versa. The transformation is carried out by means of a conversion operation (converter). Second-order approximations obtained with the help of second-order (upper and lower) coexhausters are considered. It is shown how a secondorder upper coexhauster can be converted into a lower coexhauster and vice versa. This problem is reduced to using a first-order conversion operator but in a space of a higher dimension. The obtained result allows one to construct second-order methods for the optimization of nonsmooth functions (Newton-type methods).     

Lipschitzian stability of parametric variational inequalities over perturbed polyhedral convex sets

In this paper we investigate the Lipschitz-like property of the solution mapping of parametric variational inequalities over perturbed polyhedral convex sets. By establishing some lower and upper estimates for the coderivatives of the solution mapping, among other things, we prove that the solution mapping could not be Lipschitz-like around points where the positive linear independence condition is invalid. Our analysis is based heavily on the Mordukhovich criterion (Mordukhovich in Variational Analysis and Generalized Differentiation. vol. I: Basic Theory, vol. II: Applications. Springer, Berlin, 2006) of the Lipschitz-like property for set-valued mappings between Banach spaces and recent advances in variational analysis. The obtained result complements the corresponding ones of Nam (Nonlinear Anal 73:2271–2282, 2010) and Qui (Nonlinear Anal 74:1674–1689, 2011).     

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.     

Relationships between upper exhausters and the basic subdifferential in variational analysis

In this paper we establish a relationship between the basic subdifferential and upper exhausters of positively homogeneous and polyhedral functions. In the case of a finite exhauster this relationship is represented in a form of an equality, and in the case of a Lipschitz function an inclusion formula is obtained.     

An Inexact SQP Newton Method for Convex SC<Superscript>1</Superscript> Minimization Problems

In this paper, we present a globally and superlinearly convergent inexact SQP Newton method for solving large scale convex SC ¹ minimization problems under mild conditions. In particular, the BD-regularity assumption made by Pang and Qi in Journal of Optimization Theory and Applications, 85 (1995), pp. 633–648 is replaced by a much more realistic assumption. Our numerical experiments conducted on least squares semidefinite programming with lower and upper bounds demonstrate that our inexact SQP Newton method is much more efficient than its exact version and is competitive with existing methods when the number of simple constraints is very large.     

Morse�CBott functions and the Lusternik�CSchnirelmann category

Lusternik–Schnirelmann category of a manifold gives a lower bound of the number of critical points of a differentiable map on it. The purpose of this paper is to show how to construct cone-decompositions of manifolds by using functions of class C ¹ and their gradient flows, where cone-decompositions are used to give an upper bound for the Lusternik–Schnirelmann category which is a homotopy invariant of a topological space. In particular, the Morse–Bott functions on the Stiefel manifolds considered by Frankel (1965) are effectively used to construct the conedecompositions of Stiefel manifolds and symmetric Riemannian spaces to determine their Lusternik–Schnirelmann categories.     

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.     

Generalized qd algorithm and Markov–Bernstein inequalities for Jacobi weight

The Markov–Bernstein inequalities for the Jacobi measure remained to be studied in detail. Indeed the tools used for obtaining lower and upper bounds of the constant which appear in these inequalities, did not work, since it is linked with the smallest eigenvalue of a five diagonal positive definite symmetric matrix. The aim of this paper is to generalize the qd algorithm for positive definite symmetric band matrices and to give the mean to expand the determinant of a five diagonal symmetric matrix. After that these new tools are applied to the problem to produce effective lower and upper bounds of the Markov–Bernstein constant in the Jacobi case. In the last part we com pare, in the particular case of the Gegenbauer measure, the lower and upper bounds which can be deduced from this paper, with those given in Draux and Elhami (Comput J Appl Math 106:203–243, 1999) and Draux (Numer Algor 24:31–58, 2000).      

Lipschitz Functions and Ekeland’s Theorem

As shown by F. Sullivan (Proc. Am. Math. Soc. 83:345–346, 1981), validity of the weak Ekeland variational principle implies completeness of the underlying metric space. In this note, we show that what really forces completeness in Sullivan’s argument is an even simpler geometric property of lower bounded Lipschitz functions. We derive the weak Ekeland principle from this new property, and use the new property to directly obtain an omnibus non-empty intersection result for decreasing sequences of closed sets that yields as special cases the theorems of Cantor and Kuratowski valid in complete metric spaces     

Differential calculus and integration of generalized functions over membranes

In this paper we continue the development of the differential calculus started in Aragona et al. (Monatsh. Math. 144:13–29, 2005). Guided by the so-called sharp topology and the interpretation of Colombeau generalized functions as point functions on generalized point sets, we introduce the notion of membranes and extend the definition of integrals, given in Aragona et al. (Monatsh. Math. 144:13–29, 2005), to integrals defined on membranes. We use this to prove a generalized version of the Cauchy formula and to obtain the Goursat Theorem for generalized holomorphic functions. A number of results from classical differential and integral calculus, like the inverse and implicit function theorems and Green’s theorem, are transferred to the generalized setting. Further, we indicate that solution formulas for transport and wave equations with generalized initial data can be obtained as well.     

Order Embeddings with Irrational Codomain: Debreu Properties of Real Subsets

The objective of this paper is to investigate the role of the set of irrational numbers as the codomain of order-preserving functions defined on topological totally preordered sets. We will show that although the set of irrational numbers does not satisfy the Debreu property it is still nonetheless true that any lower (respectively, upper) semicontinuous total preorder representable by a real-valued strictly isotone function (semicontinuous or not) also admits a representation by means of a lower (respectively, upper) semicontinuous strictly isotone function that takes values in the set of irrational numbers. These results are obtained by means of a direct construction. Moreover, they can be related to Cantor’s characterization of the real line to obtain much more general results on the semicontinuous Debreu properties of a wide family of subsets of the real line.      

Characterizations of the Nonemptiness and?Boundedness of Weakly Efficient Solution Sets of?Convex Vector Optimization Problems in Real Reflexive?Banach Spaces

Under a weak compactness assumption on the functions involved, which always holds in finite-dimensional normed linear spaces, this paper extends various characterizations of the nonemptiness and boundedness of weakly efficient solution sets of convex vector optimization problems, obtained previously by the author (Deng in J. Optim. Theory Appl. 96:123–131, 1998) in the real finite-dimensional normed linear space setting, to those in the real reflexive Banach space setting.