Polynomial Time Guarantees for the Burer-Monteiro Method
Offered By: Fields Institute via YouTube
Course Description
Overview
Explore a 41-minute conference talk from the Fields Institute's Workshop on Real Algebraic Geometry and Algorithms for Geometric Constraint Systems. Delve into Diego Cifuentes' presentation on polynomial time guarantees for the Burer-Monteiro method in solving large-scale semidefinite programs (SDPs). Learn about the nonconvex programming approach using an n×p matrix Y, where X = YYT, and discover how this method can solve SDPs in polynomial time under smoothed analysis conditions. Examine the compactness and smoothness assumptions for the SDP domain, and understand the implications of perturbing the cost matrix and constraints. Gain insights into the relationship between the number of constraints (m) and the matrix dimension (p), and how it approaches the Barvinok-Pataki bound. Understand the conditions under which the nonconvex program can achieve optimal solutions in polynomial time, advancing your knowledge of semidefinite programming and optimization techniques.
Syllabus
Polynomial time guarantees for the Burer-Monteiro method
Taught by
Fields Institute
Related Courses
Information TheoryThe Chinese University of Hong Kong via Coursera Intro to Computer Science
University of Virginia via Udacity Analytic Combinatorics, Part I
Princeton University via Coursera Algorithms, Part I
Princeton University via Coursera Divide and Conquer, Sorting and Searching, and Randomized Algorithms
Stanford University via Coursera