اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدPolyhedral Analysis of Symmetric Multilinear Polynomials over Box Constraints
99
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
It is well-known that the convex and concave envelope of a multilinear polynomial over a box are polyhedral functions. Exponential-sized extended and projected formulations for these envelopes are also known. We consider the convexification question for multilinear polynomials that are symmetric with respect to permutations of variables. Such a permutation-invariant structure naturally implies a quadratic-sized extended formulation for the envelopes through the use of disjunctive programming. The optimization and separation problems are answered directly without using this extension. The problem symmetry allows the optimization and separation problems to be answered directly without using any extension. It also implies that permuting the coefficients of a core set of facets generates all the facets. We provide some necessary conditions and some sufficient conditions for a valid inequality to be a core facet. These conditions are applied to obtain envelopes for two classes: symmetric supermodular functions and multilinear monomials with reflection symmetry, thereby yielding alternate proofs to the literature. Furthermore, we use constructs from the reformulation-linearization-technique to completely characterize the set of points lying on each facet.
قيم البحث
اقرأ أيضاً
For a d-dimensional polyhedral complex P, the dimension of the space of piecewise polynomial functions (splines) on P of smoothness r and degree k is given, for k sufficiently large, by a polynomial f(P,r,k) of degree d. When d=2 and P is simplicial,
Alfeld and Schumaker determined a formula for all three coefficients of f. However, in the polyhedral case, no formula is known. Using localization techniques and specialized dual graphs associated to codimension--2 linear spaces, we obtain the first three coefficients of f(P,r,k), giving a complete answer when d=2.
The construction of a simplicial complex given by polyhedral joins (introduced by Anton Ayzenberg), generalizes Bahri, Bendersky, Cohen and Gitlers $J$-construction and simplicial wedge construction. This article gives a cohomological decomposition o
f a polyhedral product over a polyhedral join for certain families of pairs of simplicial complexes. A formula for the Hilbert-Poincar{e} series is given, which generalizes Ayzenbergs formula for the moment-angle complex.
The regularity theory for variational inequalities over polyhedral sets developed in a series of papers by Robinson, Ralph and Dontchev-Rockafellar in the 90s has long become classics of variational analysis. But in the available proofs of almost all
main results, fairly nontrivial as they are, techniques of variational analysis do not play a significant part. In the paper we develop a new approach that allows to obtain some generalizations of the the mentioned results without invoking anything beyond elementary geometry of convex polyhedra and some basic facts of the theory of metric regularity.
Polyhedral products were defined by Bahri, Bendersky, Cohen and Gitler, to be spaces obtained as unions of certain product spaces indexed by the simplices of an abstract simplicial complex. In this paper we give a very general homotopy theoretic cons
truction of polyhedral products over arbitrary pointed posets. We show that under certain restrictions on the poset $calp$, that include all known cases, the cohomology of the resulting spaces can be computed as an inverse limit over $calp$ of the cohomology of the building blocks. This motivates the definition of an analogous algebraic construction - the polyhedral tensor product. We show that for a large family of posets, the cohomology of the polyhedral product is given by the polyhedral tensor product. We then restrict attention to polyhedral posets, a family of posets that include face posets of simplicial complexes, and simplicial posets, as well as many others. We define the Stanley-Reisner ring of a polyhedral poset and show that, like in the classical cases, these rings occur as the cohomology of certain polyhedral products over the poset in question. For any pointed poset $calp$ we construct a simplicial poset $s(calp)$, and show that if $calp$ is a polyhedral poset then polyhedral products over $calp$ coincide up to homotopy with the corresponding polyhedral products over $s(calp)$.
We present a deterministic algorithm which computes the multilinear factors of multivariate lacunary polynomials over number fields. Its complexity is polynomial in $ell^n$ where $ell$ is the lacunary size of the input polynomial and $n$ its number o
f variables, that is in particular polynomial in the logarithm of its degree. We also provide a randomized algorithm for the same problem of complexity polynomial in $ell$ and $n$. Over other fields of characteristic zero and finite fields of large characteristic, our algorithms compute the multilinear factors having at least three monomials of multivariate polynomials. Lower bounds are provided to explain the limitations of our algorithm. As a by-product, we also design polynomial-time deterministic polynomial identity tests for families of polynomials which were not known to admit any. Our results are based on so-called Gap Theorem which reduce high-degree factorization to repeated low-degree factorizations. While previous algorithms used Gap Theorems expressed in terms of the heights of the coefficients, our Gap Theorems only depend on the exponents of the polynomials. This makes our algorithms more elementary and general, and faster in most cases.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
