Skip to content

Improve the Cpp implementation of rounding method in volesti library

Jump to bottom
Apostolos Chalkis edited this page Feb 9, 2024 · 8 revisions

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).

Size: Medium (150 hours)
Difficulty: Medium

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 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 of volesti.

  • 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.
Clone this wiki locally