Henry Wolkowicz's Research

Research Home
 Publications & Abstracts
 Talks & Presentations
 Semidefinite
Programming		 EDM
and SNL		 Graph
Partitioning
 Maximum
Cut
Linear
Programming		 Quadratic
Assignment
 NLP,
Regularization,
TRS 		Set
Partitioning
Matrix
Approximation
 Misc. Software/Opt. Matrices
and
Optimization

Semidefinite Programming

 

About Semidefinite Programming

Notation; Handbook of Semidefinite Programming;
Semidefinite Programming Bibliography/Comments/abstracts, (organized by Henry Wolkowicz)

Semidefinite programs are linear programs where the nonnegativity constraint is replaced
by a positive semidefinite constraint on matrix variables.
Semidefinite programs arise in many applications, e.g., combinatorial optimization, control theory, statistics, and nonlinear programming.
In particular, semidefinite programs arise from Lagrangian relaxations
of quadratic approximations; thus they provide improvements over linear approximations.
(And "the world is not linear".)

Semidefinite Programming WWW page by Christoph Helmberg; Search Results at simplifynet

A number of SDP solvers are listed below. (See also The NEOS Solvers.)



YALMIP (Yet another LMI parser): YALMIP serves as an interface to a number of solvers. Developed by Johan Loefberg.
Semidefinite Programming contains (locally) a toolbox with MATLAB programs for semidefinite programming.
SDPSOL is still available, but it has been superceded by CVX.


 

 

Further Information


Long list of related references (found using MathSearch); Primal-dual algorithms from Monteiro:

Interior-Point Archiv; e Game Theory Resources

A gzipped bib file for SDP with related papers
 
A Bibliography on Semidefinite Programming,
a searchable bib collection from The Collection of Computer Science Bibliographies --> Subject area: Bibliographies on Mathematics.

Several of my papers related to semidefinite programming are available through this abstracts file

 

Test Problems


Generating Hard Instances of SDP:
The two MATLAB files:
(i) rungenHard.m
(which uses writesdpa.m from CSDP webpage to get both SeDuMi format and .dat-s format),
and  (ii) genHardSDP.m,
generate hard instances of SDP.
These are SDP problems where strict complementarity fails.

This gzipped tar file contains the MATLAB mat files with the test problems gap0 to gap24 used in the research report
genhardsdp.pdf,
where the details for the problem generation are provided
(authors: Hua Wei and Henry Wolkowicz).


SDPLIB Test Problems (on SDP), from Brian Borchers

Large collection with benchmarks from Hans Mittelmann

 

Workshops and Conferences


Large Scale Nonlinear and Semidefinite Programming Workshop
Wednesday, May 12 to Saturday, May 15, 2004
at University of Waterloo
Call for Papers: Special Issue of MP


Novel Approaches to Hard Discrete Optimization,
April 2001
Workshop at the University of Waterloo.


Workshop at the Fields Institute
Semidefinite Programming and Interior-Point Approaches for Combinatorial Optimization Problems,
Toronto, Ontario, May 15-17, 1996

Two volumes of proceedings:
New Approaches to Hard Discrete Optimization,
volume 6 #3 in J. Comb. Opt.
Kluwer Academic Publishers,
Hingham, MA, 2002

Novel Approaches to Hard Discrete Optimization,
The Fields Institute for Research in Mathematical Sciences, Communications Series,
Providence, RI, 2003.
American Mathematical Society,
see bib data.

  

Home Pages and Lecture Notes



.






Last Modified:  Sunday 31 October 2010
XHTML CSS W3C-WAI