Optimization Online


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

Stefania Bellavia (stefania.bellavia***at***unifi.it)
Jacek Gondzio (j.gondzio***at***ed.ac.uk)
Margherita Porcelli (margherita.porcelli***at***unibo.it)

Abstract: 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.

Keywords: semidefinite programming, interior point algorithms, low rank, matrix-completion problems

Category 1: Linear, Cone and Semidefinite Programming (Semi-definite Programming )

Category 2: Nonlinear Optimization (Nonlinear Systems and Least-Squares )

Citation: arXiv:1909.06099

Download: [PDF]

Entry Submitted: 09/16/2019
Entry Accepted: 09/16/2019
Entry Last Modified: 03/26/2021

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society