Large-scale semidefinite programming via a saddle point Mirror-Prox algorithm
成果类型：
Article
署名作者：
Lu, Zhaosong; Nemirovski, Arkadi; Monteiro, Renato D. C.
署名单位：
Simon Fraser University; University System of Georgia; Georgia Institute of Technology
刊物名称：
MATHEMATICAL PROGRAMMING
ISSN/ISSBN：
0025-5610
DOI：
10.1007/s10107-006-0031-2
发表日期：
2007
页码：
211-237
关键词：
摘要：
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 O(epsilon(-1)). Implementations and some numerical results for large-scale Lovsz capacity and MAXCUT problems are finally presented.
来源URL：