-
Notifications
You must be signed in to change notification settings - Fork 3
Randomized SDP solver
The projects targets in 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 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 to day 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.
The projects will provide GeomScale with state-of-the-art randomized solver for semi-definite programming, that will comparable and in many case will be faster that 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.
Name:Rohit Email:[email protected] GitHub:https://github.com/phoenixrao885/gsoc-monte-carlo-solutions Test done :monte carlo integration -Easy,Medium,Hard,Bonus
Name: Prajwal Bagal Email: [email protected] Github: https://github.com/Prajwalbagal/GeomScaleTest
Name:Abhishek Agrawal Email:[email protected] GitHub:Easy-task: https://github.com/abhishek8764/Monte-Carlo-Integration
Name: Divesh Kuamar Email: [email protected] Task-Link(Easy Randomized LP solver): https://github.com/diveshkr-code/Geomscale_Gsoc2020`
Name: Deifilia To Email: [email protected] Task-link: (Easy and Medium of Apothesis): https://github.com/DeifiliaTo/Apothesis_gsoc
Name: Soumyajit Chakraborty Email: [email protected] Task-Link(Easy Task of Apothesis): https://github.com/soumyajit1729/Apothesis
Name: Soumyajit Chakraborty Email: [email protected] Task-Link(Medium Task of Apothesis): https://github.com/soumyajit1729/Apothesis
Name: Soumyajit Chakraborty Email: [email protected] Task-Link(Hard Task of Apothesis): https://docs.google.com/presentation/d/1mX4UA3x8cs6--aCZ_cN2ZNB6jr3eC7P5sbiEB92YEC0/edit?usp=sharing
Name:Abhishek Agrawal Email:[email protected] GitHub:Medium-task: https://github.com/abhishek8764/Monte-Carlo-Integration
Name: Alexandros Manochis, Email: [email protected], Github: https://github.com/AlexManochis/volume_approximation/tree/gsoc20, Project: A comparative study of uniform high dimensional samplers, Tests completed: Easy, Medium, Hard
Name: Sunit Gautam Email: [email protected], [email protected] GitHub: https://github.com/gsunit/Monte-Carlo-Intergration Tasks completed: Monte Carlo integration - Easy, Medium, Hard
Name: Vaibhav Thakkar
Email: [email protected]
GitHub: https://github.com/vaithak/GeomScale_LP
Tasks completed: Randomized LP - Easy, Medium, Hard
Name: Sharat Bhat Email: [email protected] Github: https://github.com/Sharat-Bhat Tasks: https://github.com/Sharat-Bhat/GSoC_volesti
Name: Kunal Katiyar Email: [email protected] GitHub: https://github.com/KunalKatiyar/GSoC_RandLP
Name: Reyan Ahmed Email: [email protected] GitHub: https://github.com/abureyanahmed/VolEsti_test
Name:Abhishek Agrawal Email:[email protected] GitHub:Easy-task: https://github.com/abhishek8764/A-comparative-study-of-uniform-high-dimensional-samplers
Name: Sushovan Haldar Email: [email protected] Github: Easy task of using volesti : https://github.com/SushovanHaldar/geomscalecodes
Name: Anastasios Sourpis Email: [email protected] Github: Apothesis : https://github.com/pithonas/Apothesis
Name: Daniel Pozo Email: [email protected] GitHub: https://github.com/danipozo/uld-test-solutions
Name: Iasonas Nikolaou Email: [email protected] GitHub: (Easy and medium task, randomized LP) https://github.com/jasonNikolaou/GeomScale_gsoc
Name: Fernando Martin Email: fdmartin92 (at) gmail (dot) com GitHub: https://github.com/fmartin92/GeomScale_MonteCarlo (All tasks corresponding to the Monte Carlo integration proposal)
Name: Marios Papachristou Email: papachristoumarios [at) gmail (dot] com GitHub: https://github.com/papachristoumarios/geomscales-challenge (All challenges for ULD)
Name: Eugenio Borghini Email: [email protected] GitHub: https://github.com/eugenusb/GeomScale_LP (Easy and medium test projects for the randomized LP solver)
Name: Muhammad Ali Nayeem Email: [email protected] GitHub: https://github.com/ali-nayeem Test: https://github.com/ali-nayeem/gsoc2020_rand_LP_solver
Name: Bychkov Andrey Email: [email protected] GitHub: https://github.com/AndreyBychkov Test: https://github.com/AndreyBychkov/LIPA (Hard for Optimization and SOS)
Name: Yuan Yuan Email: [email protected] Github:https://github.com/yzy0014 Test:https://github.com/yzy0014/GeomScale Test demo:https://rpubs.com/yzy0014/584976, https://rpubs.com/yzy0014/585064 (High dimensional sampling with applications to structural biology)
Name: Haris Zafeiropoulos Email: [email protected] Github:https://github.com/hariszaf/ Test:https://hariszaf.github.io/gsoc2020/
Name: Mokhwa Lee
Email: [email protected] OR [email protected]
Github: https://github.com/Mokhwalee
Test: https://github.com/Mokhwalee/Exercise-Gsos
( Monte Carlo - Easy, Medium, Hard, Bonus )
Name: Antonis Skarlatos
Email: [email protected]
Github: https://github.com/Hepic/
Test: https://github.com/Hepic/Monte-Carlo-integration
(Monte-Carlo-integration: easy/medium/hard/bonus Languages used: R/C++)
Name: Konstantinos Emmanouilidis
Email: [email protected]
Github: https://github.com/emmanouilidisk
Test: https://github.com/emmanouilidisk/GeomScale_challenges
(Challenges for Randomised LP Solver)
Name: Imrane Belhadia Email: [email protected] Github:https://github.com/ImraneBELH Test: https://github.com/ImraneBELH/gsocEvaluation-MonteCarlo.git (Monte Carlo)
Name: Repouskos Panagiotis Email: [email protected] Github: https://github.com/panagiotisrep/volume_approximation/tree/Optimization , https://github.com/panagiotisrep/volume_approximation/tree/SDP-cutting-plane Test: Randomized SDP solver (medium, hard)
Name: Mohammad Taufeeque
Email: [email protected]
Github: https://github.com/taufeeque9
Test: https://github.com/taufeeque9/GSoC_Randomized_SDP_Solver_Test
(Easy and hard task for Randomized SDP Solver)
Name: Bento Natura
Email: [email protected]
Github: https://github.com/platformconclude/volume_approximation/tree/spectra_sampling
Test: Randomized SDP solver (medium)
Github: https://github.com/platformconclude/simple_LP_IPM
Test: Interior point method for linear programming (IPM)
Name: Ritwik Chakraborty
Email: [email protected]
Github: https://github.com/ritwikchakraborty123
Test: :A comparative study of uniform high-dimensional samplers (medium)