Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userComputing gaussian & exponential measures of semi-algebraic sets
186
0
0.0
(
0
)
Authors
Jean-Bernard Lasserre
Ask ChatGPT about the research
No Arabic abstract
We provide a numerical scheme to approximate as closely as desired the Gaussian or exponential measure $mu(om)$ of (not necessarily compact) basic semi-algebraic sets$omsubsetR^n$. We obtain two monotone (non increasing and non decreasing) sequences of upper and lower bounds $(overline{omega}_d)$, $(underline{omega}_d)$, $dinN$, each converging to $mu(om)$ as $dtoinfty$. For each $d$, computing $overline{omega}_d$ or $underline{omega}_d$reduces to solving a semidefinite program whose size increases with $d$. Some preliminary (small dimension) computational experiments are encouraging and illustrate thepotential of the method. The method also works for any measure whose moments are known and which satisfies Carlemans condition.
rate research
Read More
Let $Ssubset R^n$ be a compact basic semi-algebraic set defined as the real solution set of multivariate polynomial inequalities with rational coefficients. We design an algorithm which takes as input a polynomial system defining $S$ and an integer $pgeq 0$ and returns the $n$-dimensional volume of $S$ at absolute precision $2^{-p}$.Our algorithm relies on the relationship between volumes of semi-algebraic sets and periods of rational integrals. It makes use of algorithms computing the Picard-Fuchs differential equation of appropriate periods, properties of critical points, and high-precision numerical integration of differential equations.The algorithm runs in essentially linear time with respect to~$p$. This improves upon the previous exponential bounds obtained by Monte-Carlo or moment-based methods. Assuming a conjecture of Dimca, the arithmetic cost of the algebraic subroutines for computing Picard-Fuchs equations and critical points is singly exponential in $n$ and polynomial in the maximum degree of the input.
Many algorithms for determining properties of real algebraic or semi-algebraic sets rely upon the ability to compute smooth points. Existing methods to compute smooth points on semi-algebraic sets use symbolic quantifier elimination tools. In this paper, we present a simple algorithm based on computing the critical points of some well-chosen function that guarantees the computation of smooth points in each connected compact component of a real (semi)-algebraic set. Our technique is intuitive in principal, performs well on previously difficult examples, and is straightforward to implement using existing numerical algebraic geometry software. The practical efficiency of our approach is demonstrated by solving a conjecture on the number of equilibria of the Kuramoto model for the $n=4$ case. We also apply our method to design an efficient algorithm to compute the real dimension of (semi)-algebraic sets, the original motivation for this research.
Let $k$ be a field of characteristic zero containing all roots of unity and $K=k((t))$. We build a ring morphism from the Grothendieck group of semi-algebraic sets over $K$ to the Grothendieck group of motives of rigid analytic varieties over $K$. It extend the morphism sending the class of an algebraic variety over $K$ to its cohomological motive with compact support. We show that it fits inside a commutative diagram involving Hrushovski and Kazhdans motivic integration and Ayoubs equivalence between motives of rigid analytic varieties over $K$ and quasi-unipotent motives over $k$ ; we also show that it satisfies a form of duality. This allows us to answer a question by Ayoub, Ivorra and Sebag about the analytic Milnor fiber.
Given any arbitrary semi-algebraic set $X$, any two points in $X$ may be joined by a piecewise $C^2$ path $gamma$ of shortest length. Suppose $mathcal{A}$ is a semi-algebraic stratification of $X$ such that each component of $gamma cap mathcal{A}$ is either a singleton or a real analytic geodesic segment in $mathcal{A}$, the question is whether $gamma cap mathcal{A}$ has at most finitely many such components. This paper gives a semi-algebraic stratification, in particular a cell decomposition, of a real semi-algebraic set in the plane whose open cells have this finiteness property. This provides insights for high dimensional stratifications of semi-algebraic sets in connection with geodesics.
We present a theorem of Sard type for semi-algebraic set-valued mappings whose graphs have dimension no larger than that of their range space: the inverse of such a mapping admits a single-valued analytic localization around any pair in the graph, for a generic value parameter. This simple result yields a transparent and unified treatment of generic properties of semi-algebraic optimization problems: typical semi-algebraic problems have finitely many critical points, around each of which they admit a unique active manifold (analogue of an active set in nonlinear optimization); moreover, such critical points satisfy strict complementarity and second-order sufficient conditions for optimality are indeed necessary.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
