Continuous Optimization Seminar - Sina RezazadehExport this event to calendar

Wednesday, November 28, 2018 — 4:00 PM EST

Title: Convergence Rate of Block-Coordinate Maximization Burer-Monteiro Method for Solving Large SDP

Speaker: Sina Rezazadeh
Affiliation: University of Waterloo
Room: MC 5479

Abstract: Burer and Monteiro in 2003 proposed a nonlinear algorithm for solving semidefinite programs. They replace the psd constraint with a low-rank factorization, turning the problem into a non-convex formulation. Then to solve the non-convex problem, they suggested an augmented Lagrangian based algorithm for it. 

Seeking some faster algorithm for some prevalent semidefinite programs,   e.g. Max-Cut, EDM etc. applicable to large scale SDPs,  P. Parrilo et al. prove a convergence rate for the block-coordinate maximization (BCM) algorithm for the Burer and Monteiro reformulation. 

In this talk, I will go through the proofs in P.Parillo et al paper, title as above. Their paper has appeared in ICML 2018. 

Location 
MC - Mathematics & Computer Building
5479
200 University Avenue West

Waterloo, ON N2L 3G1
Canada

S M T W T F S
29
30
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
1
2
  1. 2019 (143)
    1. October (14)
    2. September (15)
    3. August (9)
    4. July (17)
    5. June (18)
    6. May (16)
    7. April (9)
    8. March (24)
    9. February (13)
    10. January (8)
  2. 2018 (138)
    1. December (2)
    2. November (18)
    3. October (14)
    4. September (9)
    5. August (2)
    6. July (10)
    7. June (13)
    8. May (17)
    9. April (9)
    10. March (19)
    11. February (14)
    12. January (11)
  3. 2017 (103)
  4. 2016 (137)
  5. 2015 (136)
  6. 2014 (88)
  7. 2013 (48)
  8. 2012 (39)
  9. 2011 (36)
  10. 2010 (40)
  11. 2009 (40)
  12. 2008 (39)
  13. 2007 (15)