Representations of polytopes and polyhedral sets

In this paper we describe a variant of the diagram techniques, such as Gale diagrams for polytopes and positive diagrams for positive bases, which is appropriate for polyhedral sets. We obtain our new technique as a translation-invariant representation of polytopes or polyhedral sets. This approach leads naturally to simpler proofs of the familiar combinatorial diagram relationships. However, this method is more versatile than those previously employed, in that it can be used to investigate linear systems of polyhedral sets, and metrical properties such as volume. In particular, we give an easy proof of a result of Meyer on decomposability of polytopes, and a more perspicuous way of looking at the well-known theorem of Minkowski on the realizability of polytopes whose facets have given outer normal vectors and areas.     

Locally Farkas-Minkowski linear inequality systems

This paper introduces thelocally Farkas-Minkowski (LFM) linear inequality systems in a finite dimensional Euclidean space. These systems are those ones that satisfy that any consequence of the system that is active at some solution point is also a consequence of some finite subsystem. This class includes the Farkas-Minkowski systems and verifies most of the properties that these systems possess. Moreover, it contains the locally polyhedral systems, which are the natural external representation of quasi-polyhedral sets. TheLFM systems appear to be the natural external representation of closed convex sets. A characterization based on their properties under the union of systems is provided. In linear semi-infinite programming, theLFM property is the more general constraint qualification such that the Karush-Kuhn-Tucker condition characterizes the optimal points. Furthermore, the pair of Haar dual problems has no duality gap.     

Analytical Linear Inequality Systems and Optimization

In many interesting semi-infinite programming problems, all the constraints are linear inequalities whose coefficients are analytical functions of a one-dimensional parameter. This paper shows that significant geometrical information on the feasible set of these problems can be obtained directly from the given coefficient functions. One of these geometrical properties gives rise to a general purification scheme for linear semi-infinite programs equipped with so-called analytical constraint systems. It is also shown that the solution sets of such kind of consistent systems form a transition class between polyhedral convex sets and closed convex sets in the Euclidean space of the unknowns.     

Shelling pseudopolyhedra

The notion of shellability originated in the context of polyhedral complexes and combinatorial topology. An abstraction of this concept for graded posets (i.e., graded partially ordered sets) was recently introduced by Björner and Wachs first in the finite case [1] and then with Walker in the infinite case [11]. Many posets arising in combinatorics and in convex geometry were investigated and some proved to be shellable. A key achievement was the proof by Bruggesser and Mani that boundary complexes of convex polytopes are shellable [4].We extend here the result of Bruggesser and Mani to polyhedral complexes arising as boundary complexes of more general convex sets, called pseudopolyhedra, with suitable asymptotic behavior. This includes a previous result on tilings of a Euclidean space ^d which are projections of the boundary of a (d+1)-pseudopolyhedron [7].     

Structure of the Space of Diametrically Complete Sets in a Minkowski Space

We study the structure of the space of diametrically complete sets in a finite dimensional normed space. In contrast to the Euclidean case, this space is in general not convex. We show that its starshapedness is equivalent to the completeness of the parallel bodies of complete sets, a property studied in Moreno and Schneider (Isr. J. Math. 2012, doi:10.1007/s11856-012-0003-6), which is generically not satisfied. The space in question is, however, always contractible. Our main result states that in the case of a polyhedral norm, the space of translation classes of diametrically complete sets of given diameter is a finite polytopal complex. The proof makes use of a diagram technique, due to P. McMullen, for the representation of translation classes of polytopes with given normal vectors. The paper concludes with a study of the extreme diametrically complete sets.     

Efficient solutions in generalized linear vector optimization

This paper establishes several new facts on generalized polyhedral convex sets and shows how they can be used in vector optimization. Among other things, a scalarization formula for the efficient solution sets of generalized linear vector optimization problems is obtained. We also prove that the efficient solution set of a generalized linear vector optimization problem in a locally convex Hausdorff topological vector space is the union of finitely many generalized polyhedral convex sets and it is connected by line segments.     

关于多胞形一个新仿射不变量的应用

用组合极值方法导出了n维欧氏空间中关于原点对称的一个凸多胞形子类上一个新的仿射不变量(最近由Lutwak,Yang和Zhang引入)的解析表达式,并给出了其在凸多胞形Minkowski问题的一个应用．     

Motzkin decomposition of closed convex sets

Theodore Motzkin proved, in 1936, that any polyhedral convex set can be expressed as the (Minkowski) sum of a polytope and a polyhedral convex cone. This paper provides five characterizations of the larger class of closed convex sets in finite dimensional Euclidean spaces which are the sum of a compact convex set with a closed convex cone. These characterizations involve different types of representations of closed convex sets as the support functions, dual cones and linear systems whose relationships are also analyzed in the paper. The obtaining of information about a given closed convex set F and the parametric linear optimization problem with feasible set F from each of its different representations, including the Motzkin decomposition, is also discussed.     

Some results on quasipolyhedral convexity

The objective of this paper is to analyze under what well-known operations the class of quasipolyhedral convex functions, which can be regarded as an extension of that of polyhedral convex functions, is closed. The operations that will be considered are those that preserve polyhedral convexity, such that the image and the inverse image under linear transformations, right scalar multiplication (including the case where λ=0⁺) and pointwise addition.      

Existence and Boundedness of Solutions in Infinite-Dimensional Vector Optimization Problems

This work focuses on the nonemptiness and boundedness of the sets of efficient and weak efficient solutions of a vector optimization problem, where the decision space is a normed space and the image space is a locally convex Hausdorff topological linear space. By studying certain boundedness and coercivity concepts of vector-valued functions and via an asymptotic analysis, we extend to this kind of problems some well-known existence and boundedness results for efficient and weak efficient solutions of multiobjective optimization problems with Pareto or polyhedral orderings. Some of these results are proved under weaker assumptions.     

Éléments finis mixtes minimaux sur les polyèdres

Given a cellular complex consisting of polytopes, embedded in a Euclidean space, we construct finite element spaces of differential forms, conforming with respect to the exterior derivative, containing those that are polynomial of given maximal degree, having locally the property of exact sequence and extension, so that among all spaces having these properties they have the smallest dimension. More generally we construct, for any finite element system included in a compatible finite element system, an intermediate compatible finite element system of minimal dimension.     

Properties of ℛ-Sausages

This paper is concerned with the Steiner ratio. A number of properties about the structure of the flat sausage and -Sausage convex polytopes yielding the best Steiner ratio in two- and three-dimensional Euclidean space, and the topology of the Steiner Minimal Tree for the corresponding vertex sets, are presented.     

Mixed-volume computation by dynamic lifting applied to polynomial system solving

The aim of this paper is to present a flexible approach for the efficient computation of the mixed volume of a tuple of polytopes. In order to compute the mixed volume, a mixed subdivision of the tuple of polytopes is needed, which can be obtained by embedding the polytopes in a higher-dimensional space, i.e., by lifting them. Dynamic lifting is opposed to the static approach. This means that one considers one point at a time and only fixes the value of the lifting function when the point really influences the mixed volume. Conservative lifting functions have been developed for this purpose. This provides us with a deterministic manipulation of the lifting for computing mixed volumes, which rules out randomness conditions. Cost estimates for the algorithm are given. The implications of dynamic lifting on polyhedral homotopy methods for the solution of polynomial systems are investigated and applications are presented.     

Local tensor valuations on convex polytopes

Local versions of the Minkowski tensors of convex bodies in $n$ -dimensional Euclidean space are introduced. An extension of Hadwiger’s characterization theorem for the intrinsic volumes, due to Alesker, states that the continuous, isometry covariant valuations on the space of convex bodies with values in the vector space of symmetric $p$ -tensors are linear combinations of modified Minkowski tensors. We ask for a local analogue of this characterization, and we prove a classification result for local tensor valuations on polytopes, without a continuity assumption.     

An upper bound on the expectation of simplicial functions of multivariate random variables

We introduce an upper bound on the expectation of a special class of sublinear functions of multivariate random variables defined over the entire Euclidean space without an independence assumption. The bound can be evaluated easily requiring only the solution of systems of linear equations thus permitting implementations in high-dimensional space. Only knowledge on the underlying distribution means and second moments is necessary. We discuss pertinent techniques on dominating general sublinear functions by using simpler sublinear and polyhedral functions and second order quadratic functions.     

Properties of faces of parallelohedra

We consider an important class of polytopes, called parallelohedra, that tile the Euclidean space. The concepts of a standard face of a parallelohedron and of the index of a face are introduced. It is shown that the sum of indices of standard faces in a parallelohedron is an invariant; this implies the Minkowski bound for the number of facets of parallelohedra. New properties of faces of parallelohedra are obtained.     

Lifting tropical curves in space and linear systems on graphs

Tropicalization is a procedure for associating a polyhedral complex in Euclidean space to a subvariety of an algebraic torus. We study the question of which graphs arise from tropicalizing algebraic curves. By using Baker’s specialization of linear systems from curves to graphs, we are able to give a necessary condition for a balanced weighted graph to be the tropicalization of a curve. Our condition reproduces a generalization of Speyer’s well-spacedness condition and also gives new conditions. In addition, it suggests a new combinatorial structure on tropicalizations of algebraic curves.     

A generalization of antiwebs to independence systems and their canonical facets

We consider independence system polytopes, i.e. polytopes whose extreme points are the incidence vectors of the sets of an independence system. We first give a sufficient condition for recognizing Boolean facets. Then, the notion of antiweb introduced by Trotter for graphs is generalized to independence systems and used for obtaining canonical facets of the associated polytopes. We also point out how our results relate with known ones for knapsack, set covering and matroid polytopes.     

Computing reachable sets of hybrid systems using a combination of zonotopes and polytopes

The computation of reachable sets for hybrid systems with linear continuous dynamics is addressed. Zonotopes are used for the representation of reachable sets, resulting in an algorithm with low computational complexity with respect to the dimension of the considered system. However, zonotopes have drawbacks when being intersected with transition guards which determine the discrete behavior of the hybrid system. For this reason, in the proposed approach, reachable sets are represented by polytopes within guard sets as an intermediate step in order to enclose them by zonotopes afterwards. Different methods for the conservative conversion from zonotopes to polytopes and vice versa are proposed and numerically evaluated.     

Multidimensional triangle-truncated simplexes

We consider the convex polytopes, called triangle-truncated simplexes. From the point of view of a constructive object in four and higher dimensions vector space such polytopes are multidimensional analogs of one classical semi-regular polytopes, namely, truncated tetrahedron. We present results of investigations of inner geometrical structure and combinatorial characteristics of the complete assemblage of faces of triangle-truncated simplexes in vector spaces of arbitrary dimension. We formulate and prove a theorem about the volumes of multidimensional truncated simplex of generalized kind in Euclidean space.