Speaker: Margherita Porcelli Affiliation: Università di Bologna Time: Friday, 04/06/2021, 16:00
Title: Relaxed Interior point methods for low-rank semidefinite programming problems
In this talk we will discuss a relaxed variant of interior point methods for semidefinite programming problems (SPDs). We focus on problems in which the primal variable is expected to be low-rank at optimality. Such situations are common in relaxations of combinatorial optimization problems, for example in maximum cut problems as well as in matrix completion problems. We exploit the structure of the sought solution and relax the rigid structure of IPMs for SDP. In anticipation to converging to a low-rank primal solution, a special nearly low-rank form of all primal iterates is imposed. To accommodate such a (restrictive) structure, the first order optimality conditions have to be relaxed and are therefore approximated by solving an auxiliary least-squares problem. The relaxed interior point framework opens numerous possibilities how primal and dual approximated Newton directions can be computed. In particular, it admits the application of both the first- and the second-order methods in this context. In this talk we will focus on second-order approaches and discuss the difficulties arising in the linear algebra phase. A prototype implementation is shown as well as computational results on matrix completion problems. In particular, we will consider mildly-ill conditioned and noisy random problems as well as problems arising in diverse applications as the matrix to be recovered represents city-to- city distances, a grayscale image, game parameters in a basketball tournament.
This is joint work with S. Bellavia (Unifi) and J. Gondzio (Univ. Edinburgh)
https://www.dm.unipi.it/webnew/it/seminari/relaxed-interior-point-methods-lo...
Meeting link: https://hausdorff.dm.unipi.it/b/leo-xik-xu4