Loading...
Please wait, while we are loading the content...
Similar Documents
Fast Algorithms for Solving SDPs on Graphs SPUR Final Paper, Summer 2014
| Content Provider | Semantic Scholar |
|---|---|
| Author | Gao, Yibo Gu, Yuzhou Vladu, Adrian Peng, Richard |
| Copyright Year | 2014 |
| Abstract | Semidefinite programming (SDP) is a basic optimization primitive, which has been successfully applied to many combinatorial graph algorithms. Unfortunately, in the era of big data, standard methods for solving SDP’s (Interior Point, Ellipsoid) are prohibitively slow. Instead of focusing on these, we shift our attention to first order methods, which appear to be very fast for practical purposes. It turns out that simply by applying mirror descent, one can solve SDP’s within accuracy using O( −2) iterations, each of them consisting of simple matrix operations. However, the standard setup for mirror descent has the fundamental flaw that iterations are computationally expensive. In this work, we consider the SDP relaxation for MAXCUT, and attempt to provide an efficient algorithm for solving it, which takes into account the sparsity of the input. We provide a different (and simpler) setup for mirror descent in hope of achieving cheaper iterations. |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | http://math.mit.edu/research/undergraduate/spur/documents/2014gao-gu.pdf |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
