Search

We present a product formula for the initial parts of the sparse resultant associated with an arbitrary family of supports, generalizing a previous result by Sturmfels. This allows to compute the homogeneities and degrees of this sparse resultant, and its evaluation at systems of Laurent polynomials with smaller supports. We obtain an analogous product formula for some of the initial parts of the principal minors of the Sylvester-type square matrix associated with a mixed subdivision of a polytope. Applying these results, we prove that under suitable hypothesis, the sparse resultant can be computed as the quotient of the determinant of such a square matrix by one of its principal minors. This generalizes the classical Macaulay formula for the homogeneous resultant and confirms a conjecture of Canny and Emiris., Author(s): Carlos D'Andrea [sup.1] [sup.2] , Gabriela Jeronimo [sup.3] [sup.4] [sup.5] , Martín Sombra [sup.1] [sup.2] [sup.6] Author Affiliations: (1) grid.5841.8, 0000 0004 1937 0247, Departament de Matemàtiques i Informàtica, [...]

We initiate a study of the Euclidean distance degree in the context of sparse polynomials. Specifically, we consider a hypersurface [Formula omitted] defined by a polynomial f that is general given its support, such that the support contains the origin. We show that the Euclidean distance degree of [Formula omitted] equals the mixed volume of the Newton polytopes of the associated Lagrange multiplier equations. We discuss the implication of our result for computational complexity and give a formula for the Euclidean distance degree when the Newton polytope is a rectangular parallelepiped., Author(s): P. Breiding [sup.1] , F. Sottile [sup.2] , J. Woodcock [sup.2] Author Affiliations: (1) grid.419532.8, Max-Planck-Institute for Mathematics in the Sciences Leipzig, , Inselstr. 22, 04103, Leipzig, Germany (2) [...]

It is well known that the gradient descent algorithm converges linearly when applied to a strongly convex function with Lipschitz gradient. In this case, the algorithm's rate of convergence is determined by the condition number of the function. In a similar vein, it has been shown that a variant of the Frank-Wolfe algorithm with away steps converges linearly when applied to a strongly convex function with Lipschitz gradient over a polytope. In a nice extension of the unconstrained case, the algorithm's rate of convergence is determined by the product of the condition number of the function and a certain condition number of the polytope. We shed new light on the latter type of polytope conditioning. In particular, we show that previous and seemingly different approaches to define a suitable condition measure for the polytope are essentially equivalent to each other. Perhaps more interesting, they can all be unified via a parameter of the polytope that formalizes a key premise linked to the algorithm's linear convergence. We also give new insight into the linear convergence property. For a convex quadratic objective, we show that the rate of convergence is determined by a condition number of a suitably scaled polytope. Funding: J. Pena's research has been supported by the National Science Foundation [Grant CMMI-1534850]. Keywords: linear convergence * Frank--Wolfe * polytope conditioning, 1. Introduction A standard result in convex optimization states that the gradient descent algorithm converges linearly to the minimizer of a strongly convex function with Lipschitz gradient. For a related [...]

The distortion varieties of a given projective variety are parametrized by duplicating coordinates and multiplying them with monomials. We study their degrees and defining equations. Exact formulas are obtained for the case of one-parameter distortions. These are based on Chow polytopes and Gröbner bases. Multi-parameter distortions are studied using tropical geometry. The motivation for distortion varieties comes from multi-view geometry in computer vision. Our theory furnishes a new framework for formulating and solving minimal problems for camera models with image distortion., Author(s): Joe Kileel [sup.1] , Zuzana Kukelova [sup.2] , Tomas Pajdla [sup.3] , Bernd Sturmfels [sup.1] Author Affiliations: (Aff1) 0000 0001 2181 7878, grid.47840.3f, Department of Mathematics, University of California, [...]

Let S [??] [{0,1}.sup.n] and R be any polytope contained in [[0,1].sup.n] with R [??] [{0,1}.sup.n] = S. We prove that R has bounded Chvatal-Gomory rank (CG-rank) provided that S has bounded notch and bounded gap, where the notch is the minimum integer p such that all p-dimensional faces of the 0/1-cube have a nonempty intersection with S, and the gap is a measure of the size of the facet coefficients of conv(S). Let H[[bar.S]] denote the subgraph of the n-cube induced by the vertices not in S. We prove that if H[[bar.S]] does not contain a subdivision of a large complete graph, then the notch and the gap are bounded. By our main result, this implies that the CG-rank of R is bounded as a function of the treewidth of H[[bar.S]]. We also prove that if S has notch 3, then the CG-rank of R is always bounded. Both results generalize a recent theorem of Cornuejols and Lee [Cornuejols G, Lee D (2016) On some polytopes contained in the 0,1 hypercube that have a small Chvatal rank. Louveaux Q, Skutella M, eds. Proc. 18th Internat. Conf. Integer Programming Combinatorial Optim., IPCO '16 (Springer International, Cham, Switzerland), 300-311], who proved that the CG-rank is bounded by a constant if the treewidth of H[[bar.S]] is at most 2. Funding: The first, second, and third authors were supported by European Research Council Con-solidator [Grant 615640-ForEFront]. Keywords: polyhedra * cutting-planes * graphs * Integer programming, 1. Introduction Given a polytope R [??] [R.sup.n], its first Chvdtal-Gomory-closure (CG-closure) is defined as R':= {x [epsilon] [R.sup.n]: [c.sup.[tau]]x [greater than or equal to] [[miny.sup.[member of]R] [c.sup.[tau]]y] [for all]c[member [...]

Let G = (V, E) be a graph. The matching polytope of G, denoted by P(G), is the convex hull of the incidence vectors of all matchings in G. As proved by Edmonds [10] [Edmonds J (1965) Maximum matching and a polyhedron with 0, 1-vertices, J. Res. Nat. Bur. Standards Sect. B 69(1-2):125-130.], P(G) is determined by the following linear system [pi](G): x(e) [greater than or equal to] 0 for each e [member of] E; x{[delta]{[upsilon])) [less than or equal to] 1 for each [upsilon] [member of] V; and x{E{U]) [less than or equal to] [[1/2]U] for each U [??] V with |U| odd. In 1978, Cunningham and Marsh [6] [Cunningham W, Marsh A (1978) A primal algorithm for optimum matching. Balinski ML, Hoffman AJ, eds. Polyhedral combinatorics. Mathematical Programming Studies, Vol. 8 (Springer, Berlin), 50-72.] strengthened this theorem by showing that [pi](G) is always totally dual integral. In 1984, Edmonds and Giles [11] [Edmonds J, Giles R (1984) Total dual integrality of linear inequality systems. Progress in Combinatorial Optimization (Academic Press, Toronto), 117-129.] initiated the study of graphs G for which [pi]{G) is box-totally dual integral. In this paper, we present a structural characterization of all such graphs, and develop a general and powerful method for establishing box-total dual integrality. Funding: The first author is supported in part by the National Science Foundation [Grant DMS-1500699] and the third author is supported in part by the Research Grants Council of Hong Kong. Supplemental Material: The online appendix is available at https://doi.org/10.1287/moor.2017.0852. Keywords: matching * polytope * linear system * box-total dual integrality * signed graph, 1. Introduction Let Ax [less than or equal to] b, X [greater than or equal to] 0 be a rational linear system and let P denote the polyhedron {x: Ax [...]

Abstract. We introduce a novel scheme based on a blending of Fourier-Motzkin elimination (FME) and adjustable robust optimization techniques to compute the maximum volume inscribed ellipsoid (MVE) in a polytopic [...]

We present a new approach for constructing polytope Lyapunov functions for continuous-time linear switching systems (LSS). This allows us to decide the stability of LSS and to compute the Lyapunov exponent with a good precision in relatively high dimensions. The same technique is also extended for stabilizability of positive systems by evaluating a polytope concave Lyapunov function ('antinorm') in the cone. The method is based on a suitable discretization of the underlying continuous system and provides both a lower and an upper bound for the Lyapunov exponent. The absolute error in the Lyapunov exponent computation is estimated from above and proved to be linear in the dwell time. The practical efficiency of the new method is demonstrated in several examples and in the list of numerical experiments with randomly generated matrices of dimensions up to 10 (for general linear systems) and up to 100 (for positive systems). The development of the method is based on several theoretical results proved in the paper: the existence of monotone invariant norms and antinorms for positively irreducible systems, the equivalence of all contractive norms for stable systems and the linear convergence theorem., Author(s): Nicola Guglielmi [sup.1] [sup.2] , Linda Laglia [sup.1] , Vladimir Protasov [sup.3] Author Affiliations: (1) 0000 0004 1757 2611grid.158820.6Dipartimento di Ingegneria Scienze Informatiche e Matematica, University of L'Aquila, Via [...]

Consistent reconstruction is a method for producing an estimate of a signal if one is given a collection of noisy linear measurements [Formula omitted], , that have been corrupted by i.i.d. uniform noise . We prove mean-squared error bounds for consistent reconstruction when the measurement vectors are drawn independently at random from a suitable distribution on the unit-sphere . Our main results prove that the mean-squared error (MSE) for consistent reconstruction is of the optimal order under general conditions on the measurement vectors. We also prove refined MSE bounds when the measurement vectors are i.i.d. uniformly distributed on the unit-sphere and, in particular, show that in this case, the constant [Formula omitted] is dominated by , the cube of the ambient dimension. The proofs involve an analysis of random polytopes using coverage processes on the sphere., Author(s): Alexander M. Powell[sup.1] , J. Tyler Whitehouse[sup.2] Author Affiliations: (1) Department of Mathematics, Vanderbilt University, 37240, Nashville, TN, USA (2) Quantitative Scientific Solutions, LLC, Washington, DC, USA Introduction We [...]

Icosahedral symmetry is ubiquitous in nature, and understanding possible deformations of structures exhibiting it can be critical in determining fundamental properties. In this work we present a framework for generating and representing deformations of such structures while the icosahedral symmetry is preserved. This is done by viewing the points of an orbit of the icosahedral group as vertices of an icosahedral polytope. Contraction of the orbit is defined as a continuous variation of the coordinates of the dominant point--which specifies the orbit in an appropriate basis--toward smaller positive values. Exact icosahedral symmetry is maintained at any stage of the contraction. All icosahedral orbits or polytopes can be built by successive contractions. This definition of contraction is general and can be applied to orbits of any finite reflection group. PACS Nos.: 61.05.-a, 61.18.-j, 61.48.-c. La symetrie icosaedrique est omnipresente dans la nature et la comprehension des deformations possibles des structures est critique pour determiner les proprietes fondamentales. Nous presentons ici un cadre de travail pour generer et representer les deformations de ce type de structures, tout en preservant la symetrie icosaedrique. Ceci est fait en prenant des points d'une orbite du groupe icosaedre comme des sommets d'un polytope icosaedrique. La contraction de l'orbite est definie par des variations continues des coordonnees du point dominant--ceci positionne l'orbite dans une base appropriee--vers de plus petites valeurs positives. Nous maintenons la symetrie icosaedrique a toutes les etapes de la contraction. Toutes les orbites/polytopes icosaedriques peuvent etre construites par contractions successives. Cette definition de la contraction est generale et peut etre appliquee aux orbites de n'importe quel groupe de reflexion fini. [Traduit par la Redaction], 1. Introduction In the optimization of self-assembled structures in nature, the formation of regular polyhedrals is a ubiquitously encountered strategy. Examples of this include the formation of hollow-cage fullerenes [1], [...]

In recent years, open problem that found the number of integral points on a polytope in high dimension space are appeared. There are many reasons for considering structures in higher dimension, some of them practical and some are aesthetic. Our main purpose is to introduce a procedure in which it makes the operation of computing the factoring of N = p.q as easier as the direct computation fast, therefore, two approaches are working on for finding the number of integral points make benefit from the concept of the Ehrhart polynomial and its application on integral points on a polytope. Polytopes which are taken is the cube, and a map is making between a ball and a polytope in four dimension, then discuss the relation between the number of integral points on a cube from dimension one to n dimension. We found a relation between the radius of the ball, the edge of the cube and the dimension together with Pascal triangle. Two different methods are used, but in this paper we present only one of them and the other we are working on. Keywords Polytope, lattice points. 2000 Mathematics Subject Classification: 52B20, llP21, [section]1. Introduction and preliminaries A wide variety of pure and applied mathematics involve the problem of counting the number of integral points (lattice points) inside a region in space. Applications [...]

Provan and Billera defined the notion of weak k-decomposability for pure simplicial complexes in the hopes of bounding the diameter of convex polytopes. They showed the diameter of a weakly [...]

Let A be a d x n matrix and T = [T.sup.n-1] be the standard simplex in [R.sup.n]. Suppose that d and n are both large and comparable: d [approximately equal to] [delta]n, [delta] [member of] (0, 1). We count the faces of the projected simplex AT when the projector A is chosen uniformly at random from the Grassmann manifold of d-dimensional orthoprojectors of [R.sup.n]. We derive [rho]N([delta]) > 0 with the property that, for any [rho] < [rho]N([delta]), with overwhelming probability for large d, the number of k-dimensional faces of P = AT is exactly the same as for T, for 0 [less than or equal to] k [less than or equal to] [rho]d. This implies that P = is [??][rho]d[??]-neighborly, and its skeleton Skel[??][rho]d[??](P) is combinatorially equivalent to Skel[??][rho]d[??](T). We also study a weaker notion of neighborliness where the numbers of k-dimensional faces [f.sub.k](P) [greater than or equal to] [f.sub.k](T)(1 - [epsilon]). Vershik and Sporyshev previously showed existence of a threshold [rho]vs([delta]) > 0 at which phase transition occurs in k/d. We compute and display [rho]vs and compare with [rho]N. Corollaries are as follows. (1) The convex hull of n Gaussian samples in [R.sup.d], with n large and proportional to d, has the same k-skeleton as the (n - 1) simplex, for k < [rho]N (d/n)d(1 + op(1)). (2) There is a 'phase transition' in the ability of linear programming to find the sparsest nonnegative solution to systems of underdetermined linear equations. For most systems having a solution with fewer than [rho]vs(d/ n)d(1 + o(1)) nonzeros, linear programming will find that solution. neighborly polytopes | convex hull of Gaussian sample | underdetermined systems of linear equations | uniformly distributed random projections | phase transitions

Consider an underdetermined system of linear equations y = Ax with known y and d x n matrix A. We seek the nonnegative x with the fewest nonzeros satisfying y = Ax. In general, this problem is NP-hard. However, for many matrices A there is a threshold phenomenon: if the sparsest solution is sufficiently sparse, it can be found by linear programming. We explain this by the theory of convex polytopes. Let [a.sub.j] denote the jth column of A, 1 [less than or equal to] j [less than or equal to] n, let [a.sub.0] = 0 and P denote the convex hull of the [a.sub.j]. We say the polytope P is outwardly k-neighborly if every subset of k vertices not including 0 spans a face of P. We show that outward k-neighborliness is equivalent to the statement that, whenever y = Ax has a nonnegative solution with at most k nonzeros, it is the nonnegative solution to y = Ax having minimal sum. We also consider weak neighborliness, where the overwhelming majority of k-sets of [a.sub.j]s not containing 0 span a face of P. This implies that most nonnegative vectors x with k nonzeros are uniquely recoverable from y = Ax by linear programming. Numerous corollaries follow by invoking neighborliness results. For example, for most large n by 2n underdetermined systems having a solution with fewer nonzeros than roughly half the number of equations, the sparsest solution can be found by linear programming. neighborly polytopes | cyclic polytopes | combinatorial optimization | convex hull of Gaussian samples | positivity constraints in ill-posed problems

Bacterial nitrous oxide ([N.sub.2]O) respiration depends on the polytopic membrane protein NosR for the expression of [N.sub.2]O reductase from the nosZ gene. We constructed His-tagged NosR and purified it from detergent-solubilized membranes of Pseudomonas stutzeri ATCC 14405. NosR is an iron-sulfur flavoprotein with redox centers positioned at opposite sides of the cytoplasmic membrane. The flavin cofactor is presumably bound covalently to an invariant threonine residue of the periplasmic domain. NosR also features conserved [CX.sub.3]CP motifs, located C-terminally of the transmembrane helices TM4 and TM6. We genetically manipulated nosR with respect to these different domains and putative functional centers and expressed recombinant derivatives in a nosR null mutant, MK418nosR::Tn5. NosR's function was studied by its effects on [N.sub.2]O respiration, NosZ synthesis, and the properties of purified NosZ proteins. Although all recombinant NosR proteins allowed the synthesis of NosZ, a loss of [N.sub.2]O respiration was observed upon deletion of most of the periplasmic domain or of the C-terminal parts beyond TM2 or upon modification of the cysteine residues in a highly conserved motif, CGWLCP, following TM4. Nonetheless, NosZ purified from the recombinant NosR background exhibited in vitro catalytic activity. Certain NosR derivatives caused an increase in NosZ of the spectral contribution from a modified catalytic Cu site. In addition to its role in nosZ expression, NosR supports in vivo [N.sub.2]O respiration. We also discuss its putative functions in electron donation and redox activation.

The relaxation of the matching polytope defined by the non-negativity and degree constraints is considered. Given an undirected graph on n nodes and the corresponding relaxation of the matching polytope, it is proven that (n/2) iterations of the Lovasz-Schrijver semidefinite lifting prototype are required to derive the matching polytope, in th worst case. It is also demonstrated that (n/2) iterations of the algorithm are enough.

The anion (Cd(S(O)CPh)3)- exhibits polytopal isomerism around the CdS3 skeleton which exhibit both planar and pyramidal geometries in the rhombohedral form of the anion. The structural characterizations of the anion and its monoclinic as well as rhombohedral modifications are presented. Planar-pyramidal isomerism among three-coordinate species is a very rare occurrence.

A projection polytope-based strategy for solving the projection problems of maximization/minimization of shadow area and their higher-dimensional analogues demonstrates the significant role of the diameter/width in simplex optimization. The minimization of the shadow volume is solvable in polynomial time whereas maximization turns out to be intractable/NP-hard. The minimization process exploits the fact that the projection polytope of a parallelotope is itself a parallelotope. An algorithm determines the minimum projection of a simplex in O(n(super 2)) steps.

The geometric dissection of four-dimensional polytopes is investigated. The task involves two steps: first, determine which dissections are possible, and second, find the possible dissections. Mathematical recreations enthusiasts can try creating semi-regular polytopes from regular versions using the expansion and contraction processes, with techniques described by Stott (1910).

There are just three regular polytopes in Euclidean (n > 4)-space. We calculate their dimensions, including the distance from the centroid to the periphery in a random direction - that of a white-Gaussian-noise vector. As n [approaches] [infinity], this distance becomes very predictable. It differs from the distance near which almost all of the volume and surface of the polytope lie. Index Terms - Geometric codes, regular polytopes, Voronoi polytopes, noise immunity.

Several characteristics of Lemke paths on a simple labelled d-dimensional polytope P with 2d facets are investigated to verify whether the d-step conjecture for linear programming is true. The latter holds that any two vertices of such polytopes can be linked by a path with maximum length d in the graph of P. To this end, several negative results are given, including the exponential growth of the shortest Lemke path lengths connecting two vertices.

In this paper, the problem of constructing Lyapunov functions for a class of nonlinear dynamical systems is considered. The problem of constructing a Lyapunov function is reduced to the construction of a polytope satisfying some conditions. A generalization of the concept of sector condition is proposed so that it makes possible to evaluate a given nonlinear function by using a set of piecewise-linear functions. This improvement reduces the conservatism in the stability analysis of nonlinear systems very much. Two algorithms to construct such polytopes are proposed, and two examples are shown to demonstrate the usefulness of the obtained results.

A study presents a class of valid inequalities and a class of facets for the cut polytope of the complete graph. The former class is proven to include other known classes of valid inequalities such as triangle, hypermetric and cycle types. Large classes of facets can also be defined by specializing some of the parameters, making each class contain at least (n/3)super(n/3) facets, with n >= 10 denoting the number of vertices. Additionally, their respective separation problems are shown to be equivalent to a minimum weight spanning tree problem, thus making them polynomially solvable.

The stability of linear systems subject to possibly fast time-varying uncertainties is analyzed. A method is developed to compute the upper bound of uncertainty size allowed for retaining quadratic stability. The algorithm consists of a two-level optimization. The inner level of the algorithm consists of choosing an extremum among a finite number of values. It is proved that although the outer level of the algorithm is a nonconvex optimization problem, no local minimum distinct from the global minimum can exist. An illustrative example is presented.

A graph with a defined edge set, partitions and multicuts is established. A study analyzes the polytopes that are actually the convex hulls of the incidence vectors of all multicuts bounded by the graph. Clique-web inequalities, a large class of inequalities, are introduced to the polytopes and characterized. General facet manipulation techniques such as collapsing, lifting and node splitting are afterwards used to demonstrate the existence of clique-web facethood for the inequalities.

The Asymmetric Traveling Salesman (ATS) and the Fixed Outdegree 1-Arborescence (FDA) polytopes are studied. The FDA polytope becomes the 1-arborescence polytope when F = phi, and becomes the ATS polytope when F is the entire node set. Classes of valid FDA inequalities are derived and proven to be facet defining by using a theorem that proves a facet defining inequality for the ATS polytope also holds true for the FDA polytope. A canonical form then demonstrates the distinctiveness of each polytope's facets from the other as well as generally with other known facets.

A class of valid inequalities for the Symmetric Traveling Salesman Polytope is defined on the sets of handles and teeth that are now nested, not of tree structure and no longer restricted to the value one. This new family, the largest known of its kinds so far generalizes the previously defined path, comb, clique tree and hyperstar inequalities and contains some bipartition inqualities as well. The binested inequalities present in this polytope and its graphical relaxation are proven valid. Conditions and conjectures are presented to make this family facet inducing for this specific case.

Suppose that we are given a polytope of real polynomials. We shall present a result which will allow us to construct the smallest set of regions in the complex plane which characterizes its zero location.

The pseudoboundary of a polytope is defined to be the set of all polynomials in the polytope each of which has at least one zero on the imaginary axis. It is proven that a "section" of the pseudoboundary corresponding to any frequency "[[Omega].sub.0]" is itself a polytope whose vertices lie in the exposed two-dimensional faces of the given polytope. A simple algorithm is proposed to generate all the vertex polynomials of any section of the pseudoboundary of a polytope. An illustrative example is given.

This note presents some strict positive realness results of a family of polytopic plants. More specifically, we shall show that the strict positive real property of such a family of plants can be ascertained from its vertex plants.

We present a polyhedral study of the complementarity knapsack problem. Traditionally, complementarity constraints are modeled by introducing auxiliary binary variables and additional constraints, and the model is tightened by introducing [...]

A new sufficient condition for a polytope of matrices to be Hurwitz-stable is presented. The stability is a consequence of the existence of a parameter-dependent quadratic Lyapunov function, which is assured by a certain linear constraint for generating extreme matrices of the polytope. The condition can be regarded as a duality of the known extreme point result on quadratic stability of matrix polytopes, where a fixed quadratic Lyapunov function plays the role. The obtained results are applied to a polytope of second-degree polynomials for illustration. Index Terms--Hurwitz-stability, parameter-dependent Lyapunov function, polytope of matrices, quadratic stability.

In this paper we present a tour of the symmetric traveling salesman polytope, focusing on inequalities that can be defined on sets of nodes. Most widely known inequalities are of [...]