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.     

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).     

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.     

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.     

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.     

Approximation and optimization of discrete and differential inclusions described by inequality constraints

In the first part of this article optimization of polyhedral discrete and differential inclusions is considered, the problem is reduced to convex minimization problem and the necessary and sufficient condition for optimality is derived. The optimality conditions for polyhedral differential inclusions based on discrete-approximation problem according to continuous problems are formulated. In particular, boundedness of the set of adjoint discrete solutions and upper semi-continuity of the locally adjoint mapping are proved. In the second part of this article an optimization problem described by convex inequality constraint is studied. By using the equivalence theorem concerning the subdifferential calculus and approximating method necessary and sufficient condition for discrete-approximation problem with inequality constraint is established.     

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).     

Optimal Control of Differential–Algebraic Equations of Higher Index,Part 2: Necessary Optimality Conditions

This paper deals with optimal control problems described by higher index DAEs. We introduce a class of problems which can be transformed to index one control problems. For these problems we show in the accompanying paper that, if the solutions to the adjoint equations are well–defined, then the first-order approximations to the functionals defining the problem can be expressed in terms of the adjoint variables. In this paper we show that the solutions to the adjoint equations are essentially bounded measurable functions. Then, based on the first order approximations, we derive the necessary optimality conditions for the considered class of control problems. These conditions do not require the transformation of the DAEs to index-one system; however, higher-index DAEs and their associated adjoint equations have to be solved.     

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.     

Optimal Control of Differential–Algebraic Equations of Higher Index, Part 1: First-Order Approximations

This paper deals with optimal control problems described by higher index DAEs. We introduce a class of these problems which can be transformed to index one control problems. For this class of higher index DAEs, we derive first-order approximations and adjoint equations for the functionals defining the problem. These adjoint equations are then used to state, in the accompanying paper, the necessary optimality conditions in the form of a weak maximum principle. The constructive way used to prove these optimality conditions leads to globally convergent algorithms for control problems with state constraints and defined by higher index DAEs.     

The Fundamental Solution and Its Role in the Optimal Control of Infinite Dimensional Neutral Systems

In this work, we shall consider standard optimal control problems for a class of neutral functional differential equations in Banach spaces. As the basis of a systematic theory of neutral models, the fundamental solution is constructed and a variation of constants formula of mild solutions is established. We introduce a class of neutral resolvents and show that the Laplace transform of the fundamental solution is its neutral resolvent operator. Necessary conditions in terms of the solutions of neutral adjoint systems are established to deal with the fixed time integral convex cost problem of optimality. Based on optimality conditions, the maximum principle for time varying control domain is presented. Finally, the time optimal control problem to a target set is investigated.     

Dynamic convex duality in constrained utility maximization

ABSTRACT

In this paper, we study a constrained utility maximization problem following the convex duality approach. After formulating the primal and dual problems, we construct the necessary and sufficient conditions for both the primal and dual problems in terms of forward and backward stochastic differential equations (FBSDEs) plus some additional conditions. Such formulation then allows us to explicitly characterize the primal optimal control as a function of the adjoint process coming from the dual FBSDEs in a dynamic fashion and vice versa. We also find that the optimal wealth process coincides with the adjoint process of the dual problem and vice versa. Finally we solve three constrained utility maximization problems, which contrasts the simplicity of the duality approach we propose and the technical complexity of solving the primal problem directly.     

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.     

A Maximum Principle for SDEs of Mean-Field Type

We study the optimal control of a stochastic differential equation (SDE) of mean-field type, where the coefficients are allowed to depend on some functional of the law as well as the state of the process. Moreover the cost functional is also of mean-field type, which makes the control problem time inconsistent in the sense that the Bellman optimality principle does not hold. Under the assumption of a convex action space a maximum principle of local form is derived, specifying the necessary conditions for optimality. These are also shown to be sufficient under additional assumptions. This maximum principle differs from the classical one, where the adjoint equation is a linear backward SDE, since here the adjoint equation turns out to be a linear mean-field backward SDE. As an illustration, we apply the result to the mean-variance portfolio selection problem.     

Characterizing global optimality for DC optimization problems under convex inequality constraints

Characterizations of global optimality are given for general difference convex (DC) optimization problems involving convex inequality constraints. These results are obtained in terms of -subdifferentials of the objective and constraint functions and do not require any regularity condition. An extension of Farkas' lemma is obtained for inequality systems involving convex functions and is used to establish necessary and sufficient optimality conditions. As applications, optimality conditions are also given for weakly convex programming problems, convex maximization problems and for fractional programming problems.This paper was presented at the Optimization Miniconference held at the University of Ballarat, Victoria, Australia, on July 14, 1994.     

Inscribed ball and enclosing box methods for the convex maximization problem

Many important classes of decision models give rise to the problem of finding a global maximum of a convex function over a convex set. This problem is known also as concave minimization, concave programming or convex maximization. Such problems can have many local maxima, therefore finding the global maximum is a computationally difficult problem, since standard nonlinear programming procedures fail. In this article, we provide a very simple and practical approach to find the global solution of quadratic convex maximization problems over a polytope. A convex function achieves its global maximum at extreme points of the feasible domain. Since an inscribed ball does not contain any extreme points of the domain, we use the largest inscribed ball for an inner approximation while a minimal enclosing box is exploited for an outer approximation of the domain. The approach is based on the use of these approximations along with the standard local search algorithm and cutting plane techniques.     

Reducing Exhausters

The notions of upper and lower exhausters were introduced by Demyanov (Optimization 45:13–29, 1999). Upper and lower exhausters can be employed to study a very wide range of positively homogeneous functions, for example, various directional derivatives of nonsmooth functions. Exhausters are not uniquely defined; hence, the problem of minimality arises naturally. This paper describes some techniques for reducing exhausters, both in size and amount of sets. We define also a modified convertor which provides much more flexibility in converting upper exhausters to lower ones and vice versa, and allows us to obtain much smaller sets.     

非光滑向量极值问题的真有效解与最优性条件

讨论了赋范线性空间中非光滑向量极值问题的Hatley,Borwein,Benson真有效解之间的关系,指出了它们共同的标量极值问题的等价刻画,建立了问题（VMP）的广义KT-真有效解的充分条件,并给出了向量极小值问题在锥局部凸、拟凸、伪凸等条件下的最优性条件。     

Conditions for boundedness in concave programming under reverse convex and convex constraints

In this paper, we are concerned with the problem of boundedness in the constrained global maximization of a convex function. In particular, we present necessary and sufficient conditions for boundedness of a feasible region defined by reverse convex constraints and we establish sufficient and necessary conditions for existence of an upper bound for a convex objective function defined over the system of concave inequality constraints. We also address the problem of boundedness in the global maximization problem when a feasible region is convex and unbounded.     

Inhomogeneous convex approximations of nonsmooth functions

In this paper we introduce notions of inhomogeneous upper convex and lower concave approximations of an increment of a nonsmooth function defined on a normed space and study exhaustive families of these approximations. In terms of the introduced notions we establish optimality conditions for various constrained and unconstrained extremum problems.