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

Zhiming Deng; Ming Gu; Michael L. Overton

doi:10.1007/978-3-0346-0158-0_7

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

Zhiming Deng, Ming Gu, Michael L. Overton

Research output: Chapter in Book/Report/Conference proceeding › Conference 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 language	English (US)
Title of host publication	Topics in Operator Theory
Subtitle of host publication	Volume 1: Operators, Matrices and Analytic Functions - Proceedings of the 19th International Workshop on Operator Theory and its Applications, 2008
Editors	Joseph A. Ball, Vladimir Bolotnikov, Leiba Rodman, Ilya M. Spitkovsky, J. William Helton
Publisher	Springer International Publishing
Pages	111-141
Number of pages	31
ISBN (Print)	9783034601573
DOIs	https://doi.org/10.1007/978-3-0346-0158-0_7
State	Published - 2010
Event	19th International Workshop on Operator Theory and its Applications, IWOTA 2008 - Williamsburg, United States Duration: Jul 22 2008 → Jul 26 2008

Publication series

Name	Operator Theory: Advances and Applications
Volume	202
ISSN (Print)	0255-0156
ISSN (Electronic)	2296-4878

Other

Other	19th International Workshop on Operator Theory and its Applications, IWOTA 2008
Country/Territory	United States
City	Williamsburg
Period	7/22/08 → 7/26/08

Keywords

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

ASJC Scopus subject areas

Analysis

Access to Document

10.1007/978-3-0346-0158-0_7

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

Structured primal-dual interior-point methods for banded semidefinite programming. / Deng, Zhiming; Gu, Ming; Overton, Michael L.
Topics in Operator Theory: Volume 1: Operators, Matrices and Analytic Functions - Proceedings of the 19th International Workshop on Operator Theory and its Applications, 2008. ed. / Joseph A. Ball; Vladimir Bolotnikov; Leiba Rodman; Ilya M. Spitkovsky; J. William Helton. Springer International Publishing, 2010. p. 111-141 (Operator Theory: Advances and Applications; Vol. 202).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Deng, Z, Gu, M & Overton, ML 2010, Structured primal-dual interior-point methods for banded semidefinite programming. in JA Ball, V Bolotnikov, L Rodman, IM Spitkovsky & JW 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. Operator Theory: Advances and Applications, vol. 202, Springer International Publishing, pp. 111-141, 19th International Workshop on Operator Theory and its Applications, IWOTA 2008, Williamsburg, United States, 7/22/08. https://doi.org/10.1007/978-3-0346-0158-0_7

Deng Z, Gu M, Overton ML. Structured primal-dual interior-point methods for banded semidefinite programming. In Ball JA, Bolotnikov V, Rodman L, Spitkovsky IM, Helton JW, editors, Topics in Operator Theory: Volume 1: Operators, Matrices and Analytic Functions - Proceedings of the 19th International Workshop on Operator Theory and its Applications, 2008. Springer International Publishing. 2010. p. 111-141. (Operator Theory: Advances and Applications). doi: 10.1007/978-3-0346-0158-0_7

Deng, Zhiming ; Gu, Ming ; Overton, Michael L. / Structured primal-dual interior-point methods for banded semidefinite programming. Topics in Operator Theory: Volume 1: Operators, Matrices and Analytic Functions - Proceedings of the 19th International Workshop on Operator Theory and its Applications, 2008. editor / Joseph A. Ball ; Vladimir Bolotnikov ; Leiba Rodman ; Ilya M. Spitkovsky ; J. William Helton. Springer International Publishing, 2010. pp. 111-141 (Operator Theory: Advances and Applications).

@inproceedings{0e9f460b557148a4b26871f9501c94f4,

title = "Structured primal-dual interior-point methods for banded semidefinite programming",

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.",

keywords = "Banded matrix, Interior-point method, Semidefinite program, Sequentially semi-separable",

author = "Zhiming Deng and Ming Gu and Overton, {Michael L.}",

note = "Publisher Copyright: {\textcopyright} 2010 Birkh{\"a}user Verlag Basel/Switzerland. Copyright: Copyright 2020 Elsevier B.V., All rights reserved.; 19th International Workshop on Operator Theory and its Applications, IWOTA 2008 ; Conference date: 22-07-2008 Through 26-07-2008",

year = "2010",

doi = "10.1007/978-3-0346-0158-0_7",

language = "English (US)",

isbn = "9783034601573",

series = "Operator Theory: Advances and Applications",

publisher = "Springer International Publishing",

pages = "111--141",

editor = "Ball, {Joseph A.} and Vladimir Bolotnikov and Leiba Rodman and Spitkovsky, {Ilya M.} and Helton, {J. William}",

booktitle = "Topics in Operator Theory",

}

TY - GEN

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

AU - Deng, Zhiming

AU - Gu, Ming

AU - Overton, Michael L.

PY - 2010

Y1 - 2010

N2 - 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.

AB - 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.

KW - Banded matrix

KW - Interior-point method

KW - Semidefinite program

KW - Sequentially semi-separable

UR - http://www.scopus.com/inward/record.url?scp=84975702018&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84975702018&partnerID=8YFLogxK

U2 - 10.1007/978-3-0346-0158-0_7

DO - 10.1007/978-3-0346-0158-0_7

M3 - Conference contribution

AN - SCOPUS:84975702018

SN - 9783034601573

T3 - Operator Theory: Advances and Applications

SP - 111

EP - 141

BT - Topics in Operator Theory

A2 - Ball, Joseph A.

A2 - Bolotnikov, Vladimir

A2 - Rodman, Leiba

A2 - Spitkovsky, Ilya M.

A2 - Helton, J. William

PB - Springer International Publishing

T2 - 19th International Workshop on Operator Theory and its Applications, IWOTA 2008

Y2 - 22 July 2008 through 26 July 2008

ER -

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

Abstract

Publication series

Other

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this