Optimization Software at Georgia Tech
Semidefinite Optimization: First-order algorithms
SDPLR v0.130301 (March 13, 2001)
SDPLR is an ANSI C package developed S. Burer, C. Choi and R.D.C. Monteiro for
solving general semidefinite programs (SDPs) using a nonlinear, first-order algorithm
that is based on the idea of low-rank factorization. A specialized version of SDPLR
is also available for solving specially structured semidefinite programs (SDPs) such
as the MaxCut SDP, the Minimum Bisection SDP, and the (unweighted) Lovasz Theta SDP.
The details of the algorithm used by SDPLR can be found in the technical report
"A Nonlinear Programming Algorithm for Semidefinite Programs via Low-rank Factorization"
written by S. Burer and R.D.C. Monteiro.
DSA-BD v0 (September 22, 2011)
DSA-BD is a MATLAB package developed by C. Ortiz, R.D.C. Monteiro and B.F. Svaiter for
solving general semidefinite programs (SDPs) using a block-decomposition first-order
method, which is a special case of the hybrid proximal extragradient (HPE) method,
a framework of inexact proximal point methods introduced by B.F. Svaiter and M. Solodov.
Several ingredients are introduced to speed-up the method in its pure form such as:
an aggressive choice of stepsize for performing the extragradient step;
use of scaled inner products in the primal and dual spaces;
dynamic update of the scaled inner product in the primal space for properly
balancing the primal and dual relative residuals, and;
proper choices of the initial primal and dual iterates, as well as the initial
parameter for the primal scaled inner product.
The subroutines
for most of the algebraic operations (SDV, matrix-vector multiplication) use a LAPACK
implementation coded in C.
The details of the algorithm used by DSA-BD can be found in the technical report
"Implementation of a block-decomposition algorithm for solving large scale conic
semidefinite programming problems" written by R.D.C. Monteiro, C. Ortiz and B.F. Svaiter.
Combinatorial Optimization: Continuous heuristics
CirCut v1.0612 (June 12, 2001)
CirCut is a Fortran 90 package for finding approximate solutions of certain
binary quadratic programs, currently including the Max-Cut and the
Max-Bisection problems. An introduction to the details of
the algorithm behind CirCut can be found in the technical report "Rank-Two
Relaxation Heuristics for Max-Cut and Other Binary Quadratic Programs"
written by S. Burer, R.D.C. Monteiro, and Y. Zhang.
Max-AO v0.120301 (March 12, 2001)
Max-AO is an ANSI C package for heuristically solving the
(unweighted) maximum stable set and maximum clique problems.
The details of the algorithm behind Max-AO are available in the
technical report "Maximum Stable Set Formulations and Heuristics
Based on Continuous Optimization" written by S. Burer, R.D.C.
Monteiro, and Y. Zhang.
Information
Renato D.C. Monteiro,
Georgia Institute of Technology
Yin Zhang, Rice University
Sam Burer,
University of Iowa
|
