Modified interior-point method for large-And-sparse low-rank semidefinite programs

Richard Y. Zhang, Javad Lavaei

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Semidefinite programs (SDPs) are powerful theoretical tools that have been studied for over two decades, but their practical use remains limited due to computational difficulties in solving large-scale, realistic-sized problems. In this paper, we describe a modified interior-point method for the efficient solution of large-And-sparse low-rank SDPs, which finds applications in graph theory, approximation theory, control theory, sum-of-squares, etc. Given that the problem data is large-And-sparse, conjugate gradients (CG) can be used to avoid forming, storing, and factoring the large and fully-dense interior-point Hessian matrix, but the resulting convergence rate is usually slow due to ill-conditioning. Our central insight is that, for a rank-k, size-n SDP, the Hessian matrix is ill-conditioned only due to a rank-nk perturbation, which can be explicitly computed using a size-n eigendecomposition. We construct a preconditioner to 'correct' the low-rank perturbation, thereby allowing preconditioned CG to solve the Hessian equation in a few tens of iterations. This modification is incorporated within SeDuMi, and used to reduce the solution time and memory requirements of large-scale matrix-completion problems by several orders of magnitude.

Original languageEnglish (US)
Title of host publication2017 IEEE 56th Annual Conference on Decision and Control, CDC 2017
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages5640-5647
Number of pages8
ISBN (Electronic)9781509028733
DOIs
StatePublished - Jan 18 2018
Externally publishedYes
Event56th IEEE Annual Conference on Decision and Control, CDC 2017 - Melbourne, Australia
Duration: Dec 12 2017Dec 15 2017

Publication series

Name2017 IEEE 56th Annual Conference on Decision and Control, CDC 2017
Volume2018-January

Other

Other56th IEEE Annual Conference on Decision and Control, CDC 2017
Country/TerritoryAustralia
CityMelbourne
Period12/12/1712/15/17

ASJC Scopus subject areas

  • Decision Sciences (miscellaneous)
  • Industrial and Manufacturing Engineering
  • Control and Optimization

Fingerprint

Dive into the research topics of 'Modified interior-point method for large-And-sparse low-rank semidefinite programs'. Together they form a unique fingerprint.

Cite this