Efficient Sampling from Feasible Sets of SDPs and Volume Approximation

We present algorithmic, complexity, and implementation results on the problem of sampling points from a spectrahedron, that is the feasible region of a semidefinite program. Our main tool is geometric random walks. We analyze the arithmetic and bit complexity of certain primitive geometric operations that are based on the algebraic properties of spectrahedra and the polynomial eigenvalue problem. This study leads to the implementation of a broad collection of random walks for sampling from spectrahedra that experimentally show faster mixing times than methods currently employed either in theoretical studies or in applications, including the popular family of Hit-and-Run walks. The different random walks offer a variety of advantages , thus allowing us to efficiently sample from general probability distributions, for example the family of log-concave distributions which arise in numerous applications. We focus on two major applications of independent interest: (i) approximate the volume of a spectrahedron, and (ii) compute the expectation of functions coming from robust optimal control. We exploit efficient linear algebra algorithms and implementations to address the aforemen-tioned computations in very high dimension. In particular, we provide a C++ open source implementation of our methods that scales efficiently, for the first time, up to dimension 200. We illustrate its efficiency on various data sets.

Mots clés

Spectahedron Semidefinite-programming Sampling Random walk Polynomial eigenvalue problem Volume approximation Optimization

Domaines

Calcul formel [cs.SC] Logiciel mathématique [cs.MS] Optimisation et contrôle [math.OC] Géométrie algorithmique [cs.CG]

Fichier principal

spectra-vol-j (1).pdf (830.27 Ko)

2dexample1.png (4.84 Ko)

2dexample2.png (5.81 Ko)

boltz3.png (63.83 Ko)

boltzmann.png (66.32 Ko)

boltzmann2.png (72.69 Ko)

elliptope.png (132.12 Ko)

error001_d_equal_m.png (22.23 Ko)

hmc_hnr_boltz.png (73.13 Ko)

intersectionexample.png (64.17 Ko)

means.png (97.28 Ko)

reflectionsBilliard.png (53.56 Ko)

reflectionsHMC.png (59.94 Ko)

spectra-vol-j.bbl (11.21 Ko)

spectra-vol-j.log (59.46 Ko)

spectra-vol-j.pdf (837.93 Ko)

spectrahedron2.jpeg (5.41 Ko)

stds.png (115.2 Ko)

time_equal_d_m_001.png (27.16 Ko)

time_fixedd_001.png (23.36 Ko)

uniform.png (85.42 Ko)

uniform2.png (83.43 Ko)

uniform3.png (81.58 Ko)

Origine : Fichiers produits par l'(les) auteur(s)

Elias Tsigaridas : Connectez-vous pour contacter le contributeur

https://inria.hal.science/hal-02953124

Soumis le : mardi 29 septembre 2020-21:35:51

Dernière modification le : mercredi 3 avril 2024-14:02:03

Archivage à long terme le : mercredi 30 décembre 2020-19:20:35

Dates et versions

hal-02953124 , version 1 (29-09-2020)

hal-02953124 , version 2 (08-10-2020)

Identifiants

HAL Id : hal-02953124 , version 1

Citer

Apostolos Chalkis, Ioannis Emiris, Vissarion Fisikopoulos, Panagiotis Repouskos, Elias Tsigaridas. Efficient Sampling from Feasible Sets of SDPs and Volume Approximation. 2020. ⟨hal-02953124v1⟩

Exporter

BibTeX XML-TEI Dublin Core DC Terms EndNote DataCite

135 Consultations

207 Téléchargements