اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدApproximating the maximum of a polynomial over a polytope: Handelman decomposition and continuous generating functions
184
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
We investigate a way to approximate the maximum of a polynomial over a polytopal region by using Handelmans polynomial decomposition and continuous multivariate generating functions. The maximization problem is NP-hard, but our approximation methods will run in polynomial time when the dimension is fixed.
قيم البحث
اقرأ أيضاً
We provide a characterization of the set of real-valued functions that can be the value function of some polynomial game. Specifically, we prove that a function $u : dR to dR$ is the value function of some polynomial game if and only if $u$ is a continuous piecewise rational function.
Consider a subshift over a finite alphabet, $Xsubset Lambda^{mathbb Z}$ (or $XsubsetLambda^{mathbb N_0}$). With each finite block $BinLambda^k$ appearing in $X$ we associate the empirical measure ascribing to every block $CinLambda^l$ the frequency o
f occurrences of $C$ in $B$. By comparing the values ascribed to blocks $C$ we define a metric on the combined space of blocks $B$ and probability measures $mu$ on $X$, whose restriction to the space of measures is compatible with the weak-$star$ topology. Next, in this combined metric space we fix an open set $mathcal U$ containing all ergodic measures, and we say that a block $B$ is ergodic if $Binmathcal U$. In this paper we prove the following main result: Given $varepsilon>0$, every $xin X$ decomposes as a concatenation of blocks of bounded lengths in such a way that, after ignoring a set $M$ of coordinates of upper Banach density smaller than $varepsilon$, all blocks in the decomposition are ergodic. The second main result concerns subshifts whose set of ergodic measures is closed. We show that, in this case, no matter how $xin X$ is partitioned into blocks (as long as their lengths are sufficiently large and bounded), after ignoring a set $M$ of upper Banach density smaller than $varepsilon$, all blocks in the decomposition are ergodic. The first half of the paper is concluded by examples showing, among other things, that the small set $M$, in both main theorems, cannot be avoided. The second half of the paper is devoted to generalizing the two main results described above to subshifts $XsubsetLambda^G$ with the action of a countable amenable group $G$. The role of long blocks is played by blocks whose domains are members of a Fo lner sequence while the decomposition of $xin X$ into blocks (of which majority is ergodic) is obtained with the help of a congruent system of tilings.
We present a method to over-approximate reachable tubes over compact time-intervals, for linear continuous-time, time-varying control systems whose initial states and inputs are subject to compact convex uncertainty. The method uses numerical approxi
mations of transition matrices, is convergent of first order, and assumes the ability to compute with compact convex sets in finite dimension. We also present a variant that applies to the case of zonotopic uncertainties, uses only linear algebraic operations, and yields zonotopic over-approximations. The performance of the latter variant is demonstrated on an example.
This work studies the problem of maximizing a higher degree real homogeneous multivariate polynomial over the unit sphere. This problem is equivalent to finding the leading eigenvalue of the associated symmetric tensor of higher order, which is nonco
nvex and NP-hard. Recent advances show that semidefinite relaxation is quite effective to find a global solution. However, the solution methods involve full/partial eigenvalue decomposition during the iterates, which heavily limits its efficiency and scalability. On the other hand, for odd degree (odd order) cases, the order has to be increased to even, which potentially reduces the efficiency. To find the global solutions, instead of convexifying the problem, we equivalently reformulate the problem as a nonconvex matrix program based on an equivalence property between symmetric rank-1 tensors and matrices of any order, which is a generalization of the existing results. The program is directly solved by a vanilla alternating direction method, which only involves the computation of leading eigenvalue/singular value of certain matrices, benefiting from the special structure of the program. Although being nonconvex, under certain hypotheses, it is proved that the algorithm converges to a leading eigenvalue of the associated tensor. Numerical experiments on different classes of tensors demonstrate that the proposed approach has a significant improvement in efficiency and scalability, while it can keep the effectiveness of semidefinite relaxation as much as possible. For instance, the proposed method finds the leading eigenpair of a third-order 500 dimensional Hilbert tensor in a personal computer within 100 seconds.
Let $Bbbk$ be a field and let $I$ be a monomial ideal in the polynomial ring $Q=Bbbk[x_1,ldots,x_n]$. In her thesis, Taylor introduced a complex which provides a finite free resolution for $Q/I$ as a $Q$-module. Later, Gemeda constructed a differenti
al graded structure on the Taylor resolution. More recently, Avramov showed that this differential graded algebra admits divided powers. We generalize each of these results to monomial ideals in a skew polynomial ring $R$. Under the hypothesis that the skew commuting parameters defining $R$ are roots of unity, we prove as an application that as $I$ varies among all ideals generated by a fixed number of monomials of degree at least two in $R$, there is only a finite number of possibilities for the Poincar{e} series of $Bbbk$ over $R/I$ and for the isomorphism classes of the homotopy Lie algebra of $R/I$ in cohomological degree larger or equal to two.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
