# A conditional gradient homotopy method with applications to Semidefinite Programming

arXiv: https://arxiv.org/abs/2207.03101 · HTML: https://mlsanity.com/paper/2207.03101/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 10 of its 50 references that are in the map.
- First posted on arXiv 7 Jul 2022.

## Builds on (most cited first, 10 of 10)

- [Scalable Semidefinite Programming](https://mlsanity.com/paper/1912.02949/) (2019)
- [New Analysis and Results for the Frank-Wolfe Method](https://mlsanity.com/paper/1307.0873/) (2013)
- [On the low-rank approach for semidefinite programs arising in synchronization and community detection](https://mlsanity.com/paper/1602.04426/) (2016)
- [Conditional Gradient Algorithms for Norm-Regularized Smooth Convex Optimization](https://mlsanity.com/paper/1302.2325/) (2013)
- [Analysis of the Frank-Wolfe Method for Convex Composite Optimization involving a Logarithmically-Homogeneous Barrier](https://mlsanity.com/paper/2010.08999/) (2020)
- [Self-Concordant Analysis of Frank-Wolfe Algorithms](https://mlsanity.com/paper/2002.04320/) (2020)
- [Semidefinite approximations of the matrix logarithm](https://mlsanity.com/paper/1705.00812/) (2017)
- [Generalized Self-Concordant Analysis of Frank-Wolfe algorithms](https://mlsanity.com/paper/2010.01009/) (2020)
- [First-Order Methods for Convex Optimization](https://mlsanity.com/paper/2101.00935/) (2021)
- [Finding Sparse Solutions for Packing and Covering Semidefinite Programs](https://mlsanity.com/paper/1809.09698/) (2018)

## Abstract (arXiv)

We propose a new homotopy-based conditional gradient method for solving convex optimization problems with a large number of simple conic constraints. Instances of this template naturally appear in semidefinite programming problems arising as convex relaxations of combinatorial optimization problems. Our method is a double-loop algorithm in which the conic constraint is treated via a self-concordant barrier, and the inner loop employs a conditional gradient algorithm to approximate the analytic central path, while the outer loop updates the accuracy imposed on the temporal solution and the homotopy parameter. Our theoretical iteration complexity is competitive when confronted to state-of-the-art SDP solvers, with the decisive advantage of cheap projection-free subroutines. Preliminary numerical experiments are provided for illustrating the practical performance of the method.