  


Exploiting Sparsity for SemiAlgebraic Set Volume Computation
Matteo Tacchi(matteo.tacchilaas.fr) Abstract: We provide a systematic deterministic numerical scheme to approximate the volume (i.e. the Lebesgue measure) of a basic semialgebraic set whose description follows a sparsity pattern. As in previous works (without sparsity), the underlying strategy is to consider an infinitedimensional linear program on measures whose optimal value is the volume of the set. This is a particular instance of a generalized moment problem which in turn can be approximated as closely as desired by solving a hierarchy of semidefinite relaxations of increasing size. The novelty with respect to previous work is that by exploiting the sparsity pattern we can provide a sparse formulation for which the associated semidefinite relaxations are of much smaller size. In addition, we can decompose the sparse relaxations into completely decoupled subproblems of smaller size, and in some cases computations can be done in parallel. To the best of our knowledge, it is the first contribution that exploits sparsity for volume computation of semialgebraic sets which are possibly highdimensional and/or nonconvex and/or nonconnected. Keywords: Category 1: Linear, Cone and Semidefinite Programming (Semidefinite Programming ) Category 2: Convex and Nonsmooth Optimization (Convex Optimization ) Citation: Download: [PDF] Entry Submitted: 02/06/2019 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  