Discrete Convexity

In the paper, we explain what subsets of the lattice ℤ ⁿ and what functions on the lattice ℤ ⁿ could be called convex. The basis of our theory is the following three main postulates of classical convex analysis: concave functions are closed under sums; they are also closed under convolutions; and the superdifferential of a concave function is nonempty at each point of the domain. Interesting (and even dual) classes of discrete concave functions arise if we require either the existence of superdifferentials and closeness under convolutions or the existence of superdifferentials and closeness under sums. The corresponding classes of convex sets are obtained as the affinity domains of such discretely concave functions. The classes of the first type are closed under (Minkowski) sums, and the classes of the second type are closed under intersections. In both classes, the separation theorem holds true. Unimodular sets play an important role in the classification of such classes. The so-called polymatroidal discretely concave functions, most interesting for applications, are related to the unimodular system . Such functions naturally appear in mathematical economics, in Gelfand-Tzetlin patterns, play an important role for solution of the Horn problem, for describing submodule invariants over discrete valuation rings, and so on. Bibliography: 6 titles. __________ Translated from Zapiski Nauchnykh Seminarov POMI, Vol. 312, 2004, pp. 86–93.     

Convexity in oriented matroids

We generalize to oriented matroids classical notions of Convexity Theory: faces of convex polytopes, convex hull, etc., and prove some basic properties. We relate the number of acyclic orientations of an orientable matroid to an evaluation of its Tutte polynomial.     

Partial Convexity

We study OC-convexity, which is defined by the intersection of conic semispaces of partial convexity. We investigate an optimization problem for OC-convex sets and prove a Krein--Milman type theorem for OC-convexity. The relationship between OC-convex and functionally convex sets is studied. Topological and numerical aspects, as well as separability properties are described. An upper estimate for the Carathéodory number for OC-convexity is found. On the other hand, it happens that the Helly and the Radon number for OC-convexity are infinite. We prove that the OC-convex hull of any finite set of points is the union of finitely many polyhedra.     

Convexity in directed graphs

In this paper the concept of convexity in directed graphs is described. It is shown that the set of convex subgraphs of a directed graph G partially ordered by inclusion forms a complete, semimodular, A-regular lattice, denoted ?_G. The lattice theoretic properties of the convex subgraph lattice lead to inferences about the path structure of the original graph G. In particular, a graph factorization theorem is developed. In Section 4, several graph homomorphism concepts are investigated in relation to the preservation of convexity properties. Finally we characterize an interesting class of locally convex directed graphs.     

Convexity in oriented graphs

For vertices u and v in an oriented graph D, the closed interval I[u,v] consists of u and v together with all vertices lying in a u−v geodesic or v−u geodesic in D. For S⊆V(D), I[S] is the union of all closed intervals I[u,v] with u,v∈S. A set S is convex if I[S]=S. The convexity number con(D) is the maximum cardinality of a proper convex set of V(D). The nontrivial connected oriented graphs of order n with convexity number n−1 are characterized. It is shown that there is no connected oriented graph of order at least 4 with convexity number 2 and that every pair k, n of integers with 1⩽k⩽n−1 and k≠2 is realizable as the convexity number and order, respectively, of some connected oriented graph. For a nontrivial connected graph G, the lower orientable convexity number con⁻(G) is the minimum convexity number among all orientations of G and the upper orientable convexity number con⁺(G) is the maximum such convexity number. It is shown that con⁺(G)=n−1 for every graph G of order n⩾2. The lower orientable convexity numbers of some well-known graphs are determined, with special attention given to outerplanar graphs.     

Convexity in Scheduling Problems

凸性在连续性最优化理论中起着重要的作用．它在离散性最优化中的相应概念尚待研究．本文运用差分和次梯度的概念给出排序问题中离散凸性的描述，并指出凸性在构造最优排序中的重要性．     

Convexity in Topological Affine Planes

We extend to topological affine planes the standard theorems of convexity, among them the separation theorem, the anti-exchange theorem, Radon's, Helly's, Caratheodory's, and Kirchberger's theorems, and the Minkowski theorem on extreme points. In a few cases the proofs are obtained by adapting proofs of the original results in the Euclidean plane; in others it is necessary to devise new proofs that are valid in the more general setting considered here.     

Uniform Convexity in Nonsymmetric Spaces

Mathematical Notes - Uniformly convex asymmetric spaces are defined. It is proved that every nonempty closed convex set in a uniformly convex complete asymmetric space is a set of approximative...     

Depth-Optimized Convexity Cuts

This paper presents a general, self-contained treatment of convexity or intersection cuts. It describes two equivalent ways of generating a cut—via a convex set or a concave function—and a partial-order notion of cut strength. We then characterize the structure of the sets and functions that generate cuts that are strongest with respect to the partial order. Next, we specialize this analytical framework to the case of mixed-integer linear programming (MIP). For this case, we formulate two kinds of the deepest cut generation problem, via sets or via functions, and subsequently consider some special cases which are amenable to efficient computation. We conclude with computational tests of one of these procedures on a large set of MIPLIB problems.     

N元Stolarsky平均的凸性和几何凸性

讨论了n个正数的Stolarsky平均的S-凸性和S-几何凸性,证明了:n元Stolarsky平均在r>1时是S-凸的和S-几何凸的;在r<1时是S-凹的.作为推论,此文也比较了n个正数的Stolarsky平均和算术平均的大小.     

N 元指数和对数平均的凸性及几何凸性

讨论了n 元指数平均和对数平均的凸性、S - 凸性、几何凸性及S - 几何凸性, 证明了:(1) n 元指数平均是S - 凹的和S - 几何凸的; (2) n 元第一对数平均是S - 凹的; (3) n 元第二对数平均是凹的和几何凸的. 最后提出了二个悬而未决的问题.     

Convexity in finite metric spaces

A subsetS of a metric space (X,d) is calledd-convex if for any pair of pointsx,y S each pointz X withd(x,z) +d(z,y) =d(x,y) belongs toS. We give some results and open questions concerning isometric and convexity-preserving embeddings of finite metric spaces into standard spaces and the number ofd-convex sets of a finite metric space.     

N元指数和对数平均的凸性及几何凸性

讨论了n元指数平均和对数平均的凸性、S-凸性、几何凸性及S-几何凸性，证明了：（1）n元指数平均是S-凹的和S-几何凸的；（2）n元第一对数平均是S-凹的；（3）n元第二对数平均是凹的和几何凸的．最后提出了二个悬而未决的问题．     

Finite distributive lattices are congruence lattices of almost-geometric lattices

A semimodular lattice L of finite length will be called an almost-geometric lattice if the order J(L) of its nonzero join-irreducible elements is a cardinal sum of at most two-element chains. We prove that each finite distributive lattice is isomorphic to the lattice of congruences of a finite almost-geometric lattice.     

Convexity methods in variational calculus

Book Review

Convexity methods in variational calculusPeter Smith: (Electronic and Electrical Engineering Research Studies. Applied and Engineering Mathematics Series 1), John Wiley, New York (ISBN 0471 906794), 1985. Research Studies Press, U.K. (ISBN 0 86380 022 X).     

Convexity andq-gamma function

Inequalities and convexity properties known for the gamma function are extended to theq-gamma function, 0<q<1. Applying some classical inequalities for convex functions, we deduce monotonicity results for several functions involving theq-gamma function. Further applications to the probability theory are given.     

Strong Restricted-Orientation Convexity

Strong restricted-orientation convexity is a generalization of standard convexity. We explore the properties of strongly convex sets in multidimensional Euclidean space and identify major properties of standard convex sets that also hold for strong convexity. We characterize strongly convex flats and halfspaces, and establish the strong convexity of the affine hull of a strongly convex set. We then show that, for every point in the boundary of a strongly convex set, there is a supporting strongly convex hyperplane through it. Finally, we show that a closed set with nonempty interior is strongly convex if and only if it is the intersection of strongly convex halfspaces; we state a condition under which this result extends to sets with empty interior.