Large-Scale Semidefinite Programming via Saddle Point Mirror-Prox Algorithm

Zhaosong Lu (zhaosongisye.gatech.edu)
Arkadi Nemirovski (nemirovsie.technion.ac.il)
Renato Monteiro (monteiroisye.gatech.edu)

Abstract: In this paper, we first develop ``economical'' representations for positive semidefinitness of well-structured sparse symmetric 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 with efficiency ${\cal O}(\epsilon^{-1})$ developed in \cite{Nem}. Some numerical implementations for large-scale Lovasz capacity and MAXCUT problems are finally present.

Keywords: Semidefinite Programming, Saddle point problem, Mirror-Prox method

Category 1: Linear, Cone and Semidefinite Programming (Semi-definite Programming )

Citation: Technical report, School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, Georgia 30332, USA, November, 2004.

Download: [Postscript][PDF]

Entry Submitted: 11/12/2004
Entry Accepted: 11/12/2004
Entry Last Modified: 11/12/2004

Modify/Update this entry