-
Notifications
You must be signed in to change notification settings - Fork 1
Randomized solver for Semidefinite Programs
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.
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.
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
Large (350 hours)
- Required: C++, Probability theory, Basic applied math background
- Preferred: Experience with optimization or other mathematical software is a plus
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.
-
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.
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.
Students, please post a link to your test results here.
- EXAMPLE STUDENT 1 NAME, LINK TO GITHUB PROFILE, LINK TO TEST RESULTS.