Local Minima, Stable Sets, and Sums of Squares
Offered By: Society for Industrial and Applied Mathematics via YouTube
Course Description
Overview
Syllabus
Intro
A bird's eye view of optimization
Step size too small
Forcing a smart initialization?
Finding a local minimum
Finding a local minimizer of a quadratic program
Stable sets in graphs
Proof outline
What about the unconstrained case?
Finding local minima of cubics Let's start with a simpler question. Can we efficiently find a critical point
Unexpected convexity
Local minima of cubics and SDP
All roads lead to sums of squares
A more complete story
Remainder of the talk
Nonnegativity vs. sum of squares
Nonnegative polynomials that are not SOS?
A new notion: SOS-perfect graphs
Example
An immediate implication
What happens on random graphs?
A challenge for the SOS/SDP community is
Feel the need for more SOS?
Taught by
Society for Industrial and Applied Mathematics
Related Courses
Approximation Algorithms Part IIÉcole normale supérieure via Coursera Convex Optimization
Stanford University via edX Graph Partitioning and Expanders
Stanford University via NovoEd Approximation Algorithm
Indian Institute of Technology, Kharagpur via Swayam The Effect of Parametrization on Nonconvex Optimization Landscapes - Seminar
Instituto de Matemática Pura e Aplicada via YouTube