YoVDO

Local Minima, Stable Sets, and Sums of Squares

Offered By: Society for Industrial and Applied Mathematics via YouTube

Tags

SIAM (Society for Industrial and Applied Mathematics) Courses Algebra Courses Graph Theory Courses Semidefinite Programming Courses

Course Description

Overview

Explore the complexity of finding local minimizers in polynomial optimization problems through this invited talk from the SIAM Conference on Optimization 2021. Delve into the characterization of problem complexity based on polynomial degrees, examining two key results: the NP-hardness of finding approximate local minimizers for quadratic polynomials over polytopes, and the efficient discovery of local minimizers for cubic polynomials using semidefinite programming. Investigate the connections between stable sets in graph theory and sum of squares polynomials in algebra, leading to an algebraic characterization of perfect graphs. Gain insights into optimization challenges, computational complexity, and the interplay between graph theory and algebraic methods in this comprehensive presentation by Amir Ali Ahmadi from Princeton University.

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