Subdifferentials of value functions and optimality conditions for DC and bilevel infinite and semi-infinite programs

The paper concerns the study of new classes of parametric optimization problems of the so-called infinite programming that are generally defined on infinite-dimensional spaces of decision variables and contain, among other constraints, infinitely many inequality constraints. These problems reduce to semi-infinite programs in the case of finite-dimensional spaces of decision variables. We focus on DC infinite programs with objectives given as the difference of convex functions subject to convex inequality constraints. The main results establish efficient upper estimates of certain subdifferentials of (intrinsically nonsmooth) value functions in DC infinite programs based on advanced tools of variational analysis and generalized differentiation. The value/marginal functions and their subdifferential estimates play a crucial role in many aspects of parametric optimization including well-posedness and sensitivity. In this paper we apply the obtained subdifferential estimates to establishing verifiable conditions for the local Lipschitz continuity of the value functions and deriving necessary optimality conditions in parametric DC infinite programs and their remarkable specifications. Finally, we employ the value function approach and the established subdifferential estimates to the study of bilevel finite and infinite programs with convex data on both lower and upper level of hierarchical optimization. The results obtained in the paper are new not only for the classes of infinite programs under consideration but also for their semi-infinite counterparts.     

Minimal convex majorants of functions and Demyanov–Rubinov exhaustive super(sub)differentials

ABSTRACT

The primary goal of the paper is to establish characteristic properties of (extended) real-valued functions defined on normed vector spaces that admit the representation as the lower envelope (the pointwise infimum) of their minimal (with respect of the pointwise ordering) convex majorants. The results presented in the paper generalize and extend the well-known Demyanov-Rubinov characterization of upper semicontinuous positively homogeneous functions as the lower envelope of exhaustive families of continuous sublinear functions to larger classes of (not necessarily positively homogeneous) functions defined on arbitrary normed spaces. As applications of the above results, we introduce, for nonsmooth functions, a new notion of the Demyanov-Rubinov exhaustive subdifferential at a given point, and show that it generalizes a number of known notions of subdifferentiability, in particular, the Fenchel-Moreau subdifferential of convex functions, the Dini-Hadamard (directional) subdifferential of directionally differentiable functions, and the Φ-subdifferential in the sense of the abstract convexity theory. Some applications of Demyanov-Rubinov exhaustive subdifferentials to extremal problems are considered.     

Solving convex quadratic bilevel programming problems using an enumeration sequential quadratic programming algorithm

In this paper, we present an original method to solve convex bilevel programming problems in an optimistic approach. Both upper and lower level objective functions are convex and the feasible region is a polyhedron. The enumeration sequential linear programming algorithm uses primal and dual monotonicity properties of the primal and dual lower level objective functions and constraints within an enumeration frame work. New optimality conditions are given, expressed in terms of tightness of the constraints of lower level problem. These optimality conditions are used at each step of our algorithm to compute an improving rational solution within some indexes of lower level primal-dual variables and monotonicity networks as well. Some preliminary computational results are reported.     

Calculus rules for global approximate minima and applications to approximate subdifferential calculus

We provide calculus rules for global approximate minima concerning usual operations on functions. The formulas we obtain are then applied to approximate subdifferential calculus. In this way, new results are presented, for example on the approximate subdifferential of a deconvolution, or on the subdifferential of an upper envelope of convex functions.     

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.     

Optimality and duality for proper and isolated efficiencies in multiobjective optimization

We use some advanced tools of variational analysis and generalized differentiation such as the nonsmooth version of Fermat’s rule, the limiting/Mordukhovich subdifferential of maximum functions, and the sum rules for the Fréchet subdifferential and for the limiting one to establish necessary conditions for (local) properly efficient solutions and (local) isolated minimizers of a multiobjective optimization problem involving inequality and equality constraints. Sufficient conditions for the existence of such solutions are also provided under assumptions of (local) convex/affine functions or $L$-invex-infine functions defined in terms of the limiting subdifferential of locally Lipschitz functions. In addition, we propose a type of Wolfe dual problems and examine weak/strong duality relations under $L$-invexity-infineness hypotheses.     

Bilevel programming problems with simple convex lower level

This article is dedicated to the study of bilevel optimal control problems equipped with a fully convex lower level of special structure. In order to construct necessary optimality conditions, we consider a general bilevel programming problem in Banach spaces possessing operator constraints, which is a generalization of the original bilevel optimal control problem. We derive necessary optimality conditions for the latter problem using the lower level optimal value function, ideas from DC-programming and partial penalization. Afterwards, we apply our results to the original optimal control problem to obtain necessary optimality conditions of Pontryagin-type. Along the way, we derive a handy formula, which might be used to compute the subdifferential of the optimal value function which corresponds to the lower level parametric optimal control problem.     

Necessary and Sufficient Conditions for Weak Quasi Efficiency in Nonsmooth Multiobjective Problems

In this article, a multiobjective problem with a feasible set defined by inequality, equality and set constraints is considered, where the objective and constraint functions are locally Lipschitz. Several constraint qualifications are given and the relations between them are analyzed. We establish Kuhn-Tucker and strong Kuhn-Tucker necessary optimality conditions for (weak) quasi e?ciency in terms of the Clarke subdifferential. By using two new classes of generalized convex functions, su?cient conditions for local (weak) quasi e?cient are also provided. Furthermore, we study the Mond-Weir type dual problem and establish weak, strong and converse duality results.     

Subdifferential of the supremum function: moving back and forth between continuous and non-continuous settings

In this paper we establish general formulas for the subdifferential of the pointwise supremum of convex functions, which cover and unify both the compact continuous and the non-compact non-continuous settings. From the non-continuous to the continuous setting, we proceed by a compactification-based approach which leads us to problems having compact index sets and upper semi-continuously indexed mappings, giving rise to new characterizations of the subdifferential of the supremum by means of upper semicontinuous regularized functions and an enlarged compact index set. In the opposite sense, we rewrite the subdifferential of these new regularized functions by using the original data, also leading us to new results on the subdifferential of the supremum. We give two applications in the last section, the first one concerning the nonconvex Fenchel duality, and the second one establishing Fritz-John and KKT conditions in convex semi-infinite programming.

     

New Formulas for the Fenchel Subdifferential of the Conjugate Function

Following (López and Volle, J Convex Anal 17, 2010) we provide new formulas for the Fenchel subdifferential of the conjugate of functions defined on locally convex spaces. In particular, this allows deriving expressions for the minimizers set of the lower semicontinuous convex hull of such functions. These formulas are written by means of primal objects related to the subdifferential of the initial function, namely a new enlargement of the Fenchel subdifferential operator.     

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.     

Necessary Conditions in Nonsmooth Minimization via Lower and Upper Subgradients

The paper concerns first-order necessary optimality conditions for problems of minimizing nonsmooth functions under various constraints in infinite-dimensional spaces. Based on advanced tools of variational analysis and generalized differential calculus, we derive general results of two independent types called lower subdifferential and upper subdifferential optimality conditions. The former ones involve basic/limiting subgradients of cost functions, while the latter conditions are expressed via Fréchet/regular upper subgradients in fairly general settings. All the upper subdifferential and major lower subdifferential optimality conditions obtained in the paper are new even in finite dimensions. We give applications of general optimality conditions to mathematical programs with equilibrium constraints deriving new results for this important class of intrinsically nonsmooth optimization problems.     

Bilevel problems over polyhedra with extreme point optimal solutions

Bilevel programming involves two optimization problems where the constraint region of the upper level problem is implicitly determined by another optimization problem. In this paper we focus on bilevel problems over polyhedra with upper level constraints involving lower level variables. On the one hand, under the uniqueness of the optimal solution of the lower level problem, we prove that the fact that the objective functions of both levels are quasiconcave characterizes the property of the existence of an extreme point of the polyhedron defined by the whole set of constraints which is an optimal solution of the bilevel problem. An example is used to show that this property is in general violated if the optimal solution of the lower level problem is not unique. On the other hand, if the lower level objective function is not quasiconcave but convex quadratic, assuming the optimistic approach we prove that the optimal solution is attained at an extreme point of an ??enlarged?? polyhedron.     

Some characterizations of robust optimal solutions for uncertain convex optimization problems

In this paper, we consider robust optimal solutions for a convex optimization problem in the face of data uncertainty both in the objective and constraints. By using the properties of the subdifferential sum formulae, we first introduce a robust-type subdifferential constraint qualification, and then obtain some completely characterizations of the robust optimal solution of this uncertain convex optimization problem. We also investigate Wolfe type robust duality between the uncertain convex optimization problem and its uncertain dual problem by proving duality between the deterministic robust counterpart of the primal model and the optimistic counterpart of its dual problem. Moreover, we show that our results encompass as special cases some optimization problems considered in the recent literature.     

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.     

On an algorithm solving two-level programming problems with nonunique lower level solutions

In the paper, an algorithm is presented for solving two-level programming problems. This algorithm combines a direction finding problem with a regularization of the lower level problem. The upper level objective function is included in the regularzation to yield uniqueness of the follower's solution set. This is possible if the problem functions are convex and the upper level objective function has a positive definite Hessian. The computation of a direction of descent and of the step size is discussed in more detail. Afterwards the convergence proof is given.Last but not least some remarks and examples describing the difficulty of the inclusion of upper-level constraints also depending on the variables of the lower level are added.     

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.     

On the Maximization of (not necessarily) Convex Functions on Convex Sets

The global solutions of the problem of maximizing a convex function on a convex set were characterized by several authors using the Fenchel (approximate) subdifferential. When the objective function is quasiconvex it was considered the differentiable case or used the Clarke subdifferential. The aim of the present paper is to give necessary and sufficient optimality conditions using several subdifferentials adequate for quasiconvex functions. In this way we recover almost all the previous results related to such global maximization problems with simple proofs.     

The exact extreme response and the confidence extreme response analysis of structures subjected to uncertain-but-bounded excitations

In this study, the methods for computing the exact bounds and the confidence bounds of the dynamic response of structures subjected to uncertain-but-bounded excitations are discussed. Here the Euclidean norm of the nodal displacement is considered as the measurement of the structural response. The problem of calculating the exact lower bound, the confidence (outer) approximation and the inner approximation of the exact upper bound, and the exact upper bound of the dynamic response are modeled as three convex QB (quadratic programming with box constraints) problems and a problem of quadratic programming with bivalent constraints at each time point, respectively. Accordingly, the DCA (difference of convex functions algorithm) and the vertex method are adopted to solve the above convex QB problems and the quadratic programming problem with bivalent constraints, respectively. Based on the inner approximation and the outer approximation of the exact upper bound, the error between the confidence upper bound and the exact upper bound of dynamic response could be yielded. Specially, we also investigate how to obtain the confidence bound of the dynamic response of structures subjected to harmonic excitations with uncertain-but-bounded excitation frequencies. Four examples are given to show the efficiency and accuracy of the proposed method.     

Properties of the set of “trajectory-control” pairs of a control systemwith subdifferential operators

We consider a control system described by an evolution equation with control constraint which is a multivalued mapping of a phase variable with closed nonconvex values. One of the evolution operators of the system is the subdifferential of a time-dependent proper, convex, and lower semicontinuous function. The other operator, acting on the derivative of the required functions, is the subdifferential of a convex continuous function. We also consider systems with the following control constraints: multivalued mappings whose values are the closed convex hulls of the values of the original constraint and multivalued mapping whose values are the extreme points of the convexified constraint that belong to the original one. We study topological properties of the sets of admissible “trajectory–control” pairs of the system with various control constraints and clarify the relations between them. An example of a parabolic system with hysteresis and diffusion phenomena is considered in detail. Bibliography: 19 titles.