Duality for optimization and best approximation over finite intersections

Recently Deutsch, Li and Swetits [2] have studied, in Hilbert space, a dual problem (Q_m ) to the primal problem (P) of minimization of a special class of convex functions f over the intersection of m closed convex sets, where m is finite. In the first part of this paper we obtain, in a locally convex space, some results on problem (Q_m ) and on its relations with the usual Lagrangian dual problem (Q) to (P) (studied in [9]), in the case when (P) has a solution. In the second part we give some applications to duality for the distance to the intersection of m closed convex sets in a normed linear space, in the case when a nearest point exists. Most of our results seem to be new even in the particular cases studied in [9] (the case m = 1), [l] (duality formulas for the distance to the intersection of m closed half-spaces in a normed linear space) and [2].     

Geometric Condition Measures and Smoothness Condition Measures for Closed Convex Sets and Linear Regularity of Infinitely Many Closed Convex Sets

In this paper, we study geometric condition measures and smoothness condition measures of closed convex sets, bounded linear regularity, and linear regularity. We show that, under certain conditions, the constant for the linear regularity of infinitely many closed convex sets can be characterized by the geometric condition measure of the intersection or by the smoothness condition measure of the intersection. We study also the bounded linear regularity and present some interesting properties of the general linear regularity problem.The author is grateful to the referees for valuable and constructive suggestions. In particular, she thanks a referee for drawing her attention to Corollary 5.14 of Ref. 3, which inspired her to derive Theorem 4.2 and Corollary 4.2 in the revision of this paper.     

Strong Minkowski Separation and Co-Drop Property

In the framework of topological vector spaces, we give a characterization of strong Minkowski separation, introduced by Cheng, et al., in terms of convex body separation. From this, several results on strong Minkowski separation are deduced. Using the results, we prove a drop theorem involving weakly countably compact sets in locally convex spaces. Moreover, we introduce the notion of the co-drop property and show that every weakly countably compact set has the co-drop property. If the underlying locally convex space is quasi-complete, then a bounded weakly closed set has the co-drop property if and only if it is weakly countably compact.     

非可微凸规划的对偶问题

文章建立关于非可微凸规划的一个新的对偶问题,它不同于已知的对偶问题,文中证明了弱对偶性及强对偶性。并用Ｌａｇｒａｎｇｅ正则性证明了强对偶性的充要条件。最后,讨论了等式约束的情况。     

Generic Banach spaces and generic simplexes

We give a systematic study of certain class of generic Banach spaces. We show that they distinguish between an array of different properties related to smoothness of equivalent norms such as for example the Mazur intersection property or the existence of convex sets supported by all of their points. We also examine the dual constructions of generic Choquet simplexes with extra requirements such as for example those of Poulsen and Bauer asking that the set of extremal points is dense or closed, respectively.     

The strong conical hull intersection property for convex programming

The strong conical hull intersection property (CHIP) is a geometric property of a collection of finitely many closed convex intersecting sets. This basic property, which was introduced by Deutsch et al. in 1997, is one of the central ingredients in the study of constrained interpolation and best approximation. In this paper we establish that the strong CHIP of intersecting sets of constraints is the key characterizing property for optimality and strong duality of convex programming problems. We first show that a sharpened strong CHIP is necessary and sufficient for a complete Lagrange multiplier characterization of optimality for the convex programming model problem where C is a closed convex subset of a Banach space X, S is a closed convex cone which does not necessarily have non-empty interior, Y is a Banach space, is a continuous convex function and g:X→Y is a continuous S-convex function. We also show that the strong CHIP completely characterizes the strong duality for partially finite convex programs, where Y is finite dimensional and g(x)=−Ax+b and S is a polyhedral convex cone. Global sufficient conditions which are strictly weaker than the Slater type conditions are given for the strong CHIP and for the sharpened strong CHIP. The author is grateful to the referees for their constructive comments and valuable suggestions which have contributed to the final preparation of the paper.     

Fenchel Duality and the Strong Conical Hull Intersection Property

We study a special dual form of a convex minimization problem in a Hilbert space, which is formally suggested by Fenchel dualityand is useful for the Dykstra algorithm. For this special duality problem, we prove that strong duality holds if and only if the collection of underlying constraint sets {C ₁,...,C _m} has the strong conical hull intersection property. That is,

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     

A simple closure condition for the normal cone intersection formula

In this paper it is shown that if and are two closed convex subsets of a Banach space and , then whenever the convex cone, , is weak* closed, where and are the support function and the normal cone of the set respectively. This closure condition is shown to be weaker than the standard interior-point-like conditions and the bounded linear regularity condition.

     

The rate of convergence for the cyclic projections algorithm III: Regularity of convex sets

The cyclic projections algorithm is an important method for determining a point in the intersection of a finite number of closed convex sets in a Hilbert space. That is, for determining a solution to the “convex feasibility” problem. This is the third paper in a series on a study of the rate of convergence for the cyclic projections algorithm. In the first of these papers, we showed that the rate could be described in terms of the “angles” between the convex sets involved. In the second, we showed that these angles often had a more tractable formulation in terms of the “norm” of the product of the (nonlinear) metric projections onto related convex sets.In this paper, we show that the rate of convergence of the cyclic projections algorithm is also intimately related to the “linear regularity property” of Bauschke and Borwein, the “normal property” of Jameson (as well as Bakan, Deutsch, and Li’s generalization of Jameson’s normal property), the “strong conical hull intersection property” of Deutsch, Li, and Ward, and the rate of convergence of iterated parallel projections. Such properties have already been shown to be important in various other contexts as well.     

Regularities and their relations to error bounds

In this paper, we mainly study various notions of regularity for a finite collection {C₁,,C_m} of closed convex subsets of a Banach space X and their relations with other fundamental concepts. We show that a proper lower semicontinuous function f on X has a Lipschitz error bound (resp., -error bound) if and only if the pair {epi(f),X×{0}} of sets in the product space X× is linearly regular (resp., regular). Similar results for multifunctions are also established. Next, we prove that {C₁,,C_m} is linearly regular if and only if it has the strong CHIP and the collection {N_C1(z),,N_Cm(z)} of normal cones at z has property (G) for each zC:=_i=1^mC_i. Provided that C₁ is a closed convex cone and that C₂=Y is a closed vector subspace of X, we show that {C₁,Y} is linearly regular if and only if there exists >0 such that each positive (relative to the order induced by C₁) linear functional on Y of norm one can be extended to a positive linear functional on X with norm bounded by . Similar characterization is given in terms of normal cones.Mathematics Subject Classifications: 90C25, 90C31, 49J52, 46A40This research was supported by an Earmarked grant from the Research Grant Council of Hong Kong     

Subdifferential set of the supremum of lower semi-continuous convex functions and the conical hull intersection property

In this paper we give some characterizations for the subdifferential set of the supremum of an arbitrary (possibly infinite) family of proper lower semi-continuous convex functions. This is achieved by means of formulae depending exclusively on the (exact) subdifferential sets and the normal cones to the domains of the involved functions. Our approach makes use of the concept of conical hull intersection property (CHIP, for short). It allows us to establish sufficient conditions guarantying explicit representations for this subdifferential set at any point of the effective domain of the supremum function. Research supported by grant SB2003-0344 of SEUI (MEC), Spain.     

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     

Best Approximation and Perturbation Property in Hilbert Spaces

We study the perturbation property of best approximation to a set defined by an abstract nonlinear constraint system. We show that, at a normal point, the perturbation property of best approximation is equivalent to an equality expressed in terms of normal cones. This equality is related to the strong conical hull intersection property. Our results generalize many known results in the literature on perturbation property of best approximation established for a set defined by a finite system of linear/nonlinear inequalities. The connection to minimization problem is considered.The authors thank the referees for valuable suggestions.K.F. Ng - This author was partially supported by Grant A0324638 from the National Natural Science Foundation of China and Grants (2001) 01GY051-66 and SZD0406 from Sichuan Province. Y.R. He -This author was supported by a Direct Grant (CUHK) and an Earmarked Grant from the Research Grant Council of Hong Kong.     

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.     

The Sweeping Processes without Convexity

We study the sweeping processes in a Hilbert space which are generated by a closed not necessarily convex moving set. A technique is developed, based on measurability properties of normal cones, in order to prove existence of solutions. Some existence results are proved, with or without hypothesis of compactness; moreover, under suitable assumptions, uniqueness and regularity properties are established. In particular, the well-known results of Moreau are extended to a class of not necessarily convex (called -convex) sets.     

Uniform subsmoothness and linear regularity for a collection of infinitely many closed sets

Motivated by the subsmoothness of a closed set introduced by Aussel et al. (2005) [8], we introduce and study the uniform subsmoothness of a collection of infinitely many closed subsets in a Banach space. Under the uniform subsmoothness assumption, we provide an interesting subdifferential formula on distance functions and consider uniform metric regularity for a kind of multifunctions frequently appearing in optimization and variational analysis. Different from the existing works, without the restriction of convexity, we consider several fundamental notions in optimization such as the linear regularity, CHIP, strong CHIP and property (G) for a collection of infinitely many closed sets. We establish relationships among these fundamental notions for an arbitrary collection of uniformly subsmooth closed sets. In particular, we extend duality characterizations of the linear regularity for a collection of closed convex sets to the nonconvex setting.     

Limiting -subgradient characterizations of constrained best approximation

In this paper, we show that the strong conical hull intersection property (CHIP) completely characterizes the best approximation to any x in a Hilbert space X from the set

K:=C∩{xX:-g(x)S},