Structured primal-dual interior-point methods for banded semidefinite programming

Zhiming Deng, Ming Gu, Michael L. Overton

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

Abstract

For semidefinite programming (SDP) problems, traditional primaldual interior-point methods based on conventional matrix operations have an upper limit on the problem size that the computer can handle due to memory constraints. But for a special kind of SDP problem, which is called the banded symmetric semidefinite programming (BSDP) problem, a memoryefficient algorithm, called a structured primal-dual interior-point method, can be applied. The method is based on the observation that both banded matrices and their inverses can be represented in sequentially semi-separable (SSS) form with numerical ranks equal to the half bandwidths of the banded matrices. Moreover, all computation can be done sequentially using the SSS form. Experiments of various problem sizes are performed to verify the feasibility of the proposed method.

Original languageEnglish (US)
Title of host publicationTopics in Operator Theory
Subtitle of host publicationVolume 1: Operators, Matrices and Analytic Functions - Proceedings of the 19th International Workshop on Operator Theory and its Applications, 2008
EditorsJoseph A. Ball, Vladimir Bolotnikov, Leiba Rodman, Ilya M. Spitkovsky, J. William Helton
PublisherSpringer International Publishing
Pages111-141
Number of pages31
ISBN (Print)9783034601573
DOIs
StatePublished - 2010
Event19th International Workshop on Operator Theory and its Applications, IWOTA 2008 - Williamsburg, United States
Duration: Jul 22 2008Jul 26 2008

Publication series

NameOperator Theory: Advances and Applications
Volume202
ISSN (Print)0255-0156
ISSN (Electronic)2296-4878

Other

Other19th International Workshop on Operator Theory and its Applications, IWOTA 2008
CountryUnited States
CityWilliamsburg
Period7/22/087/26/08

Keywords

  • Banded matrix
  • Interior-point method
  • Semidefinite program
  • Sequentially semi-separable

ASJC Scopus subject areas

  • Analysis

Fingerprint Dive into the research topics of 'Structured primal-dual interior-point methods for banded semidefinite programming'. Together they form a unique fingerprint.

  • Cite this

    Deng, Z., Gu, M., & Overton, M. L. (2010). Structured primal-dual interior-point methods for banded semidefinite programming. In J. A. Ball, V. Bolotnikov, L. Rodman, I. M. Spitkovsky, & J. W. Helton (Eds.), Topics in Operator Theory: Volume 1: Operators, Matrices and Analytic Functions - Proceedings of the 19th International Workshop on Operator Theory and its Applications, 2008 (pp. 111-141). (Operator Theory: Advances and Applications; Vol. 202). Springer International Publishing. https://doi.org/10.1007/978-3-0346-0158-0_7