Develop a new rounding method for convex polytopes - GeomScale/gsoc24 GitHub Wiki

Overview

Rounding a convex polytope is crucial to improve the mixing rate of several MCMC methods that sample uniformly from the polytope. A standard method to round a convex polytope is to bring it to John position. This can be achieved by computing the maximum volume ellipsoid (MVE) of the polytope (or the John ellipsoid) and apply to it the transformation that maps the ellipsoid to the unit ball. The final polytope would be in John position.

An alternative method is to apply the fast transformation of the MVE problem in [2] to compute the minimum volume enclosing ellipsoid (MVEE) of a set of points.

Related work

There are several software packages that round polytopes by computing the John ellipsoid. The best implementations lie in PolyRound and in Cobra Matlab library. The first is a pure Python implementation of [1] and the second a pure Matlab implementation of [1]. volesti includes an open-source implementation of Khachiyan algorithm for solving the MVEE problem.

Details of your coding project

This project will develop a C++ implementation of the transformation, it will use the C++ code in volesti to solve MVEE and apply the inverse transformation to obtain the MVE and finally round the polytope. The contributor will also has to compare the new implementation with PolyRound and write an experimental report based on her/his findings.

Difficulty: Medium

Size

Medium (175 hours)

Skills

  • Required: C++, Linear Algebra, Convex optimization theory
  • Preferred: Experience with statistical or other mathematical software is a plus

Expected impact

The project will be a very useful addition to package volesti as it will crucially contribute to the implementation of efficient Rounding of convex polytopes.

Mentors

  • Apostolos Chalkis <tolis.chal at gmail.com> is a Research Engineer at Quantagonia GmbH. He is an expert in statistical software, computational geometry, and optimization, and has previous GSoC student experience (2018 & 2019) and mentoring experience with GeomScale (from 2020 to 2023).
  • 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-2017) and the R-project (2017).

Students, please contact the first and the third mentor after completing at least one of the tests below.

Tests

Students, please do one or more of the following tests before contacting the mentors above.

  • Easy: Compile and run volesti library. Run the rounding routines.
  • Medium: Compare the existing roudning C++ implementation in volesti that solves the MVEE problem of a uniformly distributed sample inside the polytope with PolyRound. The contribute could use the Python interface in dingo to access the volesti's implementation.
  • Hard: Write in your proposal a pseudocode of the transformation between MVE and MVEE problem.

For tips and references contact the Mentors!

References

[1] Y. Zhang, L. Gao, On Numerical Solution of the Maximum Volume Ellipsoid Problem, 2003.
[2] L. G. Khachiyan and M. J. Todd. On the complexity of approximating the maximal inscribed ellipsoid for a polytope, 1993.

Solutions of tests

Students, please post a link to your test results here.

  • EXAMPLE STUDENT 1 NAME, LINK TO GITHUB PROFILE, LINK TO TEST RESULTS.