Cone superadditivity of discrete convex functions

A function f is said to be cone superadditive if there exists a partition of R ⁿ into a family of polyhedral convex cones such that f(z?+?x) + f(z?+?y) ≤ f(z) + f(z?+?x?+?y) holds whenever x and y belong to the same cone in the family. This concept is useful in nonlinear integer programming in that, if the objective function is cone superadditive, the global minimality can be characterized by local optimality criterion involving Hilbert bases. This paper shows cone superadditivity of L-convex and M-convex functions with respect to conic partitions that are independent of particular functions. L-convex and M-convex functions in discrete variables (integer vectors) as well as in continuous variables (real vectors) are considered.     

Proximity theorems of discrete convex functions

A proximity theorem is a statement that, given an optimization problem and its relaxation, an optimal solution to the original problem exists in a certain neighborhood of a solution to the relaxation. Proximity theorems have been used successfully, for example, in designing efficient algorithms for discrete resource allocation problems. After reviewing the recent results for L-convex and M-convex functions, this paper establishes proximity theorems for larger classes of discrete convex functions, L₂-convex functions and M₂-convex functions, that are relevant to the polymatroid intersection problem and the submodular flow problem.Mathematics Subject Classification (2000): 90C27, 05B35     

On order-preserving and order-reversing mappings defined on cones of convex functions

In this paper,we first show that for a Banach space X,there is a fully order-reversing mapping T from conv(X)(the cone of all the extended real-valued lower semicontinuous proper convex functions defined on X) onto itself if and only if X is reflexive and linearly isomorphic to its dual X~*.Then we further prove the following generalized Artstein-Avidan-Milman representation theorem:For every fully order-reversing mapping T:conv(X)→conv(X),there exist a linear isomorphism U:X→X~*,x_0~*,φ_0∈X~*,α0 and r_0∈R so that(Tf)(x)=α(Ff)(Ux+x_0~*)+φ_0,x+r_0,■x∈X where T:conv(X)→conv(X~*) is the Fenchel transform.Hence,these resolve two open questions.We also show several representation theorems of fully order-preserving mappings defined on certain cones of convex functions.For example,for every fully order-preserving mapping S:semn(X)→ semn(X),there is a linear isomorphism U:X→ X so that(Sf)(x)=f(Ux),■f∈semn(X),x∈X where semn(X) is the cone of all the lower semicontinuous seminorms on X.     

Nondegenerate families of convex cones and convex polytopes

This paper describes relations between convex polytopes and certain families of convex cones in R ⁿ .The purpose is to use known properties of convex cones in order to solve Helly type problems for convex sets in R ⁿ or for spherically convex sets in S _n , the n-dimensional unit sphere. These results are strongly related to Gale diagrams.     

Bifractional inequalities and convex cones

In this paper we give a systematic study of a class of linear inequalities related to convex cones in linear spaces. In particular, Chebyshev and Andersson type inequalities are discussed. Some classical and new inequalities are derived from the results.     

Isotone functions,dual cones,and networks

If the collection of all real-valued functions defined on a finite partially ordered set S of n elements is identified in the natural way with Rⁿ, it is obvious that the subset of functions that are isotone or order preserving with respect to the given partial order constitutes a closed, convex, polyhedral cone K in Rⁿ. The dual cone K^* of K is the set of all linear functionals that are nonpositive of K. This article identifies the important geometric properties of K, and characterizes a nonredundant set of defining equations and inequalities for K^* in terms of a special class of partitions of S into upper and lower sets. These defining constraints immediately imply a set of extreme rays spanning K and K^*. One of the characterizations of K^* involves feasibility conditions on flows in a network. These conditions are also used as a tool in analysis.     

Bases of convex cones and Borwein's proper efficiency

In this note, we establish some interesting relationships between the existence of Borwein's proper efficient points and the existence of bases for convex ordering cones in normed linear spaces. We show that, if the closed unit ball in a smooth normed space ordered by a convex cone possesses a proper efficient point in the sense of Borwein, then the ordering cone is based. In particular, a convex ordering cone in a reflexive space is based if the closed unit ball possesses a proper efficient point. Conversely, we show that, in any ordered normed space, if the ordering cone has a base, then every weakly compact set possesses a proper efficient point.The research was conducted while the author was working on his PhD Degree under the supervision of Professor J. M. Borwein, whose guidance and valuable suggestions are gratefully appreciated. The author would like to thank two anonymous referees for their constructive comments and suggestions. This research was supported by an NSERC grant and a Mount Saint Vincent University Research Grant.     

An infinite class of convex tangent cones

Since the early 1970's, there have been many papers devoted to tangent cones and their applications to optimization. Much of the debate over which tangent cone is best has centered on the properties of Clarke's tangent cone and whether other cones have these properties. In this paper, it is shown that there are an infinite number of tangent cones with some of the nicest properties of Clarke's cone. These properties are convexity, multiple characterizations, and proximal normal formulas. The nature of these cones indicates that the two extremes of this family of cones, the cone of Clarke and the B-tangent cone or the cone of Michel and Penot, warrant further study. The relationship between these new cones and the differentiability of functions is also considered.     

Geometry of homogeneous convex cones,duality mapping,and optimal self-concordant barriers

We study homogeneous convex cones. We first characterize the extreme rays of such cones in the context of their primal construction (due to Vinberg) and also in the context of their dual construction (due to Rothaus). Then, using these results, we prove that every homogeneous cone is facially exposed. We provide an alternative proof of a result of Güler and Tunç el that the Siegel rank of a symmetric cone is equal to its Carathéodory number. Our proof does not use the Jordan-von Neumann-Wigner characterization of the symmetric cones but it easily follows from the primal construction of the homogeneous cones and our results on the geometry of homogeneous cones in primal and dual forms. We study optimal self-concordant barriers in this context. We briefly discuss the duality mapping in the context of automorphisms of convex cones and prove, using numerical integration, that the duality mapping is not an involution on certain self-dual cones.Research of this author was supported in part by a Summer Undergraduate Research Assistantship Award from NSERC (Summer 2001) and a research grant from NSERC while she was an undergraduate student at Faculty of Mathematics, University of Waterloo.Research of this author was supported in part by a PREA from Ontario, Canada and research grants from NSERC. Corresponding author.Mathematics Subject Classification (2000): 90C25, 90C51, 90C60, 90C05, 65Y20, 52A41, 49M37, 90C30     

Projective and inductive limits in locally convex cones

We define and study the projective and inductive limit notions for locally convex cones. We use convex quasiuniform structure method for this purpose. Also we study the barreledness in the locally convex cones and introduce the notion upper-barreled cones and prove that the inductive limit of upper-barreled cones is upper-barreled.     

Convex bodies and convexity on grassmann cones (X): Projection functions of parallel convex bodies

Summary It is shown that if K is a convex polyhedron or a smooth convex body, then for sufficiently large positive ρ, the body parallel to K at distance ρ has convex projection functions. An example is given of a convex body which does not have this property. In memory of Guido Castelnuovo, in the recurrence of the first centenary of his birth. Supported by a grant from the National Science Foundation, U.S.A.