Weakly convex sets and modulus of nonconvexity

We consider a definition of a weakly convex set which is a generalization of the notion of a weakly convex set in the sense of Vial and a proximally smooth set in the sense of Clarke, from the case of the Hilbert space to a class of Banach spaces with the modulus of convexity of the second order. Using the new definition of the weakly convex set with the given modulus of nonconvexity we prove a new retraction theorem and we obtain new results about continuity of the intersection of two continuous set-valued mappings (one of which has nonconvex images) and new affirmative solutions of the splitting problem for selections. We also investigate relationship between the new definition and the definition of a proximally smooth set and a smooth set.     

Empty convex polygons in almost convex sets

A finite set of points, in general position in the plane, is almost convex if every triple determines a triangle with at most one point in its interior. For every ℓ ≥ 3, we determine the maximum size of an almost convex set that does not contain the vertex set of an empty convex ℓ-gon. Partially supported by grants T043631 and NK67867 of the Hungarian NFSR (OTKA).     

Extensions of convex and semiconvex functions and intervally thin sets

We call A⊂RNintervally thin if for all x,y∈RN and ε>0 there exist x^′∈B(x,ε), y^′∈B(y,ε) such that [x^′,y^′]∩A=∅. Closed intervally thin sets behave like sets with measure zero (for example such a set cannot “disconnect” an open connected set). Let us also mention that if the (N−1)-dimensional Hausdorff measure of A is zero, then A is intervally thin. A function f is preconvex if it is convex on every convex subset of its domain. The consequence of our main theorem is the following: Let U be an open subset ofRNand let A be a closed intervally thin subset of U. Then every preconvex functioncan be uniquely extended (with preservation of preconvexity) onto U. In fact we show that a more general version of this result holds for semiconvex functions.     

A new algorithm for minimizing convex functions over convex sets

Let be a convex set for which there is an oracle with the following property. Given any pointz∈ℝ ⁿ the oracle returns a “Yes” ifz∈S; whereas ifz∉S then the oracle returns a “No” together with a hyperplane that separatesz fromS. The feasibility problem is the problem of finding a point inS; the convex optimization problem is the problem of minimizing a convex function overS. We present a new algorithm for the feasibility problem. The notion of a volumetric center of a polytope and a related ellipsoid of maximum volume inscribable in the polytope are central to the algorithm. Our algorithm has a significantly better global convergence rate and time complexity than the ellipsoid algorithm. The algorithm for the feasibility problem easily adapts to the convex optimization problem.     

Optimization of expected shortfall on convex sets

In this article, we prove that the minimization problem of the expected shortfall over a convex but not necessarily closed set of financial positions $ \mathcal{X}\subseteq {L^1} $ has a solution. We provide both minimax and variational approaches on this problem. In the case where the optimization conclusions arise from the application of subgradient arguments, we need the assumption that the set of financial positions $ \mathcal{X} $ is closed.     

Optimization of convex functions on w*-compact sets

We give a direct, self-contained, and iterative proof that for any convex, Lipschitz andw ^*-lower semicontinuous function ϕ defined on aw ^*-compact convex setC in a dual Banach spaceX ^* and for any ε>0 there is anx∈X, with ‖x‖≤ε, such that ϕ+x attains its supremum at an extreme point ofC. This result is implicitly contained in the work of Lindenstrauss [9] and the work of Ghoussoub and Maurey on strongw ^*−H _σ sets [8]. In addition, we discuss the applications of this result to the geometry of convex sets. Research supported in part by the NSERC of Canada under grant OGP41983 for the first author and grant OGP7926 for the second author.     

Strongly hyperbolically convex functions

Let C(w₁,w₂,w₃) denote the circle in through w₁,w₂,w₃ and let denote one of the two arcs between w₁,w₂ belonging to C(w₁,w₂,w₃). We prove that a domain Ω in the Riemann sphere, with no antipodal points, is spherically convex if and only if for any w₁,w₂,w₃∈Ω, with w₁≠w₂, the arc of the circle which does not contain lies in Ω. Based on this characterization we call a domain G in the unit disk D, strongly hyperbolically convex if for any w₁,w₂,w₃∈G, with w₁≠w₂, the arc in D of the circle is also contained in G. A number of results on conformal maps onto strongly hyperbolically convex domains are obtained.     

二元凸函数的判别条件

给出了二元凸函数的定义,导出了二元凸函数的判别条件,该判别条件由二元函数的二阶导数给出.用二元凸函数的判别条件和半正定的(半负定)矩阵的性质,得到了二元二次多项式凸性的简单判别形式.     

Polyhedral approximations of strictly convex compacta

We consider polyhedral approximations of strictly convex compacta in finite-dimensional Euclidean spaces (such compacta are also uniformly convex). We obtain the best possible estimates for errors of considered approximations in the Hausdorff metric. We also obtain new estimates of an approximate algorithm for finding the convex hulls.     

Note on generalized convex functions

In this note, an important class of generalized convex functions, called invex functions, is defined under a general framework, and some properties of the functions in this class are derived. It is also shown that a function is (generalized) pseudoconvex if and only if it is quasiconvex and invex.     

A method for globally minimizing concave functions over convex sets

A method is described for globally minimizing concave functions over convex sets whose defining constraints may be nonlinear. The algorithm generates linear programs whose solutions minimize the convex envelope of the original function over successively tighter polytopes enclosing the feasible region. The algorithm does not involve cuts of the feasible region, requires only simplex pivot operations and univariate search computations to be performed, allows the objective function to be lower semicontinuous and nonseparable, and is guaranteed to converge to the global solution. Computational aspects of the algorithm are discussed.     

On uniformly convex functions

Non-convex functions that yet satisfy a condition of uniform convexity for non-close points can arise in discrete constructions. We prove that this sort of discrete uniform convexity is inherited by the convex envelope, which is the key to obtain other remarkable properties such as the coercivity. Our techniques allow to retrieve Enflo's uniformly convex renorming of super-reflexive Banach spaces as the regularization of a raw function built from trees. Among other applications, we provide a sharp estimation of the distance of a given function to the set of differences of Lipschitz convex functions. Finally, we prove the equivalence of several possible ways to quantify the super weakly noncompactness of a convex subset of a Banach space.     

Continuous valuations on convex sets

((Without abstract)) Submitted: December 1997     

Some notes on convex sets

In [1] Tukey proves that if A and B are closed convex subsets in a Banach space, so that A is bounded and A-B is dense in the open unit ball U then A-BU. We shall give here a more general result than the former one which contains the Banach's isomorphism theorem as particular case. Other results over convex sets are also given.The author is indebted to the referee for the several very valuable comments.     

Extremal convex sets

Letf be an extended real valued function on the classK ⁿ of closed convex subsets of euclideann-dimensional space. A setK∈K ⁿ is said to bef-maximal if the conditionsK′∈K ⁿ ,K?K′,K≠K′ implyf(K)<f(K′), andf-minimal ifK′∈K ⁿ,K′∈K,K′≠K impliesf(K′)<f(K). In the cases whenf is the circumradius or inradius allf-maximal andf-minimal sets are determined. Under a certain regularity assumption a corresponding result is obtained for the minimal width. Moreover, a general existence theorem is established and a result concerning the existence of extremal sets with respect to packing and covering densities is proved.     

Protecting convex sets

A point-setS is protecting a collection F =T ₁,T ₂,..., _n ofn mutually disjoint compact sets if each one of the setsT _i is visible from at least one point inS; thus, for every setT _i ∈F there are points xS andy T _i such that the line segment joining x to y does not intersect any element inF other thanT _i . In this paper we prove that [2(n-2)/3] points are always sufficient and occasionally necessary to protect any family F ofn mutually disjoint compact convex sets. For an isothetic family F, consisting ofn mutually disjoint rectangles, [n/2] points are always sufficient and [n/2] points are sometimes necessary to protect it. IfF is a family of triangles, [4n/7] points are always sufficient. To protect families ofn homothetic triangles, [n/2] points are always sufficient and [n/2] points are sometimes necessary.     

Almost convex sets

The concept of a wedgoid, a generalized wedge, is introduced and studied. Almost all convex sets are characterized by the fact that balls can be separated from such a set by means of wedgoids.