2019/09/13 by Stefania Bellavia, Bellavia, Stefania, Jacek Gondzio +3 · 2 citations
Computer Science · Engineering · Mathematics · #65F10 #65F50 #90C22 #90C51 #Advanced Optimization Algorithms Research #FOS: Mathematics #Numerical Analysis (math.NA) #Optimization and Control (math.OC) #Optimization and Variational Analysis #Sparse and Compressive Sensing Techniques
paper · pdf · doi:10.48550/arxiv.1909.06099
openalex publication_date 2019/09/13 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A new relaxed variant of interior point method for low-rank semidefinite\nprogramming problems is proposed in this paper. The method is a step outside of\nthe usual interior point framework. In anticipation to converging to a low-rank\nprimal solution, a special nearly low-rank form of all primal iterates is\nimposed. To accommodate such a (restrictive) structure, the first order\noptimality conditions have to be relaxed and are therefore approximated by\nsolving an auxiliary least-squares problem. The relaxed interior point\nframework opens numerous possibilities how primal and dual approximated Newton\ndirections can be computed. In particular, it admits the application of both\nthe first- and the second-order methods in this context. The convergence of the\nmethod is established. A prototype implementation is discussed and encouraging\npreliminary computational results are reported for solving the\nSDP-reformulation of matrix-completion problems.\n