Randomized solver for Semidefinite Programs

Overview

The project targets a state-of-the-art implementation for solving SDP, based on sampling and randomized tools. As we can sample points independently, this approach could have an efficient parallel implementation.

Related work

For the randomized algorithm for SDP, we will be based on [B1] and [B2] using the current sampling routines of volesti but also implementing new ones.
One of the most efficient open-source SDP solvers today is SDPA.

References:

[B1] Dabbene, Fabrizio, Pavel S. Shcherbakov, and Boris T. Polyak. A randomized cutting plane method with probabilistic geometric convergence SIAM Journal on Optimization 20.6 (2010): 3185-3207.

[B2] Adam Tauman Kalai, Santosh Vempala Simulated Annealing for Convex Optimization Mathematics of Operations Research Vol. 31, No. 2, 2006.

Details of your coding project

The project aims to two implementations of randomized algorithms from [B1], [B2] for solving semi-definite programs. There should also be a comparison with existing open-source SDP solvers like SDPA. The code will be in C++ with R interfaces using Rcpp, following volesti structure. Basic documentation for the R version is required.

Difficulty: Hard

Expected impact

The projects will provide GeomScale with a state-of-the-art randomized solver for semi-definite programming, that will be comparable and in many cases will be faster than traditional SDP solvers.

Mentors

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).
Fabrice Rouillier <fabrice.rouillier at inria.fr> is an expert in computational algebra, geometry, and mathematical software. He has contributed to the implementation of several state-of-the-art software tools for computing with intervals and polynomials.
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).

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.

Easy: compile and run volesti. Use the R extension to visualize sampling (with any sampling algorithm) in a polytope.
Medium: Extent the hit-and-run algorithm to sample from the boundary of the spectrahedron (feasible region of an SDP).
Hard: Implement an interior point algorithm for linear programming.