Sampling the feasible sets of SDPs and volume approximation - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Article Dans Une Revue ACM Communications in Computer Algebra Année : 2021

Sampling the feasible sets of SDPs and volume approximation

Résumé

We present algorithmic, complexity, and implementation results on the problem of sampling points in the interior and the boundary of a spectrahedron, that is the feasible region of a semidefinite program. Our main tool is random walks. We define and analyze a set of primitive geometric operations that exploits the algebraic properties of spectrahedra and the polynomial eigenvalue problem, and leads to the realization of a broad collection of efficient random walks. We demonstrate random walks that experimentally show faster mixing time than the ones used previously for sampling from spectrahedra in theory or applications, for example Hit and Run. Consecutively, the variety of random walks allows us to sample from general probability distributions, for example the family of log-concave distributions which arise frequently in numerous applications. We apply our tools to compute (i) the volume of a spectrahedron and (ii) the expectation of functions coming from robust optimal control. We provide a C++ open source implementation of our methods that scales efficiently up to to dimension 200. We illustrate its efficiency on various data sets.
Fichier principal
Vignette du fichier
spectra-vol.pdf (1.36 Mo) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-02572792 , version 1 (13-05-2020)

Identifiants

Citer

Tolis Chalkis, Vissarion Fisikopoulos, Panagiotis Repouskos, Elias Tsigaridas. Sampling the feasible sets of SDPs and volume approximation. ACM Communications in Computer Algebra, inPress, ⟨10.1145/3457341.3457349⟩. ⟨hal-02572792⟩
175 Consultations
345 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More