Optimization Online


First- and Second-Order Methods for Semidefinite Programming

Renato D.C. Monteiro (monteiro***at***isye.gatech.edu)

Abstract: In this paper, we survey the most recent methods that have been developed for the solution of semidefinite programs. We first concentrate on the methods that have been primarily motivated by the interior point (IP) algorithms for linear programming, putting special emphasis in the class of primal-dual path-following algorithms. We also survey methods that have been developed for solving large-scale SDP problems. These include first-order nonlinear programming (NLP) methods and more specialized path-following IP methods which use the (preconditioned) conjugate gradient or residual scheme to compute the Newton direction and the notion of matrix completion to exploit data sparsity.

Keywords: Semidefinite programming, interior-point methods, polynomial complexity, path-following methods, primal-dual methods, nonlinear programming, Newton method, first-order methods

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

Category 2: Nonlinear Optimization


Download: [Compressed Postscript][PDF]

Entry Submitted: 01/15/2003
Entry Accepted: 01/15/2003
Entry Last Modified: 01/15/2003

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society