Improve the Cpp implementation of rounding method in volesti library - 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 largest inscribed ellipsoid 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. 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]. This project will improve the C++ implementation of [1] in volesti library; the goal is to develop a C++ implementation as fast as PolyRound's implementation.

Related work

The volesti C++ library computes the John ellipsoid by implementing in C++ (using Eigen library) the optimization method in [1]. However, this implementation is orders of magnitude slower than PolyRound or Cobra as it lacks vectorized and optimized computations.

Details of your coding project

The contributor will have to discuss with the mentors and find together the parts of the code that can be improved and/or optimized. Then, she/he will develop a new C++ implementation of [1]. The contributor will also compare her/his implementation against PolyRound and will write an experimental report with her/his findings.

This project is marked as medium (175 hours). However, the mentors are open to discuss with the contributors how it can be extended to a large project (350 hours).

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 mentors 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 C++ implementation of [1] in volesti with PolyRound. The contribute could use the Python interface in dingo to access the volesti's implementation.
  • Hard: Find at least two parts in the C++ implementation in volesti that can be improved/optimized and write in your report how are you going to do it.

For tips and references contact the Mentors!

References

[1] Yin Zhang, Liyan Gao, On Numerical Solution of the Maximum Volume Ellipsoid Problem, 2003.

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.