-

 

 

 




Optimization Online





 

A relaxed interior point method for low-rank semidefinite programming problems

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 and a prototype implementation is discussed. Encouraging preliminary computational results are reported for solving large low-rank semidefinite programs.

Keywords: semidefinite programming, interior point algorithms, low rank, preconditioners

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: 09/16/2019

Modify/Update this entry


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

 

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