Google Summer of Code 2025

Project Title: Randomized SDP solver and improved preprocessing

Organization: Geomscale, a NumFOCUS affiliated project

Mentors: Vissarion Fisikopoulos, Apostolos Chalkis, Zafeirakis Zafeirakopoulos

Project Overview

During Google Summer of Code 2025, I contributed to enhancing the randomized semidefinite programming (SDP) solver —built on simulated annealing and reflective hamiltonian monte carlo (R-HMC)— within the VolEsti library. Motivated by the work of Chalkis et al., my project focused on improving the solver’s numerical stability and computational efficiency. In addition, I implemented support for sparse SDP problems and incorporated a preprocessing framework based on a facial reduction algorithm. Together, these enhancements improved the solver’s robustness and performance, significantly extending VolEsti’s capabilities in semidefinite programming. Benchmark evaluations demonstrated promising results, with performance comparable to established interior-point-based solvers such as SDPA, on specific test cases.

Summary of Contributions

1. Eigenvalue Problem Stability Improvements

A major part of my work focused on eigenvalue problems, particularly involving spectrahedron membership, intersection, and reflection operations. Specifically, I focused on resolving several issues present in the previous implementation, regarding numerical linear algebra (NLA) operations, leading to substantial performance gains. Although the initial errors make it difficult to quantify the exact speedup, the improved SDP solver now performs comparably to SDPA, a well-established open-source project. It is important to note that more capabilities need to be added to VolEsti in order to accurately compare the two solvers. For more details, please refer to the relevant pull requests linked below.

2. Simulated Annealing and Reflective-HMC Enhancements

I also implemented improvements to the simulated annealing algorithm and R-HMC. Specifically, I added:

Velocity persistence: This technique works particularly well due to the convexity of our feasible set, allowing for more efficient exploration of the solution space
Adaptive step sizing: This helps maintain a low reflection rate, which is crucial since reflections are computationally expensive operations, and high trajectory completion of steps, reducing boundary hits and improving overall efficiency
Metropolis filtering: This addition ensures that the Markov chain converges to the desired distribution, enhancing the quality of the solutions obtained

3. Sparse SDP Support

Beyond the core solver improvements, my work included adding comprehensive support for sparse SDP problems. The sparse representation significantly reduces memory usage and computational overhead, enabling the solver to tackle larger problem instances effectively.

4. Preprocessing Integration

Finally, I integrated Sieve-SDP, a preprocessing algorithm designed to reduce the size of SDP problems before solving them. This integration allows VolEsti to preprocess problems effectively, leading to significant performance gains, in problems with specific structure. The implementation was based on the original MATLAB code provided by the authors of Sieve-SDP.

Results and Impact

The enhancements enable the solver to:

Faster, more robustly, and more accurately solve semidefinite programming problems
Handle larger problem instances with reduced memory requirements through sparse representations
Efficiently preprocess problems, reducing the discrepancy of problems with specific structure through Sieve-SDP, leading to performance gains
Demonstrate the potential of simulated annealing and R-HMC techniques for SDPs, providing a viable alternative to traditional interior-point methods commonly used in most SDP solvers.

The demonstrated performance of those techniques provide practical evidence for their effectiveness in solving SDPs. Furthermore, the addition of sparse SDP support is particularly impactful, as sparsity naturally arises in many real-world applications—such as control theory, combinatorial optimization, and signal processing—thereby broadening the applicability and usefulness of the VolEsti library.

Challenges Faced

The project presented several significant challenges that required careful problem-solving:

Navigating a Large Codebase: One of the initial hurdles was understanding the relatively large existing codebase. It was challenging to determine what needed to be modified versus what should remain unchanged, requiring substantial time investment in code analysis.
Eigenvalue Problems: The eigenvalue problems proved more complex than initially anticipated. It took considerable time to fully comprehend the issues and identify the most efficient approaches.
Optimizing R-HMC for Specific Problem Structure: A particularly interesting challenge was adapting Reflective Hamiltonian Monte Carlo (R-HMC) to work optimally for our specific optimization problem. Since we don’t actually want to uniformly sample from the feasible area—our problem has a very specific structure—it was crucial to understand how to leverage this structure to our advantage for better performance.

What I Learned

This project deepened my understanding of:

Semidefinite programming theory and algorithms
Numerical linear algebra
Markov Chain Monte Carlo methods
Advanced C++ programming techniques
Open-source development workflows

Last but not least, I gained valuable experience in collaborating with mentors and contributing to an open-source project, which has been immensely rewarding both professionally and personally.

Acknowledgments

I would like to thank my mentors for their guidance and support throughout GSoC 2025.

Links

back