Weakly Convex Sets and Their Properties

In this paper, the notion of a weakly convex set is introduced. Sharp estimates for the weak convexity constants of the sum and difference of such sets are given. It is proved that, in Hilbert space, the smoothness of a set is equivalent to the weak convexity of the set and its complement. Here, by definition, the smoothness of a set means that the field of unit outward normal vectors is defined on the boundary of the set; this vector field satisfies the Lipschitz condition. We obtain the minimax theorem for a class of problems with smooth Lebesgue sets of the goal function and strongly convex constraints. As an application of the results obtained, we prove the alternative theorem for program strategies in a linear differential quality game.     

广义凸函数相关集合的稠密性问题

应用新方法,研究十二类广义凸函数相关集合的稠密性问题.证明了其中的八个集合在[0,1]中是稠密的.应用反例说明了其中的四个集合在[0,1]中不必稠密.     

Subgradient Methods for Sharp Weakly Convex Functions

Subgradient methods converge linearly on a convex function that grows sharply away from its solution set. In this work, we show that the same is true for sharp functions that are only weakly convex, provided that the subgradient methods are initialized within a fixed tube around the solution set. A variety of statistical and signal processing tasks come equipped with good initialization and provably lead to formulations that are both weakly convex and sharp. Therefore, in such settings, subgradient methods can serve as inexpensive local search procedures. We illustrate the proposed techniques on phase retrieval and covariance estimation problems.     

On Well-Posedness and Hausdorff Convergence of Solution Sets of Vector Optimization Problems

In this paper, we refine and improve the results established in a 2003 paper by Deng in a number of directions. Specifically, we establish a well-posedness result for convex vector optimization problems under a condition which is weaker than that used in the paper. Among other things, we also obtain a characterization of well-posedness in terms of Hausdorff distance of associated sets.     

中点凸性与广义凸函数相关集合的对称性问题

研究十二类广义凸函数相关集合的对称性问题及其对应函数的中点凸性问题.证明了其中的十个集合具有对称性,应用反例说明了余下的两个集合不必具有对称性.证明了六个集合对应的函数具有中点凸性,应用反例说明了余下六个集合对应的函数不必具有中点凸性.     

Well-positioned Closed Convex Sets and Well-positioned Closed Convex Functions

We characterize the class of those closed convex sets which have a barrier cone with a nonempty interior. As a consequence, we describe the set of those proper extended-real-valued functionals for which the domain of their Fenchel conjugate has a nonempty interior. As an application, we study the stability of the solution set of a semi-coercive variational inequality.     

Dominating Sets for Convex Functions with Some Applications

A number of optimization methods require as a first step the construction of a dominating set (a set containing an optimal solution) enjoying properties such as compactness or convexity. In this paper, we address the problem of constructing dominating sets for problems whose objective is a componentwise nondecreasing function of (possibly an infinite number of) convex functions, and we show how to obtain a convex dominating set in terms of dominating sets of simpler problems. The applicability of the results obtained is illustrated with the statement of new localization results in the fields of linear regression and location.     

Approximation of Planar Convex Sets from Hyperplane Probes

This paper studies a geometric probing problem. Suppose that an unknown convex set in R ² can be probed by an oracle which, when given a unit vector, will return the position of the supporting hyperplane of the convex set that has the given vector as an outward normal. We present an on-line algorithm for choosing probing directions so that, after n probes, an inner and an outer estimate of the convex set are obtained that are within of each other in Hausdorff distance. This is optimal since there exist convex sets that, even if visible, cannot be approximated better than with n-sided polygons, for example, a circle. Received April 18, 1995, and in revised form March 28, 1996.     

On a Class of Convex Sets and Functions

Given a convex subset C of ⁿ, the set-valued mapping C (where 0C is, by convention, the recession cone of C) is increasing on ₊ if and only if C contains the origin, and decreasing on ₊ if and only if C is contained in its recession cone. This simple fact enables us to define a binary operation which combines a concave or convex function on ^m with a convex subset of ⁿ to produce a convex subset of ^n+m. This binary operation is the set theoretic counterpart of a functional operation introduced by the author. In this paper, we present a detailed study of the class of convex subsets which are contained in their recession cones, and we establish some remarkable properties of our binary operation.Mathematics Subject Classifications (2000) 26A51, 26B25, 26E25.     

对偶空间上凸函数的逼近

设Banach空间E具有等价二次严格凸范数, f为其对偶空间E^*上的w^*下半连续Lipschitz凸函数, 该文证明了E^*上存在w^*下半连续且很光滑点集稠密(从而在稠子集上Gateaux可微)的Lipschitz 凸函数的单调序列{f_n}在有界集上一致逼近f.     

Approximation to Probabilities Through Uniform Laws on Convex Sets

Let P be a probability distribution on ^d and let be the family of the uniform probabilities defined on compact convex sets of ^d with interior non-empty. We prove that there exists a best approximation to P in , based on the L ₂-Wasserstein distance. The approximation can be considered as the best representation of P by a convex set in the minimum squares setting, improving on other existent representations for the shape of a distribution. As a by-product we obtain properties related to the limit behavior and marginals of uniform distributions on convex sets which can be of independent interest.     

Integer Optimization on Convex Semialgebraic Sets

Let Y be a convex set in Re ^k defined by polynomial inequalities and equations of degree at most d ≥ 2 with integer coefficients of binary length at most l . We show that if the set of optimal solutions of the integer programming problem min is not empty, then the problem has an optimal solution of binary length ld ^O(k4) . For fixed k , our bound implies a polynomial-time algorithm for computing an optimal integral solution y ^* . In particular, we extend Lenstra's theorem on the polynomial-time solvability of linear integer programming in fixed dimension to semidefinite integer programming. Received August 3, 1998, and in revised form March 22, 1999.     

Best Approximation on Convex Sets in Metric Linear Spaces

In this paper the concepts of strictly convex and uniformly convex normed linear spaces are extended to metric linear spaces. A relationship between strict convexity and uniform convexity is established. Some existence and uniqueness theorems on best approximation in metric linear spaces under different conditions are proved.     

Extended Well-Posedness of Quasiconvex Vector Optimization Problems

The notion of extended-well-posedness has been introduced by Zolezzi for scalar minimization problems and has been further generalized to vector minimization problems by Huang. In this paper, we study the extended well-posedness properties of vector minimization problems in which the objective function is C-quasiconvex. To achieve this task, we first study some stability properties of such problems. Research partially supported by the Cariplo Foundation, Grant 2006.1601/11.0556, Cattaneo University, Castellanza, Italy.     

Extended Well-Posedness Properties of Vector Optimization Problems

In this paper, the concept of extended well-posedness of scalar optimization problems introduced by Zolezzi is generalized to vector optimization problems in three ways: weakly extended well-posedness, extended well-posedness, and strongly extended well-posedness. Criteria and characterizations of the three types of extended well-posedness are established, generalizing most of the results obtained by Zolezzi for scalar optimization problems. Finally, a stronger vector variational principle and Palais-Smale type conditions are used to derive sufficient conditions for the three types of extended well-posedness.     

Proximal Methods Avoid Active Strict Saddles of Weakly Convex Functions

Foundations of Computational Mathematics - We introduce a geometrically transparent strict saddle property for nonsmooth functions. This property guarantees that simple proximal algorithms on...     

Asymptotic Analysis of Sample Average Approximation for Stochastic Optimization Problems with Joint Chance Constraints via Conditional Value at Risk and Difference of Convex Functions

Conditional Value at Risk (CVaR) has been recently used to approximate a chance constraint. In this paper, we study the convergence of stationary points, when sample average approximation (SAA) method is applied to a CVaR approximated joint chance constrained stochastic minimization problem. Specifically, we prove under some moderate conditions that optimal solutions and stationary points, obtained from solving sample average approximated problems, converge with probability one to their true counterparts. Moreover, by exploiting the recent results on large deviation of random functions and sensitivity results for generalized equations, we derive exponential rate of convergence of stationary points. The discussion is also extended to the case, when CVaR approximation is replaced by a difference of two convex functions (DC-approximation). Some preliminary numerical test results are reported.     

The Equivalence of Three Types of Error Bounds for Weakly and Approximately Convex Functions

Journal of Optimization Theory and Applications - We start by establishing the equivalence of three types of error bounds: weak sharp minima, level-set subdifferential error bounds and...