Jump to Content: Welcome to the virtual world of Georgia Tech

Jump to Footer Navigation: Accessibility | Contact Us | Legal & Privacy Information | Technology

School of Industrial and Systems Engineering at Georgia Tech

Assistance Navigation:

Campus Map Directories Site Map Site Help Site Search
 
Faculty Webpage

Renato Monteiro Website

crumb trail: GT >> College of Engineering >> School of Industrial and Systems Engineering >> ISyE Personal Web Site

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.

This code was developed under the support of the grants: NSF CMMI-0900094 and ONR N00014-11-1-0062

2EBD-HPE v0.2 (July 31, 2012; last update: May 31, 2013)

2EBD-HPE is a MATLAB package developed by C. Ortiz, R.D.C. Monteiro and B.F. Svaiter for solving two-easy-block structured convex optimizations problems (including SDPs) using a block-decomposition first-order method. The 2EBD-HPE method contains two important refinements from a computational point of view, namely: an adaptive choice of stepsize for performing an extragradient step; and the use of a scaling factor to balance the blocks.The details of the algorithm used by 2EBD-HPE can be found in the paper "A first-order block-decomposition method for solving two-easy-block structured semidefinite programs" by R. D. C. Monteiro, C. Ortiz and B. F. Svaiter.

This code was developed under the support of the grants: NSF CMMI-0900094 and ONR N00014-11-1-0062

AAmethod v0 (August 31, 2012)

The AA method is a new accelerated variant of Nesterov's method for solving a class of convex optimization problems, in which certain acceleration parameters are adaptively (and aggressively) chosen so as to: preserve the theoretical iteration-complexity of the original method, and; substantially improve its practical performance. The details of the algorithm used by the AA method can be found in the paper "An adaptive accelerated first-order method for convex optimization" by R. D. C. Monteiro, C. Ortiz and B. F. Svaiter.

This code was developed under the support of the grants: NSF CMMI-0900094 and ONR N00014-11-1-0062




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

This site is available to any internet device, but really looks best in a modern graphical browser that supports web standards.

GT website ISyE website GT CoE website