Convergence failures of the Burer-Monteiro factorization algorithm

Brinkman, Maurits (2020) Convergence failures of the Burer-Monteiro factorization algorithm. Bachelor's Thesis, Mathematics.

Preview	Text bMATH_2020_BrinkmanM.pdf Download (2MB) | Preview
	Text toestemming.pdf Restricted to Registered users only Download (121kB)

Abstract

In recent literature, the Burer-Monteiro factorization algorithm has shown to be an efficient method to solve large scale semidefinite programs that admit a solution of low rank: instead of optimizing over a sizable matrix $X$, one splits this matrix apart into two smaller ones by factorizing $X=VV^\top$. The disadvantage of factorizing $X$ in this way is that possibly extra non-optimal second-order critical $V$'s are generated. While the article \parencite{boumal2020} shows that in many situations this downside of the Burer-Monteiro approach is benign, recently \parencite{waldspurger2019rank} determined cases for which this factorization approach leads to an incorrect solution. In this current thesis, the results of both of these papers are combined by considering a classic minimization problem concerning optimization over quadratics, known as the trust-region subproblem. In particular, Chapter \ref{chapter04} will provide two examples of how to construct the trust-region subproblem in such a way that factorizing $X=VV^\top$ is not benign, and will therefore lead to convergence failure when applying the Burer-Monteiro factorization algorithm. Both of these examples are built on a step-by-step framework for how to deliberately bring about convergence failure of the Burer-Monteiro factorization algorithm, which will be discussed in Chapter \ref{chapter03}.

Item Type:	Thesis (Bachelor's Thesis)
Supervisor name:	Waters, A.M.S. and Wubs, F.W.
Degree programme:	Mathematics
Thesis type:	Bachelor's Thesis
Language:	English
Date Deposited:	19 Nov 2020 09:54
Last Modified:	19 Nov 2020 09:54
URI:	https://fse.studenttheses.ub.rug.nl/id/eprint/23609

Actions (login required)

View Item