-
Notifications
You must be signed in to change notification settings - Fork 5
Volume estimation of spectrahedra
Spectrahedra are probably the most well studied shapes after
polyhedra. Spectrahedra generalize polyhedra,
in the sense that they are the intersection of the cone of positive
semidefinite matrices with an affine space.
In other words, a spectrahedron S is the feasible set
of a linear matrix inequality (see [1]). Spectrahedra are convex sets and every polytope is a spectrahedron, but not the opposite. They are the feasible regions of semidefinite programs in the way that polytopes are feasible regions of linear programs. The project is about extending volesti to support uniform sampling and volume estimation of spectrahedra.
Package volesti supports volume estimation for polytopes, providing several randomized approximation methods. The most efficient implementation employs billiard walk (uniform sampling) and a certain Multiphase Monte Carlo technique. The code of volesti is a templated C++ code and thus, it could be easily extended to estimate the volume of other convex bodies if the corresponding oracles of the additional bodies are provided. Considering spectrahedra, volesti supports exponential sampling using the exact Hamiltonian Monte Carlo sampler.
It employs Arpack library for computing eigenvalue decompositions to implement the necessary membership, boundary and reflection oracles.
The student will (a) implement billiard walk for uniform sampling from spectrahedra, (b) adjust the rounding methods for spectrahedra, (c) extend volesti to estimate volumes of spectrahedra. The programming language will be 100% C++ as the project simply extends volesti.
Since spectrahedra are closely related with semidefinite programming the project will be an important contribution to GeomScale Org. towards new randomized approximation methods for solving SDPs with sampling.
[1] Apostolos Chalkisa, Ioannis Z. Emiris, Vissarion Fisikopoulos, Panagiotis Repouskos, Elias Tsigaridas, Efficient Sampling from Feasible Sets of SDPs and Volume Approximation, 2020.
-
Apostolos Chalkis <tolis.chal at gmail.com> is a PhD student in Computer Science. His research focuses on mathematical computing, optimization and computational finance. He has previous experience in GSoC 2018 and 2019 as a student under Org.
R-project, implementing state-of-the-art algorithms for sampling from high dimensional multivariate distributions. He was GSOC mentor in three projects with Geomscale (2020). He is one of the authors ofvolesti. -
Vissarion Fisikopoulos <vissarion.fisikopoulos at gmail.com> is an international expert in mathematical software, computational geometry and optimization, and has previous GSOC mentoring experience with Boost C++ libraries (2016-2020) and the R-project (2017-2019).
-
Elias Tsigaridas <elias.tsigaridas at inria.fr> is an expert in computational nonlinear algebra and geometry with experience in mathematical software. He has contributed to the implementation, in C and C++, of several solving algorithms for various open source computer algebra libraries and has previous GSOC mentoring experience with the R-project (2019) and Geomscale (2020).
Students, please contact the first and the third mentor after completing at least one of the tests below.
Students, please do one or more of the following tests before contacting the mentors above.
- Easy: compile and run
volesti. Use the R extension to visualize sampling in a polytope. - Medium: compile the C++ code of
volestiand run the examples to sample from a spectrahedron according to the exponential distribution. - Hard: create a member function
linear_tranformit()in spectrahedron class to apply to the spectrahedron a linear transformation that is defined by a symmetric rectangular matrix.
Students, please post a link to your test results here.
- EXAMPLE STUDENT 1 NAME, LINK TO GITHUB PROFILE, LINK TO TEST RESULTS.
- Paul Barbier, GitHub, Test Results