Smoothing techniques for solving semidefinite programs with many constraints

Michael Bürgisser(michael.buergisserifor.math.ethz.ch)
Michel Baes(michel.baesifor.math.ethz.ch)

Abstract: We use smoothing techniques to solve approximately mildly structured semidefinite programs with many constraints. As smoothing techniques require a specific problem format, we introduce an alternative problem formulation that fulfills the structural assumptions. The resulting algorithm has a complexity that depends linearly both on the number of constraints and on the inverse of the accuracy. Some numerical experiments show that smoothing techniques compares favorably with interior-point methods for very large-scale instances.

Keywords: Semidefinite programming, convex optimization, nonsmooth optimization

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

Category 2: Convex and Nonsmooth Optimization (Nonsmooth Optimization )

Citation: IFOR Internal report, October 2009, ETH Zurich, Raemistrasse 101, CH-8092 Zurich, Switzerland.

Download: [PDF]

Entry Submitted: 10/05/2009
Entry Accepted: 10/05/2009
Entry Last Modified: 10/05/2009

Modify/Update this entry