TY - GEN

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

AU - Deng, Zhiming

AU - Gu, Ming

AU - Overton, Michael L.

N1 - Publisher Copyright:
© 2010 Birkhäuser Verlag Basel/Switzerland.
Copyright:
Copyright 2020 Elsevier B.V., All rights reserved.

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 -