Skip to Main content Skip to Navigation
Journal articles

Sampling the feasible sets of SDPs and volume approximation

Abstract : 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.
Document type :
Journal articles
Complete list of metadata

Cited literature [55 references]  Display  Hide  Download
Contributor : Elias Tsigaridas Connect in order to contact the contributor
Submitted on : Wednesday, May 13, 2020 - 6:55:27 PM
Last modification on : Friday, August 5, 2022 - 11:59:57 AM


Files produced by the author(s)



Tolis Chalkis, Vissarion Fisikopoulos, Panagiotis Repouskos, Elias Tsigaridas. Sampling the feasible sets of SDPs and volume approximation. ACM Communications in Computer Algebra, Association for Computing Machinery (ACM), In press, ⟨10.1145/3457341.3457349⟩. ⟨hal-02572792⟩



Record views


Files downloads