Search

In this work, we propose a new approach called “Successive Linear Programming Algorithm (SLPA)” for finding an approximate global minimizer of general nonconvex quadratic programs. This algorithm can be initialized by any extreme point of the convex polyhedron of the feasible domain. Furthermore, we generalize the simplex algorithm for finding a local minimizer of concave quadratic programs written in standard form. We prove a new necessary and sufficient condition for local optimality, then we describe the Revised Primal Simplex Algorithm (RPSA). Finally, we propose a hybrid local-global algorithm called “SLPLEX”, which combines RPSA with SLPA for solving general concave quadratic programs. In order to compare the proposed algorithms to the branch-and-bound algorithm of CPLEX12.8 and the branch-and-cut algorithm of Quadproga, we develop an implementation with MATLAB and we present numerical experiments on 139 nonconvex quadratic test problems.

Considering the effects of asynchronous controller area network (CAN)-induced random delays in the control system of a dual motor plug-in hybrid electric vehicle (DM-PHEV), a robust $$\mathrm {H_\infty }$$ non-clutch coordinated controllers of mode transition process (MTP) are developed in this paper. A novel non-clutch coordinated control strategy which avoids the clutch slipping stage is proposed based on the structural characteristics of dual motors. Besides, by analyzing the characteristics of asynchronous CAN-induced random delays (ACDs) caused by the multiple actuators of DM-PHEV, complex nonlinearities of ACDs are modeled by convex polytope. Two different $$\mathrm {H_\infty }$$ non-clutch coordinated controllers are proposed to ensure the performance of MTP with ACDs. One controller considers that the control signal transmitted by CAN bus is derivative of torque, and the other controller considers the signal as torque. Comparative simulation and hardware-in-the-loop (HiL) test are provided to demonstrate the performance of MTP controlled by proposed controllers.

We present an explicit method to compute the (Siciak-Zaharjuta) extremal function of a real convex polytope in terms of supporting simplices and strips. We use this to give a new proof of the existence of extremal ellipses associated to the extremal function of a real convex body., Comment: 45 pages, 4 figures. The main theorem has a new proof

Steinitz’s theorem states that a graph G is the edge-graph of a 3-dimensional convex polyhedron if and only if, G is simple, plane and 3-connected. We prove an analogue of this theorem for ball polyhedra, that is, for intersections of finitely many unit balls in $$\mathbb {R}^3$$ R 3 .

We study properties of the realizations of groups as the combinatorial automorphism group of a convex polytope. We show that for any non-abelian group G with a central involution there is a centrally symmetric polytope with G as its combinatorial automorphisms. We show that for each integer n, there are groups that cannot be realized as the combinatorial automorphisms of convex polytopes of dimension at most n. We also give an optimal lower bound for the dimension of the realization of a group as the group of isometries that preserves a convex polytope.

We give several new criteria to judge whether a simple convex polytope in a Euclidean space is combinatorially equivalent to a product of simplices. These criteria are mixtures of combinatorial, geometrical and topological conditions that are inspired by the ideas from toric topology., 15 pages, 3 figures

In this work, we deal with a global optimization problem (P) for which we look for the most preferred extreme point (vertex) of the convex polyhedron according to a new linear criterion, among all efficient vertices of a multi-objective linear programming problem. This problem has been studied for decades and a lot has been done since the 70’s. Our purpose is to propose a new and effective methodology for solving (P) using a branch and bound based technique, in which, at each node of the search tree, new customized bounds are established to delete uninteresting areas from the decision space. In addition, an efficiency test is performed considering the last simplex tableau corresponding to the current visited vertex. A comparative study shows that the proposed method outperforms the most recent and performing method dedicated to solve (P).

In this paper, we propose a method for determining all minimal representations of a face of a polyhedron defined by a system of linear inequalities. Main difficulties for determining prime and minimal representations of a face are that the deletion of one redundant constraint can change the redundancy of other constraints and the number of descriptor index pairs for the face can be huge. To reduce computational efforts in finding all minimal representations of a face, we prove and use properties that deleting strongly redundant constraints does not change the redundancy of other constraints and all minimal representations of a face can be found only in the set of all prime representations of the face corresponding to the maximal descriptor index set for it. The proposed method is based on a top-down search strategy, is easy to implement, and has many computational advantages. Based on minimal representations of a face, a reduction of degeneracy degrees of the face and ideas to improve some known methods for finding all maximal efficient faces in multiple objective linear programming are presented. Numerical examples are given to illustrate the method.

We construct convex functions on $$\mathbb {R}^3$$ and $$\mathbb {R}^4$$ that are smooth solutions to the Monge–Ampere equation $$\begin{aligned} \det D^2u = 1 \end{aligned}$$ away from compact one-dimensional singular sets, which can be Y-shaped or form the edges of a convex polytope. The examples solve the equation in the Alexandrov sense away from finitely many points. Our approach is based on solving an obstacle problem where the graph of the obstacle is a convex polytope

This article is the publication of Yurii Aleksandrovich Volkov’s (1930–1981) Ph.D. thesis, in which A.D. Aleksandrov’s famous theorem on the existence of a convex polyhedron with a given development is proved using a variational method.

We introduce “Polyhedral Support Vector Regression” (PSVR), a regression model for data represented by arbitrary convex polyhedral sets. PSVR is derived as a generalization of support vector regression, in which the data is represented by individual points along input variables $$X_1$$ , $$X_2$$ , $$\ldots $$ , $$X_p$$ and output variable Y, and extends a support vector classification model previously introduced for polyhedral data. PSVR is in essence a robust-optimization model, which defines prediction error as the largest deviation, calculated along Y, between an interpolating hyperplane and all points within a convex polyhedron; the model relies on the affine Farkas’ lemma to make this definition computationally tractable within the formulation. As an application, we consider the problem of regression with missing data, where we use convex polyhedra to model the multivariate uncertainty involving the unobserved values in a data set. For this purpose, we discuss a novel technique that builds on multiple imputation and principal component analysis to estimate convex polyhedra from missing data, and on a geometric characterization of such polyhedra to define observation-specific hyper-parameters in the PSVR model. We show that an appropriate calibration of such hyper-parameters can have a significantly beneficial impact on the model’s performance. Experiments on both synthetic and real-world data illustrate how PSVR performs competitively or better than other benchmark methods, especially on data sets with high degree of missingness.

As a special form of piecewise linear classifier, the convex polyhedron classifier is simple to implement and achieves rapid response in real-time classification. However, it usually performs badly in the case of high noise where severe boundary intrusion exists. Inspired by the scheme of soft margin in support vector machine, in this paper we propose a soft-margin convex polyhedron classifier for nonlinear classification task. The base (linear) classifier is first generalized to its soft-margin version through kernelization process and slack variables. In each local region, the soft-margin base classifier learns a decision hyperplane with noise tolerance. Then, a series of learned hyperplanes are structurally integrated into a convex polyhedron classifier, which is essentially a convex polyhedron that encloses one class and excludes the other class outside. Experimental results on fifteen benchmark datasets show the proposed soft-margin convex polyhedron classifier is comparable to linear support vector machine and four piecewise linear classifiers, but does not perform as well as the support vector machine with radial basis function kernel in general. When random noises are added to datasets, the soft-margin convex polyhedron classifier achieves similar or better accuracies with the well-known classifiers used for comparison, implying its promising ability of noise tolerance.

We show that the space of theta functions on tropical tori is identified with a convex polyhedron. We also show a Riemann-Roch inequality for tropical abelian surfaces by calculating the self-intersection numbers of divisors.

Inference procedure is a critical step of experimental researches to draw scientific conclusions especially in multiple testing. The false positive rate increases unless the unadjusted marginal p-values are corrected. Therefore, a multiple testing correction is necessary to adjust the p-values based on the number of tests to control type I error. We propose a multiple testing correction of MAX-test for a contingency table, where multiple χ2-tests are applied based on a truncated normal distribution (TND) estimation method by Botev. The table and tests are defined geometrically by contour hyperplanes in the degrees of freedom (df) dimensional space. A linear algebraic method called spherization transforms the shape of the space, defined by the contour hyperplanes of the distribution of tables sharing the same marginal counts. So, the stochastic distributions of these tables are transformed into a standard multivariate normal distribution in df-dimensional space. Geometrically, the p-value is defined by a convex polytope consisted of truncating hyperplanes of test’s contour lines in df-dimensional space. The TND approach of the Botev method was used to estimate the corrected p. Finally, the features of our approach were extracted using a real GWAS data.

Metric basis and metric dimension has become an integral part of molecular topology and combinatorial chemistry. It has a lot of applications in pharmacy, chemistry, computer, and mathematical disciplines. Let $$\Phi =(V,E)$$ be a simple connected graph. A subset $$F=\{y_{1}, y_{2}, y_{3},\ldots ,y_{s}\}$$ of distinct vertices from $$V(\Phi )$$ is called a resolving set if for any $$a \in V(\Phi )$$ , the metric code of a with respect to F that is denoted by $$\zeta (a|F)$$ , which is defined as $$\zeta (a|F)=(d(y_{1},a), d(y_{2},a), d(y_{3}, a),\ldots , d(y_{s},a))$$ , is distinct for distinct a. Then, such a set F with minimum cardinality is called the metric basis for $$\Phi $$ , and this minimum cardinality of a resolving set F is called the metric dimension of $$\Phi $$ and is denoted by $$dim(\Phi )$$ . A polytope in elementary geometry is a geometric object with flat sides. The polytopes which are convex sets and are contained in the n-dimensional space $$\mathbb {R}^{n}$$ (Euclidean space) are termed convex polytopes. Convex polytopes have found a lot of applications in different areas of computer science and mathematics. In this work, we construct two closely related families of convex polytope graphs (viz., $$\mathfrak {D}_{n}$$ and $$\mathfrak {Q}_{n}$$ ), using the existing families of convex polytope graphs. We study the metric dimension for these graphs and prove that only three vertices are a minimum requirement for the unique identification of all vertices in these graphs. We also give some partial answers to the problems raised in the recent past.

We study stable and strongly stable matchings in the marriage market with indifference in their preferences. We characterize the stable matchings as integer extreme points of a convex polytope. We give an alternative proof for the integrity of the strongly stable matching polytope. Also, we compute men-optimal (women-optimal) stable and strongly stable matchings using linear programming. When preferences are strict, we find the men-optimal (women-optimal) stable matching.

The problem of deciding if a given triangulation of a sphere can be realized as the boundary sphere of a simplicial, convex polytope is known as the ‘Simplicial Steinitz problem’. It is known by an indirect and non-constructive argument that a vast majority of Bier spheres are non-polytopal. Contrary to that, we demonstrate that the Bier spheres associated to threshold simplicial complexes are all polytopal. Moreover, we show that all Bier spheres are starshaped. We also establish a connection between Bier spheres and Kantorovich–Rubinstein polytopes by showing that the boundary sphere of the KR-polytope associated to a polygonal linkage (weighted cycle) is isomorphic to the Bier sphere of the associated simplicial complex of “short sets”.

In this paper, we present a bilevel optimal motion planning (BOMP) model for autonomous parking. The BOMP model treats motion planning as an optimal control problem, in which the upper level is designed for vehicle nonlinear dynamics, and the lower level is for geometry collision-free constraints. The significant feature of the BOMP model is that the lower level is a linear programming problem that serves as a constraint for the upper-level problem. That is, an optimal control problem contains an embedded optimization problem as constraints. Traditional optimal control methods cannot solve the BOMP problem directly. Therefore, the modified approximate Karush–Kuhn–Tucker theory is applied to generate a general nonlinear optimal control problem. Then the pseudospectral optimal control method solves the converted problem. Particularly, the lower level is the $$J_2$$J2-function that acts as a distance function between convex polyhedron objects. Polyhedrons can approximate objects in higher precision than spheres or ellipsoids. As a result, a fast high-precision BOMP algorithm for autonomous parking concerning dynamical feasibility and collision-free property is proposed. Simulation results and experiment on Turtlebot3 validate the BOMP model, and demonstrate that the computation speed increases almost two orders of magnitude compared with the area criterion based collision avoidance method.

A cage G, defined as the 1-skeleton of a convex polytope in 3-space, holds a compact set K if G cannot move away without meeting the relative interior of K. The main results of this paper establish the infimum of the lengths of cages holding various compact convex sets. First, planar graphs and Steiner trees are investigated. Then the notion of points almost fixing a convex body in the plane is introduced and studied. The last two sections treat cages holding 2-dimensional compact convex sets, respectively the regular tetrahedron.

Let $$G=(V, E)$$ be a connected graph. The distance between the edge $$e=uv\in E$$ and the vertex $$x\in V$$ is given by $$d(e, x) = \min \{d(u, x), d(v, x)\}$$. A subset $$S_{E}$$ of vertices is called an edge metric generator for G if for every two distinct edges $$e_{1}, e_{2}\in E$$, there exists a vertex $$x\in S_{E}$$ such that $$d(e_{1}, x)\ne d(e_{2}, x)$$. An edge metric generator containing a minimum number of vertices is called an edge metric basis for G and the cardinality of an edge metric basis is called the edge metric dimension denoted by $$\mu _{E}(G)$$. In this paper, we study the edge metric dimension of some classes of plane graphs. It is shown that the edge metric dimension of convex polytope antiprism $$A_{n}$$, the web graph $${\mathbb {W}}_{n}$$, and convex polytope $${\mathbb {D}}_{n}$$ are bounded, while the prism related graph $$D^{*}_{n}$$ has unbounded edge metric dimension.

In the classical setting, a convex polytope is called semiregular if its facets are regular and its symmetry group is transitive on vertices. This paper continues our study of alternating abstract semiregular polytopes $$\mathcal {S}$$ . These structures have two kinds of abstract regular facets $$\mathcal {P}$$ and $$\mathcal {Q}$$ , still with combinatorial automorphism group transitive on vertices. Furthermore, for some interlacing number $$k\geqslant 1$$ , k copies each of $$\mathcal {P}$$ and $$\mathcal {Q}$$ can be assembled in alternating fashion around each face of co-rank 2 in $$\mathcal {S}$$ . Here we focus on constructions involving interesting pairs of polytopes $$\mathcal {P}$$ and $$\mathcal {Q}$$ . In some cases, $$\mathcal {S}$$ can be constructed for general values of k. In other remarkable instances, interlacing with certain finite interlacing numbers proves impossible.

This paper proposes a method for analyzing comprehensive theoretical digging performance of an excavator based on the convex polytope. The convex polytope is generated by using Newton–Euler’s equations to establish dynamic relationships between the digging capability of the bucket and the driving capability of hydraulic cylinders with the consideration of the excavator tipping and slipping constraints, and is used to identify the excavator’s output capability for digging forces and moments in the bucket force space. A set of indices for theoretically quantifying the digging capability, digging efficiency, as well as the matchability between the manipulator mechanism and the driving capability of hydraulic cylinders are proposed based on the polytope, and they are used to assess the digging trajectory characteristics and the dynamic digging performance of the entire excavator workspace. Two case studies for the excavator’s digging performance assessment and optimal digging trajectory generation are conducted to test and validate this method. The proposed method contributes to comprehensively and deeply understand the design principles of an excavator, and shows the promising application prospect for guiding the design and development of new excavators.

This paper is concerned with stability criteria of networked control system with two additive time-varying delay components. Firstly, by separating the whole delay interval into subintervals and using a new inequality in combination with convex polyhedron method, a less conservative criterion is proposed and an approach of stabilization controller design is given based on the obtained criterion. Secondly, a congruent condition and an extended condition with the same allowable delay upper bound are respectively deduced by using two different inequalities. Finally, some numerical examples are presented to illustrate the effectiveness of the obtained method.

A pseudo-edge graph of a convex polyhedron K is a 3-connected embedded graph in K whose vertices coincide with those of K, whose edges are distance minimizing geodesics, and whose faces are convex. We construct a convex polyhedron K in Euclidean 3-space with a pseudo-edge graph with respect to which K is not unfoldable. The proof is based on a result of Pogorelov on convex caps with prescribed curvature, and an unfoldability obstruction for almost flat convex caps due to Tarasov. Our example, which has 340 vertices, significantly simplifies an earlier construction by Tarasov, and confirms that Durer's conjecture does not hold for pseudo-edge unfoldings., Comment: 19 pages, 10 figures. Minor revisions. Accepted for publication in Discrete and Computational Geometry

We prove constructively that: The complement $${{\mathbb {R}}}^n{\setminus }\mathcal {K}$$ of ann-dimensional unbounded convex polyhedron $$\mathcal {K}\subset {{\mathbb {R}}}^n$$ and the complement $${{\mathbb {R}}}^n{\setminus }{\text {Int}}(\mathcal {K})$$ of its interior are polynomial images of $${{\mathbb {R}}}^n$$ whenever $$\mathcal {K}$$ does not disconnect $${{\mathbb {R}}}^n$$ . The case of a compact convex polyhedron and the case of convex polyhedra of small dimension were approached by the authors in previous works. The techniques here are more sophisticated than those corresponding to the compact case and require rational separation results for tuples of variables, which have interest by their own and can be applied to separate certain types of (non-compact) semialgebraic sets.

We study the limit shape of successive coronas of a tiling, which models the growth of crystals. We define basic terminologies and discuss the existence and uniqueness of corona limits, and then prove that corona limits are completely characterized by directional speeds. As an application, we give another proof that the corona limit of a periodic tiling is a centrally symmetric convex polyhedron (see [Zhuravlev 2001], [Maleev-Shutov 2011])., Comment: Revised into 26 pages, to appear in Discrete and Computational Geometry

In this article, the fault detection (FD) reduced-order filtering problem is investigated for a family of polytopic uncertain continuous-time Markovian jump linear systems (MJLSs) with time-varying delays. Under meeting the the premise of fault detection accuracy, the reduced order fault detection filters are desirable in applications where fast data processing and saving computing space are necessary. Then, by the aid of the Markovian Lyapunov-Krasovskii functional and convex polyhedron techniques, some novel time-varying delays and polytopic uncertain sufficient conditions are proposed to insure the existence of the FD reduced-order filter. Finally, a simulated continuous stirred tank reactor process example is provided to verify the feasibility of the proposed methodology.

Given a convex body $$K \subset {\mathbb {R}}^n$$ with the barycenter at the origin, we consider the corresponding Kahler–Einstein equation $$e^{-\Phi } = \det D^2 \Phi $$ . If K is a simplex, then the Ricci tensor of the Hessian metric $$D^2 \Phi $$ is constant and equals $$\frac{n-1}{4(n+1)}$$ . We conjecture that the Ricci tensor of $$D^2 \Phi $$ for an arbitrary convex body $$K \subseteq {\mathbb {R}}^n$$ is uniformly bounded from above by $$\frac{n-1}{4(n+1)}$$ and we verify this conjecture in the two-dimensional case. The general case remains open.

Utilizing linear matrix inequalities (LMI) framework, in this paper a robust control model for multi-input–output DC/DC converter is presented based on its analytical study. This converter is composed of two conventional converters, buck-boost and boost, which can supply the load when one of the inputs fails to do so. Employing the LMI method makes it possible to modelize the nonlinearities and uncertainties as a convex polytope. So, by considering LMI constraints, a certain rejection level of noise and an area for pole location are guaranteed robustly. Utilizing this method along with standard optimization algorithms can set the multi objective robust controller automatically. The simulation results are derived by MATLAB for a low efficiency implementable state-feedback and are compared with a conventional PID controller.

Many hard problems in the computational sciences are equivalent to counting the leaves of a decision tree, or, more generally, by summing a cost function over the nodes. These problems include calculating the permanent of a matrix, finding the volume of a convex polyhedron, and counting the number of linear extensions of a partially ordered set. Many approximation algorithms exist to estimate such sums. One of the most recent is Stochastic Enumeration (SE), introduced in 2013 by Rubinstein. In 2015, Vaisman and Kroese provided a rigorous analysis of the variance of SE, and showed that SE can be extended to a fully polynomial randomized approximation scheme for certain cost functions on random trees. We present an algorithm that incorporates an importance function into SE, and provide theoretical analysis of its efficacy. We also present the results of numerical experiments to measure the variance of an application of the algorithm to the problem of counting linear extensions of a poset, and show that introducing importance sampling results in a significant reduction of variance as compared to the original version of SE.

For any given finite group, Schulte and Williams (2015) establish the existence of a convex polytope whose combinatorial automorphisms form a group isomorphic to the given group. We provide here a shorter proof for a stronger result: the convex polytope we build for the given finite group is binary, and even combinatorial in the sense of Naddef and Pulleyblank (1981); the diameter of its skeleton is at most 2; any combinatorial automorphism of the polytope is induced by some isometry of the space; any automorphism of the skeleton is a combinatorial automorphism., Comment: The revised version gives a better proof for the property of the automorphisms of the polytope skeleton (Theorem 1, (v)). It also takes into account suggestions made by two anonymous referees. The final paper is to appear in Discrete and Computational Geometry

Choose uniform random points $$X_1, \dots , X_n$$ in a given convex set and let $${\text { conv}}[X_1, \dots , X_n]$$ be their convex hull. It is shown that in dimension three the expected volume of this convex hull is in general not monotone with respect to set inclusion. This answers a question by Meckes in the negative. The given counterexample is formed by uniformly distributed points in the three-dimensional tetrahedron together with a small perturbation of it. As side result we obtain an explicit formula for all even moments of the volume of a random simplex which is the convex hull of three uniform random points in the tetrahedron and the center of one facet.

We study the absorbing invariant set of a dynamical system defined by a map derived from Error Diffusion, a greedy online approximation algorithm that minimizes the (Euclidean) norm of the cumulated error. This algorithm assigns a sequence of outputs, each a vertex of some polytope, to any sequence of inputs in that polytope. Here, the polytope is assumed to be a simplex that is acute, meaning that the pairs of distinct external normal vectors to the codimension-one faces form obtuse angles. The input is assumed to be constant. The map is a system which consists of piecewise translations acting on the partition of an affine space into the Vorono¨i regions defined (once tie-breaking is resolved) by the vertices of the polytope. The translation vector in each partition piece is the difference between the input modified by adding the cumulated error and the corresponding vertex. When the polytope is a simplex such piecewise translation projects onto a translation of a torus. We prove that if the projected translation is ergodic, then there is an invariant absorbing set of the piecewise translation which is a fundamental set for the lattice generated by the simplex and which is a limit set of any bounded set with nonempty interior.

Agraïments: The first and third authors are partially supported by FAPEMIG grant APQ-001082/14. The third author is partially supported by CNPq grant 472321/2013-7 and by FAPEMIG grant PPM-00516-15. The second and third autors are supported by CAPES CSF-PVE grant 88881.030454/2013-01. MacMillan and Bartky in 1932 proved that there is a unique isosceles trapezoid central configuration of the 4--body problem when two pairs of equal masses are located at adjacent vertices. After this result the following conjecture was well known between people working on central configurations: The isosceles trapezoid is the unique convex central configuration of the planar 4--body problem when two pairs of equal masses are located at adjacent vertices. We prove this conjecture.

The design of robust $$H_\infty $$ filters for discrete-time systems with delays and lossy measurements is solved in this paper, when the uncertain parameters lie inside a given convex polytope, and measurements are lost following a binary switching sequence satisfying a conditional probability distribution. Delay-dependent $$H_\infty $$ filters are designed, which ensure that the filtering error system is exponentially mean-square stable, and that a given $$H_\infty $$ level of disturbance attenuation is achieved for the admissible uncertainties and lossy measurements. Less conservative results are obtained, compared with previous results, which are established in terms of LMIs. An iterative algorithm from numerical optimization ideas is proposed to design the filter. Three numerical examples illustrate the applicability of the proposed methodology.

Central configurations of the n-body problem have been studied for more than 200 years since the pioneer works of Euler and Lagrange. In this article we study convex central configurations which are not strictly convex. We give explicit examples of such configurations in both planar and spatial n-body problems. Particularly, in the spatial case, we consider regular polyhedra with bodies of same mass m at the vertices and bodies of same mass M at the middle points of each edge. In this setting we prove that the cube is the unique regular polyhedron such that this construction leads to a convex central configuration which is not strictly convex.

For a finite/infinite family of closed convex sets with nonempty intersection in Hilbert space, we consider the (bounded) linear regularity property and the linear convergence property of the projection-based methods for solving the convex feasibility problem. Several sufficient conditions are provided to ensure the bounded linear regularity in terms of the interior-point conditions and some finite codimension assumptions. A unified projection method, called Algorithm B-EMOPP, for solving the convex feasibility problem is proposed, and by using the bounded linear regularity, the linear convergence results for this method are established under a new control strategy introduced here.

Consider n points \(X_1,\ldots ,X_n\) in \(\mathbb {R}^d\) and denote their convex hull by \({\Pi }\). We prove a number of inclusion–exclusion identities for the system of convex hulls \({\Pi }_I:=\mathrm{conv}(X_i: i\in I)\), where I ranges over all subsets of \(\{1,\ldots ,n\}\). For instance, denoting by \(c_k(X)\) the number of k-element subcollections of \((X_1,\ldots ,X_n)\) whose convex hull contains a point \(X\in \mathbb {R}^d\), we prove that $$\begin{aligned} c_1(X)-c_2(X)+c_3(X)-\cdots + (-1)^{n-1} c_n(X) = (-1)^{\dim {\Pi }} \end{aligned}$$ for allX in the relative interior of \({\Pi }\). This confirms a conjecture of Cowan (Adv Appl Probab 39(3):630–644, 2007) who proved the above formula for almost allX. We establish similar results for the number of polytopes \({\Pi }_J\) containing a given polytope \({\Pi }_I\) as an r-dimensional face, thus proving another conjecture of Cowan (Discrete Comput Geom 43(2):209–220, 2010). As a consequence, we derive inclusion–exclusion identities for the intrinsic volumes and the face numbers of the polytopes \({\Pi }_I\). The main tool in our proofs is a formula for the alternating sum of the face numbers of a convex polytope intersected by an affine subspace. This formula generalizes the classical Euler–Schlafli–Poincare relation and is of independent interest.

Let $$X(Q,\Lambda )$$ be a quasitoric manifold associated to a simple convex polytope Q and characteristic function $$\Lambda $$ . Let $$T\cong ({S}^1)^n$$ denote the compact n-torus acting on $$X=X(Q,\Lambda )$$ . The main aim of this article is to give a presentation of the T-equivariant K-ring of X, as a Stanley–Reisner ring over $$K^*(pt)$$ . We also derive the presentation for the ordinary K-ring of X.

In this paper, by using Wu–Debnath’s method, we establish inequalities of Hammer–Bullen type for convex sequences and nondecreasing convex functions. In particular, we give an extension of a recent Farissi’s inequality. By assuming the symmetry of an involved sequence, we derive an inequality of Fejer–Hammer–Bullen type for convex sequences. In addition, we establish some companions of an Hermite–Hadamard like inequality by Latreuch and Belaidi. In our approach we use matrix methods based on column stochastic matrices.

A convex geometry is a closure space satisfying the anti-exchange axiom. For several types of algebraic convex geometries we describe when the collection of closed sets is order scattered, in terms of obstructions to the semilattice of compact elements. In particular, a semilattice $\Omega(\eta)$, that does not appear among minimal obstructions to order-scattered algebraic modular lattices, plays a prominent role in convex geometries case. The connection to topological scatteredness is established in convex geometries of relatively convex sets., Comment: 25 pages, 1 figure, submitted

For a d-dimensional convex polytope \(P\subset {\mathbb {R}}^d\), the outer normal unit vectors of its facets span another d-dimensional polytope, which is called the outer normal transform of P and denoted by \(P^*\). It seems that this transform, which clearly differs from the usual polarity transform, was not seriously investigated until now. We derive results about polytopes having natural properties with respect to this transform, like self-duality or equality for the composition of it. Among other things we prove that if P is a convex polytope inscribed in the unit sphere with the property that the circumradii of its facets are all equal, then \((P^*)^*\) coincides with P. We also prove that the converse is true when P or \(P^*\) has at most 2d vertices. For the three-dimensional case, we characterize the family of those tetrahedra T such that T and \(T^*\) are congruent.

We call the $\delta$-vector of an integral convex polytope of dimension $d$ flat if the $\delta$-vector is of the form $(1,0,\ldots,0,a,\ldots,a,0,\ldots,0)$, where $a \geq 1$. In this paper, we give the complete characterization of possible flat $\delta$-vectors. Moreover, for an integral convex polytope $\mathcal{P} \subset \mathbb{R}^N$ of dimension $d$, we let $i(\mathcal{P},n)=|n\mathcal{P} \cap \mathbb{Z}^N|$ and $\ i^*(\mathcal{P},n)=|n(\mathcal{P} \setminus \partial \mathcal{P}) \cap \mathbb{Z}^N|.$ By this characterization, we show that for any $d \geq 1$ and for any $k,\ell \geq 0$ with $k+\ell \leq d-1$, there exist integral convex polytopes $\mathcal{P}$ and $\mathcal{Q}$ of dimension $d$ such that (i) For $t=1,\ldots,k$, we have $i(\mathcal{P},t)=i(\mathcal{Q},t),$ (ii) For $t=1,\ldots,\ell$, we have $i^*(\mathcal{P},t)=i^*(\mathcal{Q},t)$ and (iii) $i(\mathcal{P},k+1) \neq i(\mathcal{Q},k+1)$ and $i^*(\mathcal{P},\ell+1)\neq i^*(\mathcal{Q},\ell+1).$, Comment: 7 pages

A bilevel linear programming problem with ambiguous lower-level objective function is a sequential decision making under uncertainty of rational reaction. The ambiguous lower-level objective function is assumed that the coefficient vector of the follower lies in a convex polytope. We apply the maximin solution approach and formulate it as a special kind of three-level programming problem. Since an optimal solution exists at a vertex of feasible region, we adopt k-th best method to search an optimal solution. At each iteration of the k-th best method, we check rationality, local optimality and global optimality of the candidate solution. In this study, we propose a global optimality test based on an inner approximation method and compare its computational efficiency to other test methods based on vertex enumeration. We also extensively utilize the history of rationality tests to verify the rationality of the solution in the follower’s problem. Numerical experiments show the advantages of the proposed methods.

Differential carrier phase applications that utilize cycle resolution need the probability density function of the baseline estimate to quantify its region of concentration. For the integer bootstrap estimator, the density function has an analytical definition that enables probability calculations given perfect statistical knowledge of measurement and process noise. This paper derives a method to upper bound the tail probability of the integer bootstrapped GNSS baseline when the measurement and process noise correlation functions are unknown, but can be upper and lower bounded. The tail probability is shown to be a non-convex function of a vector of conditional variances, whose feasible region is a convex polytope. We show how to solve the non-convex optimization problem globally by discretizing the polytope into small hyper-rectangular elements, and demonstrate the method for a static baseline estimation problem.

We prove that the second derived subdivision of any rectilinear triangulation of any convex polytope is shellable. Also, we prove that the first derived subdivision of every rectilinear triangulation of any convex 3-dimensional polytope is shellable. This complements Mary Ellen Rudin's classical example of a non-shellable rectilinear triangulation of the tetrahedron. Our main tool is a new relative notion of shellability that characterizes the behavior of shellable complexes under gluing. As a corollary, we obtain a new characterization of the PL property in terms of shellability: A triangulation of a sphere or of a ball is PL if and only if it becomes shellable after sufficiently many derived subdivisions. This improves on PL approximation theorems by Whitehead, Zeeman and Glaser, and answers a question by Billera and Swartz. We also show that any contractible complex can be made collapsible by repeatedly taking products with an interval. This strengthens results by Dierker and Lickorish, and resolves a conjecture of Oliver. Finally, we give an example that this behavior extends to non-evasiveness, thereby answering a question of Welker.

The aim of this paper is to study finite convex polyhedra in three dimensional hyperbolic space $${\mathbb {H}}^3$$ . We characterize the quasiconformal deformation space of each finite convex polyhedron. As a corollary, we obtain some results on finite circle patterns in the Riemann sphere with dihedral angle $$0\le \Theta < \pi $$ . That is, for any circle pattern on $$\hat{\mathbb {C}}$$ , its quasiconformal deformation space can be naturally identified with the product of the Teichmuller spaces of its interstices.

The experimental design literature has produced a wide range of algorithms optimizing estimator variance for linear models where the design-space is finite or a convex polytope. But these methods have problems handling nonlinear constraints or constraints over multiple treatments. This paper presents Newton-type algorithms to compute exact optimal designs in models with continuous and/or discrete regressors, where the set of feasible treatments is defined by nonlinear constraints. We carry out numerical comparisons with other state-of-art methods to show the performance of this approach.

The problem of shadow is solved. It is equivalent to the problem of finding conditions for a point to belong to a generalized convex hull of a family of compact sets.

A small cover is a closed manifold Mn with a locally standard (ℤ2)n-action such that its orbit space is a simple convex polytope Pn. Let Δn denote an n-simplex and P(m) an m-gon. This paper gives formulas for calculating the number of D-J equivalent classes and equivariant homeomorphism classes of orientable small covers over the product space \(\Delta ^{n_1 } \times \Delta ^{n_2 } \times P(m)\), where n1 is odd.