Papers on semidefinite Programming

  1. General Survey Papers

    F. Alizadeh, journal article. Deals with duality theory, interior point methods, eigenvalue optimzation and combinatorial optimization. Available Click here for bibtex reference.

    S. Boyd & L. Vandenberghe, technical report. A general survey paper, dealing with applications, and developing inteior point methods. Click here for bibtex reference. For information about software and other documents related to this paper Click here.

    Y. Nesterov & A. Nemirovskii, Book. This book deals with polynomial time interior point algorithms for general convex programs. It has several sections on semidefinite programming. Click here for bibtex reference.

  2. Duality Theory, facial Structure, degeneracy

    J. Borwein & H. Wolkowicz, journal article. Two papers on duality theory over cones without any closedness assuptions. Click here for bibtex references.

    H. Wolkowicz, journal article. Specializes the previous papers to the semidefinite cone. Click here for bibtex reference.

    G. Pataki, technical report. Studies facial structure of feasible regions of semidefinite programs. Click here for bibtex reference.

    M. Ramana, PhD Thesis. Studies multiquadratic programming, and semidefinite relaxations of quadratic and combinatorial optimzation problems. Click here for bibtex reference.

    M. Ramana, technical report. Gives an algebraic characterization of SDP duality without Slater condition. Click here for bibtex reference.

    F. Alizadeh, J.P. Haeberly, and M. Overton, technical report Studies degeneracy and strict complementarity in semidefinite programming. Click here for bibtex reference.

  3. Diffenrential Theory

    Cullum, Donath & Wolfe, journal article. An early paper on sums of largest eigenvalues and their differential properties. Click here for bibtex reference.

    Fletcher, journal article. Derives optimality conditions for optimizations problems over the cone of positive semidefinite matrices using subgradient methods. Click here for bibtex reference.

    Overton, journal article. Paper studying the largest eigenvalue of a symmetric matrix, along with first and second order optimality conditions and an active set method algorithm. Click here for bibtex reference.

    Overton & Womersley, journal article. Two papers on the differential properties of the function "sum of the largest eigenvalues of a matrix". For a closely related paper Click here. Click here for bibtex reference.

  4. Interior Point Algorithms for SDP

    F. Alizadeh, journal article. Deals with duality theory, interior point methods, eigenvalue optimzation and combinatorial optimization. Click here for bibtex reference.

    Y. Nesterov & A. Nemirovskii, Book. This book deals with polynomial time interior point algorithms for general convex programs. It has several sections on semidefinite programming. Click here for bibtex reference.

    C. Helmberg, F. Rendl, B. Vanderbei & H. Wolkowicz. A primal dual algorithm for semidefinite programming, with particular emphasis on the maximum cut and bisection problems. Includes MATLAB code. Click here for bibtex reference. H. Wolkowicz SDP Page has further information and software.

    L. L. Vandenberghe & S. Boyd, Journal article. Develops a primal-dual interior point algorithm for semidefinite programs. Click here for bibtex reference. For information about software and other documents related to this paper Click here. For other related papers and software see S. Boyd

    M. Kojima, S. Shindoh & S. Hara. Extends several primal-dual interior point algorithms from linear complimentarity problem to complimentarity problems over the positive semidefinite cone. Click here for bibtex reference. For information about software and other documents related to this paper Click here. See also the related paper M. Kojima S. Kojima & S. Hara. Click here for bibtex reference.

    R. Freund, technical report. Develops an interior point algorithm without assuming that strong duality holds. Click here for bibtex reference.

    M. J. Todd & Y. Nesterov, technical report. Develops self-scaling technique for a class of cone optimization problems that includes semidefinite programming. Click here for bibtex reference.
    M. J. Todd & Y. Nesterov, technical report. Continuation of the above paper, more focused on primal-dual methods for SDP and QCQP. Click here for bibtex reference.

    O. Guler, technical report. Characterizes homogeneous self-polar cones as essentially semidefinite programs and presents simple derivation of universal barries for this class of cones. Click here for bibtex reference.

    F. Alizadeh, J.P. Haeberly, and M. Overton, technical report Studies various primal-dual interior point algorithms with computational results. Click here for bibtex reference.

  5. Applications in Combinatorial Optimization

    M. Groetschel, L. Lovasz & A. Schrijver, book. A book on applications of convex programming and the ellipsoid method in combinatorial optimization. Chapter 9 treats application of semidefinite programming in clique and coloring problems in perfect graphs. Click here for bibtex reference.

    L. Lovasz & A. Schrijver, journal article. Presents a method for relaxing an integer 0-1 program by various linear and semidefinite cuts. As case study examines the independent set polytope of graphs. Click here for bibtex reference.

    L. Lovasz, technical report. A survey article with sections connecting semidefinite programming to quadratic inequalities in 0-1 optimization problems. Click here for bibtex reference.

    M. Goemans & D. Williamson, journal article. Uses semidefinite programming relaxtions to find approximation algorithms for MAX-CUT and MAX SAT problems. Click here for bibtex reference.

    U. Feige & M. Goemmans, proceedings article. Fine tunes the methods of previous article and obtains better approximation results for MAX 2SAT MAX DICUT problems. Click here for bibtex reference.

    D. Karger, R. Motwani & M. Sudan, article Uses a variation of Lovasz theta function and vector labeling and constructs a coloring of a graph with strong performance guarantees. Click here for bibtex reference.

    A. Frieze & M. Jerrum, technical report. Extends Goemans--Williamson results to the k-cut problem. Click here for bibtex reference.

    N. Alon & N. Kahale, article Uses Lovasz number of graphs and constructrs an approximate maximum independent set. Click here for bibtex reference.

    D.E. Knuth, journal article A survey of the properties of Lovasz Theta function. Click here for bibtex item.
Back to SDP home Page

To SDP course at RUTCOR, Spring 1995