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.
Citation
IFOR Internal report, October 2009, ETH Zurich, Raemistrasse 101, CH-8092 Zurich, Switzerland.