TY - JOUR

T1 - Large-scale semidefinite programming via a saddle point Mirror-Prox algorithm

AU - Lu, Zhaosong

AU - Nemirovski, Arkadi

AU - Monteiro, Renato D.C.

PY - 2007/3/1

Y1 - 2007/3/1

N2 - In this paper, we first demonstrate that positive semidefiniteness of a large well-structured sparse symmetric matrix can be represented via positive semidefiniteness of a bunch of smaller matrices linked, in a linear fashion, to the matrix. We derive also the "dual counterpart" of the outlined representation, which expresses the possibility of positive semidefinite completion of a well-structured partially defined symmetric matrix in terms of positive semidefiniteness of a specific bunch of fully defined submatrices of the matrix. Using the representations, we then reformulate well-structured large-scale semidefinite problems into smooth convex-concave saddle point problems, which can be solved by a Prox-method developed in [6] with efficiency script O sign (ε-1). Implementations and some numerical results for large-scale Lovász capacity and MAXCUT problems are finally presented.

AB - In this paper, we first demonstrate that positive semidefiniteness of a large well-structured sparse symmetric matrix can be represented via positive semidefiniteness of a bunch of smaller matrices linked, in a linear fashion, to the matrix. We derive also the "dual counterpart" of the outlined representation, which expresses the possibility of positive semidefinite completion of a well-structured partially defined symmetric matrix in terms of positive semidefiniteness of a specific bunch of fully defined submatrices of the matrix. Using the representations, we then reformulate well-structured large-scale semidefinite problems into smooth convex-concave saddle point problems, which can be solved by a Prox-method developed in [6] with efficiency script O sign (ε-1). Implementations and some numerical results for large-scale Lovász capacity and MAXCUT problems are finally presented.

KW - Mirror-Prox method

KW - Saddle point problem

KW - Semidefinite programming

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

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

U2 - 10.1007/s10107-006-0031-2

DO - 10.1007/s10107-006-0031-2

M3 - Article

AN - SCOPUS:33846655826

VL - 109

SP - 211

EP - 237

JO - Mathematical Programming

JF - Mathematical Programming

SN - 0025-5610

IS - 2-3

ER -