Multiscale Methods for Semidefinite Programming

In this thesis, we examine two problems of convex relaxation. The first problem involves the recovery of the ground-state energy in the Ferromagnetic Ising model with localized corruption patterns in the interaction matrix. The second problem focuses on the recovery of the ground-state energy for the quantum many-body problem. For both cases, we propose relaxations that result in semidefinite programming (SDP) problems, which can be solved in polynomial time. Additionally, we explore the inherent properties of the matrix variables from the SDP problems, and impose further structures on them to reduce the computation time for the problems. Furthermore, we conducted numerical experiments in various scenarios to compare the objective values from our relaxed problems to the true ground-state energy, to assess the exactness of our relaxations.