{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,1,2]],"date-time":"2023-01-02T05:55:44Z","timestamp":1672638944482},"reference-count":22,"publisher":"Association for Computing Machinery (ACM)","issue":"3","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Commun. Comput. Algebra"],"published-print":{"date-parts":[[2020,9]]},"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 dimension 200. We illustrate its efficiency on various data sets.<\/jats:p>","DOI":"10.1145\/3457341.3457349","type":"journal-article","created":{"date-parts":[[2021,3,15]],"date-time":"2021-03-15T22:07:02Z","timestamp":1615846022000},"page":"114-118","update-policy":"http:\/\/dx.doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Sampling the feasible sets of SDPs and volume approximation"],"prefix":"10.1145","volume":"54","author":[{"given":"Apostolos","family":"Chalkis","sequence":"first","affiliation":[{"name":"National & Kapodistrian University of Athens, Greece"}]},{"given":"Vissarion","family":"Fisikopoulos","sequence":"additional","affiliation":[{"name":"National & Kapodistrian University of Athens, Greece"}]},{"given":"Panagiotis","family":"Repouskos","sequence":"additional","affiliation":[{"name":"National & Kapodistrian University of Athens, Greece"}]},{"given":"Elias","family":"Tsigaridas","sequence":"additional","affiliation":[{"name":"Inria Paris, IMJ-PRG, Sorbonne Universit\u00e9 and Paris Universit\u00e9"}]}],"member":"320","published-online":{"date-parts":[[2021,3,15]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.5555\/2969442.2969575"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/CDC.2004.1429653"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/CDC.2003.1272983"},{"key":"e_1_2_1_4_1","volume-title":"Practical","author":"Chalkis A.","unstructured":"A. Chalkis , I. Z. Emiris , and V. Fisikopoulos . Practical volume estimation by a new annealing schedule for cooling convex bodies, 2019 . A. Chalkis, I. Z. Emiris, and V. Fisikopoulos. Practical volume estimation by a new annealing schedule for cooling convex bodies, 2019."},{"key":"e_1_2_1_5_1","volume-title":"Sampling the feasible sets of SDPs and","author":"Chalkis T.","unstructured":"T. Chalkis , V. Fisikopoulos , P. Repouskos , and E. Tsigaridas . Sampling the feasible sets of SDPs and volume approximation. working paper or preprint, May 2020 . T. Chalkis, V. Fisikopoulos, P. Repouskos, and E. Tsigaridas. Sampling the feasible sets of SDPs and volume approximation. working paper or preprint, May 2020."},{"key":"e_1_2_1_6_1","volume-title":"Hamiltonian Monte Carlo with boundary reflections, and application to polytope","author":"Chevallier A.","year":"2018","unstructured":"A. Chevallier , S. Pion , and F. Cazals . Hamiltonian Monte Carlo with boundary reflections, and application to polytope volume calculations. Research Report RR-9222 , INRIA Sophia Antipolis , France, Nov . 2018 . A. Chevallier, S. Pion, and F. Cazals. Hamiltonian Monte Carlo with boundary reflections, and application to polytope volume calculations. Research Report RR-9222, INRIA Sophia Antipolis, France, Nov. 2018."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746563"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/s12532-015-0097-z"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1137\/080742506"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/3194656"},{"key":"e_1_2_1_11_1","first-page":"11","article-title":"Random sampling: Billiard walk algorithm","volume":"238","author":"Gryazina E.","year":"2012","unstructured":"E. Gryazina and B. Polyak . Random sampling: Billiard walk algorithm . European Journal of Operational Research , 238 , 11 2012 . E. Gryazina and B. Polyak. Random sampling: Billiard walk algorithm. European Journal of Operational Research, 238, 11 2012.","journal-title":"European Journal of Operational Research"},{"key":"e_1_2_1_12_1","volume-title":"Eigen v3","author":"Guennebaud G.","year":"2010","unstructured":"G. Guennebaud , B. Jacob , Eigen v3 , 2010 . http:\/\/eigen.tuxfamily.org. G. Guennebaud, B. Jacob, et al. Eigen v3, 2010. http:\/\/eigen.tuxfamily.org."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.1060.0194"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.5555\/3044805.3044877"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.5555\/946243.946334"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2006.28"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1080\/10618600.2013.788448"},{"key":"e_1_2_1_18_1","first-page":"02","article-title":"Some geometric results in semidefinite programming","volume":"7","author":"Ramana M.","year":"1999","unstructured":"M. Ramana and A. Goldman . Some geometric results in semidefinite programming . Journal of Global Optimization , 7 , 02 1999 . M. Ramana and A. Goldman. Some geometric results in semidefinite programming. Journal of Global Optimization, 7, 02 1999.","journal-title":"Journal of Global Optimization"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.32.6.1296"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.5555\/2464853"},{"key":"e_1_2_1_21_1","volume-title":"Geometric random walks: A survey","author":"Vempala S.","year":"2005","unstructured":"S. Vempala . Geometric random walks: A survey . Combinatorial and Computational Geometry MSRI Publications Volume , 52, 01 2005 . S. Vempala. Geometric random walks: A survey. Combinatorial and Computational Geometry MSRI Publications Volume, 52, 01 2005."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1080\/1055678031000118482"}],"container-title":["ACM Communications in Computer Algebra"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3457341.3457349","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,1]],"date-time":"2023-01-01T21:35:07Z","timestamp":1672608907000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3457341.3457349"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,9]]},"references-count":22,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2020,9]]}},"alternative-id":["10.1145\/3457341.3457349"],"URL":"http:\/\/dx.doi.org\/10.1145\/3457341.3457349","relation":{},"ISSN":["1932-2240"],"issn-type":[{"value":"1932-2240","type":"print"}],"subject":["Microbiology (medical)","Immunology","Immunology and Allergy"],"published":{"date-parts":[[2020,9]]},"assertion":[{"value":"2021-03-15","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}