Convergence of the mixing method

An iterative algorithm for solving diagonally constrained semidefinite programs

Master Thesis (2022)
Authors

D.S.L. Eelkema (TU Delft - Electrical Engineering, Mathematics and Computer Science)

Supervisors

D. de Laat (TU Delft - Discrete Mathematics and Optimization)

Faculty
Electrical Engineering, Mathematics and Computer Science, Electrical Engineering, Mathematics and Computer Science
Copyright
© 2022 Dominic Eelkema
More Info
expand_more
Publication Year
2022
Language
English
Copyright
© 2022 Dominic Eelkema
Graduation Date
26-09-2022
Awarding Institution
Delft University of Technology
Programme
Applied Mathematics
Faculty
Electrical Engineering, Mathematics and Computer Science, Electrical Engineering, Mathematics and Computer Science
Reuse Rights

Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.

Abstract

This thesis explores the convergence of the mixing method, an iter- ative algorithm for solving diagonally constrained semidefinite programs. In this paper we first give an exposition of the convergence proof for the mixing method based on the proof by Wang, Chang, and Kolter , where we restructure some parts of the proof and provide extra de- tails. Then we construct an example where the linear convergence rate of the mixing method is close to one when near the optimal solution. The mixing method is then compared for convergence speed to a semidefinite programming solver and gradient descent on random max-cut instances. For instances of the max-cut, it is found that the mixing method outper- forms other methods.

Files

License info not available