YoVDO

Polynomial Time Guarantees for the Burer-Monteiro Method

Offered By: Fields Institute via YouTube

Tags

Algorithms Courses Real Algebraic Geometry Courses

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 Theory
The 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