Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userApproximating the maximum of a polynomial over a polytope: Handelman decomposition and continuous generating functions
184
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
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.
rate research
Read More
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 of 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 approximations 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 nonconvex 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 differential 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.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
