A weaker regularity condition for subdifferential calculus and Fenchel duality in infinite dimensional spaces

In this paper we present a new regularity condition for the subdifferential sum formula of a convex function with the precomposition of another convex function with a continuous linear mapping. This condition is formulated by using the epigraphs of the conjugates of the functions involved and turns out to be weaker than the generalized interior-point regularity conditions given so far in the literature. Moreover, it provides a weak sufficient condition for Fenchel duality regarding convex optimization problems in infinite dimensional spaces. As an application, we discuss the strong conical hull intersection property (CHIP) for a finite family of closed convex sets.     

Bounded linear regularity of convex sets in Banach spaces and its applications

This paper deals with bounded linear regularity, linear regularity and the strong conical hull intersection property (CHIP) of a collection of finitely many closed convex intersecting sets in Banach spaces. It is shown that, as in finite dimensional space setting (see [6]), the standard constraint qualification implies bounded linear regularity, which in turn yields the strong conical hull intersection property, and that the collection of closed convex sets {C ₁, . . . ,C _n } is bounded linearly regular if and only if the tangent cones of {C ₁, . . . ,C _n } has the CHIP and the normal cones of {C ₁, . . . ,C _n } has the property (G)(uniformly on a neighborhood in the intersection C). As applications, we study the global error bounds for systems of linear and convex inequalities. The work of this author was partially supported by the National Natural Sciences Grant (No. 10471032) and the Excellent Young Teachers Program of MOE, P.R.C The authors thank professor K.F.Ng for his helpful discussion and the referee for their helpful suggestions on improving the first version of this paper     

Strong conical hull intersection property, bounded linear regularity, Jameson’s property (G), and error bounds in convex optimization

The strong conical hull intersection property and bounded linear regularity are properties of a collection of finitely many closed convex intersecting sets in Euclidean space. These fundamental notions occur in various branches of convex optimization (constrained approximation, convex feasibility problems, linear inequalities, for instance). It is shown that the standard constraint qualification from convex analysis implies bounded linear regularity, which in turn yields the strong conical hull intersection property. Jameson’s duality for two cones, which relates bounded linear regularity to property (G), is re-derived and refined. For polyhedral cones, a statement dual to Hoffman’s error bound result is obtained. A sharpening of a result on error bounds for convex inequalities by Auslender and Crouzeix is presented. Finally, for two subspaces, property (G) is quantified by the angle between the subspaces. Received October 1, 1997 / Revised version received July 21, 1998? Published online June 11, 1999     

On coderivatives and Lipschitzian properties of the dual pair in optimization

In this paper, we apply the concept of coderivative and other tools from the generalized differentiation theory for set-valued mappings to study the stability of the feasible sets of both the primal and the dual problem in infinite-dimensional linear optimization with infinitely many explicit constraints and an additional conic constraint. After providing some specific duality results for our dual pair, we study the Lipschitz-like property of both mappings and also give bounds for the associated Lipschitz moduli. The situation for the dual shows much more involved than the case of the primal problem.     

Strong CHIP, normality, and linear regularity of convex sets

We extend the property (N) introduced by Jameson for closed convex cones to the normal property for a finite collection of convex sets in a Hilbert space. Variations of the normal property, such as the weak normal property and the uniform normal property, are also introduced. A dual form of the normal property is derived. When applied to closed convex cones, the dual normal property is the property (G) introduced by Jameson. Normality of convex sets provides a new perspective on the relationship between the strong conical hull intersection property (strong CHIP) and various regularity properties. In particular, we prove that the weak normal property is a dual characterization of the strong CHIP, and the uniform normal property is a characterization of the linear regularity. Moreover, the linear regularity is equivalent to the fact that the normality constant for feasible direction cones of the convex sets at is bounded away from 0 uniformly over all points in the intersection of these convex sets.

     

Metric regularity, tangential distances and generalized differentiation in Banach spaces

In this paper we establish new generalized differentiation rules in general Banach spaces regarding normal cones to set images under functions, coderivatives of compositions of set-valued mappings, as well as calculus results for normal compactness of sets and their images. In addition to the metric regularity of mappings, our results involve tangential distances of sets for which we also provide a fairly complete study by exploring its variations, basic properties, as well as relations to similar notions. Some related results are also established.     

Local linear convergence of approximate projections onto regularized sets

The numerical properties of algorithms for finding the intersection of sets depend to some extent on the regularity of the sets, but even more importantly on the regularity of the intersection. The alternating projection algorithm of von Neumann has been shown to converge locally at a linear rate dependent on the regularity modulus of the intersection. In many applications, however, the sets in question come from inexact measurements that are matched to idealized models. It is unlikely that any such problems in applications will enjoy metrically regular intersection, let alone set intersection. We explore a regularization strategy that generates an intersection with the desired regularity properties. The regularization, however, can lead to a significant increase in computational complexity. In a further refinement, we investigate and prove linear convergence of an approximate alternating projection algorithm. The analysis provides a regularization strategy that fits naturally with many ill-posed inverse problems, and a mathematically sound stopping criterion for extrapolated, approximate algorithms. The theory is demonstrated on the phase retrieval problem with experimental data. The conventional early termination applied in practice to unregularized, consistent problems in diffraction imaging can be justified fully in the framework of this analysis providing, for the first time, proof of convergence of alternating approximate projections for finite dimensional, consistent phase retrieval problems.     

Robust conjugate duality for convex optimization under uncertainty with application to data classification

In this paper we present a robust conjugate duality theory for convex programming problems in the face of data uncertainty within the framework of robust optimization, extending the powerful conjugate duality technique. We first establish robust strong duality between an uncertain primal parameterized convex programming model problem and its uncertain conjugate dual by proving strong duality between the deterministic robust counterpart of the primal model and the optimistic counterpart of its dual problem under a regularity condition. This regularity condition is not only sufficient for robust duality but also necessary for it whenever robust duality holds for every linear perturbation of the objective function of the primal model problem. More importantly, we show that robust strong duality always holds for partially finite convex programming problems under scenario data uncertainty and that the optimistic counterpart of the dual is a tractable finite dimensional problem. As an application, we also derive a robust conjugate duality theorem for support vector machines which are a class of important convex optimization models for classifying two labelled data sets. The support vector machine has emerged as a powerful modelling tool for machine learning problems of data classification that arise in many areas of application in information and computer sciences.     

Well-posed equilibrium problems

In this paper we introduce some notions of well-posedness for scalar equilibrium problems in complete metric spaces or in Banach spaces. As equilibrium problem is a common extension of optimization, saddle point and variational inequality problems, our definitions originates from the well-posedness concepts already introduced for these problems.We give sufficient conditions for two different kinds of well-posedness and show by means of counterexamples that these have no relationship in the general case. However, together with some additional assumptions, we show via Ekeland’s principle for bifunctions a link between them.Finally we discuss a parametric form of the equilibrium problem and introduce a well-posedness concept for it, which unifies the two different notions of well-posedness introduced in the first part.     

Optimality conditions for various efficient solutions involving coderivatives: From set-valued optimization problems to set-valued equilibrium problems

We present a new approach to the study of a set-valued equilibrium problem (for short, SEP) through the study of a set-valued optimization problem with a geometric constraint (for short, SOP) based on an equivalence between solutions of these problems. As illustrations, we adapt to SEP enhanced notions of relative Pareto efficient solutions introduced in set optimization by Bao and Mordukhovich and derive from known or new optimality conditions for various efficient solutions of SOP similar results for solutions of SEP as well as for solutions of a vector equilibrium problem and a vector variational inequality.We also introduce the concept of quasi weakly efficient solutions for the above problems and divide all efficient solutions under consideration into the Pareto-type group containing Pareto efficient, primary relative efficient, intrinsic relative efficient, quasi relative efficient solutions and the weak Pareto-type group containing quasi weakly efficient, weakly efficient, strongly efficient, positive properly efficient, Henig global properly efficient, Henig properly efficient, super efficient and Benson properly efficient solutions. The necessary conditions for Pareto-type efficient solutions and necessary/sufficient conditions for weak Pareto-type efficient solutions formulated here are expressed in terms of the Ioffe approximate coderivative and normal cone in the Banach space setting and in terms of the Mordukhovich coderivative and normal cone in the Asplund space setting.     

Generalized convex relations with applications to optimization and models of economic dynamics

We examine a notion of generalized convex set-valued mapping, extending the notions of a convex relation and a convex process. Under general conditions, we establish duality results for composite set-valued mappings and for convex programming problems involving convex set-valued mappings. We also present applications to the study of economic dynamical systems, by obtaining the characteristics of optimal paths generated by convex processes, and to optimization problems of a certain class of positively homogeneous increasing functions.     

Stability of the intersection of solution sets of semi-infinite systems

Many mathematical programming models arising in practice present a block structure in their constraint systems. Consequently, the feasibility of these problems depends on whether the intersection of the solution sets of each of those blocks is empty or not. The existence theorems allow to decide when the intersection of non-empty sets in the Euclidean space, which are the solution sets of systems of (possibly infinite) inequalities, is empty or not. In those situations where the data (i.e., the constraints) can be affected by some kind of perturbations, the problem consists of determining whether the relative position of the sets is preserved by sufficiently small perturbations or not. This paper focuses on the stability of the non-empty (empty) intersection of the solutions of some given systems, which can be seen as the images of set-valued mappings. We give sufficient conditions for the stability, and necessary ones as well; in particular we consider (semi-infinite) convex systems and also linear systems. In this last case we discuss the distance to ill-posedness.     

The Fermat rule for multifunctions for super efficiency

Using variational analysis, we study the vector optimization problems with objectives being closed multifunctions on Banach spaces or in Asplund spaces. In terms of the coderivatives and normal cones, we present Fermat’s rules as necessary or sufficient conditions for a super efficient solution of the above problems.     

Expressions for subdifferential and optimization problems defined by nonsmooth homogeneous functions

In this paper, we prove a theoretical expression for subdifferentials of lower semicontinuous and homogeneous functions. The theoretical expression is a generalization of the Euler formula for differentiable homogeneous functions. As applications of the generalized Euler formula, we consider constrained optimization problems defined by nonsmooth positively homogeneous functions in smooth Banach spaces. Some results concerning Karush–Kuhn–Tucker points and necessary optimality conditions for the optimization problems are obtained.     

Weak regularity of functions and sets in Asplund spaces

In this paper, we study a new concept of weak regularity of functions and sets in Asplund spaces. We show that this notion includes prox-regular functions, functions whose subdifferential is weakly submonotone and amenable functions in infinite dimension. We establish also that weak regularity is equivalent to Mordukhovich regularity in finite dimension. Finally, we give characterizations of the weak regularity of epi-Lipschitzian sets in terms of their local representations.     

Sensitivity in mixed generalized vector quasiequilibrium problems with moving cones

In this paper, we consider a parametric generalized vector quasiequilibrium problem which is mixed in the sense that several different relations can simultaneously appear in this problem. The moving cones and other data of the problem are assumed to be set-valued maps defined in topological spaces and taking values in topological spaces or topological vector spaces. The main result of this paper gives general verifiable conditions for the solution mapping of this problem to be semicontinuous with respect to a parameter varying in a topological space. The result is proven with the help of notions of cone-semicontinuity of set-valued maps, weaker than the usual concepts of semicontinuity, and an assumption imposed on the set-valued map whose values are the dual cones of the corresponding values of the moving cones.     

Four types of nonlinear scalarizations and some applications in set optimization

There are two types of criteria of solutions for the set-valued optimization problem, the vectorial criterion and set optimization criterion. The first criterion consists of looking for efficient points of set valued map and is called set-valued vector optimization problem. On the other hand, Kuroiwa–Tanaka–Ha started developing a new approach to set-valued optimization which is based on comparison among values of the set-valued map. In this paper, we treat the second type criterion and call set optimization problem. The aim of this paper is to investigate four types of nonlinear scalarizing functions for set valued maps and their relationships. These scalarizing functions are generalization of Tammer–Weidner’s scalarizing functions for vectors. As applications of the scalarizing functions for sets, we present nonconvex separation type theorems, Gordan’s type alternative theorems for set-valued map, optimality conditions for set optimization problem and Takahashi’s minimization theorems for set-valued map.     

Set Intersection Theorems and Existence of Optimal Solutions

The question of nonemptiness of the intersection of a nested sequence of closed sets is fundamental in a number of important optimization topics, including the existence of optimal solutions, the validity of the minimax inequality in zero sum games, and the absence of a duality gap in constrained optimization. We consider asymptotic directions of a sequence of closed sets, and introduce associated notions of retractive, horizon, and critical directions, based on which we provide new conditions that guarantee the nonemptiness of the corresponding intersection. We show how these conditions can be used to obtain simple and unified proofs of some known results on existence of optimal solutions, and to derive some new results, including a new extension of the Frank–Wolfe Theorem for (nonconvex) quadratic programming.     

Metric subregularity for proximal generalized equations in Hilbert spaces

In this paper, we introduce and consider the concept of the prox-regularity of a multifunction. We mainly study the metric subregularity of a generalized equation defined by a proximal closed multifunction between two Hilbert spaces. Using proximal analysis techniques, we provide sufficient and/or necessary conditions for such a generalized equation to have the metric subregularity in Hilbert spaces. We also establish the results of Robinson-Ursescu theorem type for prox-regular multifunctions.     

Regularity properties of optimal controls for problems with time-varying state and control constraints

In this paper we report new results on the regularity of optimal controls for dynamic optimization problems with functional inequality state constraints, a convex time-dependent control constraint and a coercive cost function. Recently, it has been shown that the linear independence condition on active state constraints, present in the earlier literature, can be replaced by a less restrictive, positive linear independence condition, that requires linear independence merely with respect to non-negative weighting parameters, provided the control constraint set is independent of the time variable. We show that, if the control constraint set, regarded as a time-dependent multifunction, is merely Lipschitz continuous with respect to the time variable, then optimal controls can fail to be Lipschitz continuous. In these circumstances, however, a weaker Hölder continuity-like regularity property can be established. On the other hand, Lipschitz continuity of optimal controls is guaranteed for time-varying control sets under a positive linear independence hypothesis, when the control constraint sets are described, at each time, by a finite collection of functional inequalities.