Newton Polytopes and Relative Entropy Optimization

Foundations of Computational Mathematics - Certifying function nonnegativity is a ubiquitous problem in computational mathematics, with especially notable applications in optimization. We study the...     

Counting Affine Roots of Polynomial Systems via Pointed Newton Polytopes

We give a new upper bound on the number of isolated roots of a polynomial system. Unlike many previous bounds, our bound can also be restricted to different open subsets of affine space. Our methods give significantly sharper bounds than the classical Bézout theorems and further generalize the mixed volume root counts discovered in the late 1970s. We also give a complete combinatorial classification of the subsets of coefficients whose genericity guarantees that our bound is actually an exact root count in affine space. Our results hold over any algebraically closed field.     

Smooth Fano Polytopes Arising from Finite Partially Ordered Sets

Gorenstein Fano polytopes arising from finite partially ordered sets will be introduced. Then we study the problem of which partially ordered sets yield smooth Fano polytopes.     

Explicit Constructions of Centrally Symmetric k-Neighborly Polytopes and Large Strictly Antipodal Sets

We present explicit constructions of centrally symmetric $2$ -neighborly $d$ -dimensional polytopes with about $3^{d/2}\approx (1.73)^d$ vertices and of centrally symmetric $k$ -neighborly $d$ -polytopes with about $2^{{3d}/{20k^2 2^k}}$ vertices. Using this result, we construct for a fixed $k\ge 2$ and arbitrarily large $d$ and $N$ , a centrally symmetric $d$ -polytope with $N$ vertices that has at least $\left( 1-k^2\cdot (\gamma _k)^d\right) \genfrac(){0.0pt}{}{N}{k}$ faces of dimension $k-1$ , where $\gamma _2=1/\sqrt{3}\approx 0.58$ and $\gamma _k = 2^{-3/{20k^2 2^k}}$ for $k\ge 3$ . Another application is a construction of a set of $3^{\lfloor d/2 -1\rfloor }-1$ points in $\mathbb R ^d$ every two of which are strictly antipodal as well as a construction of an $n$ -point set (for an arbitrarily large $n$ ) in $\mathbb R ^d$ with many pairs of strictly antipodal points. The two latter results significantly improve the previous bounds by Talata, and Makai and Martini, respectively.     

重根牛顿变换的Julia集

作者分析了重根牛顿变换的Julia集理论,并利用迭代法构造了标准牛顿变换、松弛牛顿变换和重根牛顿变换的Julia集．采用实验数学方法,作者得出如下结论:(1)函数f(z)=zα(zβ-1) 的三种牛顿变换Julia集的中心为原点目具有β倍的旋转对称性; (2)三种牛顿变换Julia集的重根吸引域对α具有敏感的依赖性;(3)由于的零点是松弛牛顿变换的中性或斥性不动点,故松弛牛顿变换的Julia集中不存在单根吸引域;(4)由于∞点不是重根牛顿变换的不动点,故重根牛顿变换的Julia集中多为重根和单根吸引域;(5)重根牛顿法受计算误差影响最小,松弛牛顿法次之, 标准牛顿法最大．     

Newton and Quasi-Newton Methods for Normal Maps with Polyhedral Sets

This paper is devoted to a search for a guaranteed counterpart of the stochastic Kalman filter. We study the guaranteed filtering of a linear system such that the phase state and external disturbance form a vector subject to an ellipsoidal bound. This seemingly exotic setup can be justified by an analogy with the observation of Gaussian processes. Unfortunately, the resulting guaranteed filtering supplies us an ellipsoid approximating the localization domain for the state vector, but not the localization domain itself, and turns out to be more difficult compared to the Kalman filter. Our main results consist of an explicit evaluation of the Hamiltonians. In principle, this permits us to write explicitly the equations of the guaranteed filter.     

Prodsimplicial-Neighborly Polytopes

Simultaneously generalizing both neighborly and neighborly cubical polytopes, we introduce PSN polytopes: their k-skeleton is combinatorially equivalent to that of a product of r simplices.     

Mixed Polytopes

Abstract. Goodey and Weil have recently introduced the notions of translation mixtures of convex bodies and of mixed convex bodies. By a new approach, a simpler proof for the existence of the mixed polytopes is given, and explicit formulae for their vertices and edges are obtained. Moreover, the theory of mixed bodies is extended to more than two convex bodies. The paper concludes with the proof of an inclusion inequality for translation mixtures of convex bodies, where the extremal case characterizes simplices.     

Mixed Polytopes

   Abstract. Goodey and Weil have recently introduced the notions of translation mixtures of convex bodies and of mixed convex bodies. By a new approach, a simpler proof for the existence of the mixed polytopes is given, and explicit formulae for their vertices and edges are obtained. Moreover, the theory of mixed bodies is extended to more than two convex bodies. The paper concludes with the proof of an inclusion inequality for translation mixtures of convex bodies, where the extremal case characterizes simplices.     

Polytopes in Arrangements

Consider an arrangement of n hyperplanes in \real ^d . Families of convex polytopes whose boundaries are contained in the union of the hyperplanes are the subject of this paper. We aim to bound their maximum combinatorial complexity. Exact asymptotic bounds were known for the case where the polytopes are cells of the arrangement. Situations where the polytopes are pairwise openly disjoint have also been considered in the past. However, no nontrivial bound was known for the general case where the polytopes may have overlapping interiors, for d>2 . We analyze families of polytopes that do not share vertices. In \real ³ we show an O(k ^1/3 n ² ) bound on the number of faces of k such polytopes. We also discuss worst-case lower bounds and higher-dimensional versions of the problem. Among other results, we show that the maximum number of facets of k pairwise vertex-disjoint polytopes in \real ^d is Ω(k ^1/2 n ^d/2 ) which is a factor of away from the best known upper bound in the range n ^d-2 ≤ k ≤ n ^d . The case where 1≤ k ≤ n ^d-2 is completely resolved as a known Θ(kn) bound for cells applies here. Received September 20, 1999, and in revised form March 10, 2000. Online publication September 22, 2000.     

Mixed Fibre Polytopes

With a slight modification of the original definition by Billera and Sturmfels, it is shown that the theory of fibre polytopes extends to one of mixed fibre polytopes. Indeed, there is a natural surjective homomorphism from the space of tensor weights on polytopes in a euclidean space V to the corresponding space of such weights on fibre polytopes in a subspace of V. Moreover, these homomorphisms compose in the correct way; this is in contrast to the original situation of the fibre polytope construction.     

Decomposability of Polytopes

A known characterization of the decomposability of polytopes is reformulated in a way which may be more computationally convenient, and a more transparent proof is given. New sufficient conditions for indecomposability are then deduced, and illustrated with some examples.     

Totally Splittable Polytopes

A split of a polytope is a (necessarily regular) subdivision with exactly two maximal cells. A polytope is totally splittable if each triangulation (without additional vertices) is a common refinement of splits. This paper establishes a complete classification of the totally splittable polytopes.     

Decomposition of Polytopes and Polynomials

Motivated by a connection with the factorization of multivariate polynomials, we study integral convex polytopes and their integral decompositions in the sense of the Minkowski sum. We first show that deciding decomposability of integral polygons is NP-complete then present a pseudo-polynomial-time algorithm for decomposing polygons. For higher-dimensional polytopes, we give a heuristic algorithm which is based upon projections and uses randomization. Applications of our algorithms include absolute irreducibility testing and factorization of polynomials via their Newton polytopes. Received December 2, 1999, and in revised form November 6, 2000. Online publication May 4, 2001.     

Linear Networks and Convex Polytopes

It is shown that the set [G,] of immersed linear networks in that are parallel to a given immersed linear network and have the same boundary as is a convex polyhedral subset of the configuration space of movable vertices of the graph G. The dimension of [G,] is calculated, and the number of its maximal faces is estimated. As an application, the spaces of all locally minimal and weighted minimal networks with fixed boundary and topology in are described. Bibliography: 21 titles.     

Neighborly Cubical Polytopes

Neighborly cubical polytopes exist: for any n≥ d≥ 2r+2 , there is a cubical convex d -polytope C _d ⁿ whose r -skeleton is combinatorially equivalent to that of the n -dimensional cube. This solves a problem of Babson, Billera, and Chan. Kalai conjectured that the boundary of a neighborly cubical polytope C _d ⁿ maximizes the f -vector among all cubical (d-1) -spheres with 2 ⁿ vertices. While we show that this is true for polytopal spheres if n≤ d+1 , we also give a counterexample for d=4 and n=6 . Further, the existence of neighborly cubical polytopes shows that the graph of the n -dimensional cube, where n\ge5 , is ``dimensionally ambiguous' in the sense of Grünbaum. We also show that the graph of the 5 -cube is ``strongly 4 -ambiguous.' In the special case d=4 , neighborly cubical polytopes have f ₃ =(f ₀ /4) log ₂ (f ₀ /4) vertices, so the facet—vertex ratio f ₃ /f ₀ is not bounded; this solves a problem of Kalai, Perles, and Stanley studied by Jockusch. Received December 30, 1998. Online publication May 15, 2000.     

Matroid Polytopes and their Volumes

We express the matroid polytope P _M of a matroid M as a signed Minkowski sum of simplices, and obtain a formula for the volume of P _M . This gives a combinatorial expression for the degree of an arbitrary torus orbit closure in the Grassmannian Gr _k,n . We then derive analogous results for the independent set polytope and the underlying flag matroid polytope of M. Our proofs are based on a natural extension of Postnikov’s theory of generalized permutohedra.     

Cutting Polytopes and Flag f-Vectors

We show how the flag f -vector of a polytope changes when cutting off any face, generalizing work of Lee for simple polytopes. The result is in terms of explicit linear operators on cd-polynomials. Also, we obtain the change in the flag f -vector when contracting any face of the polytope. Received July 13, 1998, and in revised form April 14, 1999.     

All Polytopes Are Quotients, and Isomorphic Polytopes Are Quotients by Conjugate Subgroups

In this paper it is shown that any (abstract) polytope is a quotient of a regular polytope by some subgroup N of the automorphism group W of , and also that isomorphic polytopes are quotients of by conjugate subgroups of W . This extends work published in 1980 by Kato, who proved these results for a restricted class of polytopes which he called ``regular'. The methods used here are more elementary, and treat the problem in a purely nongeometric manner. Received January 27, 1997, and in revised form October 1, 1997.