# A relaxed interior point method for low-rank semidefinite programming problems with applications to matrix completion

arXiv: https://arxiv.org/abs/1909.06099 · HTML: https://mlsanity.com/paper/1909.06099/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 13 Sep 2019.

## Built on by (most cited first, 1 of 1)

- [Provably Faster Gradient Descent via Long Steps](https://mlsanity.com/paper/2307.06324/) (2023)

## Abstract (arXiv)

A new relaxed variant of interior point method for low-rank semidefinite programming problems is proposed in this paper. The method is a step outside of the usual interior point framework. 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. The convergence of the method is established. A prototype implementation is discussed and encouraging preliminary computational results are reported for solving the SDP-reformulation of matrix-completion problems.