The Practical Guide to Semidefinite Programming (2/4)
Second video of the Semidefinite Programming series. In this video, we will see how to use semidefinite programming to solve a toy geometry problem. Python code included. -------------------------- Timestamps: 0:00 Intro 0:41 Interesting Fact about Positive Semidefinite matrices 2:17 Let'
From playlist Semidefinite Programming
Product Rules in Semidefinite Programming - Rajat Mittal
Rajat Mittal March 22, 2010 Semidefinite programming bounds are widely used in combinatorial optimization, quantum computing and complexity theory. The first semidefinite programming bound to gain fame is the so-called theta number developed by Lov\'asz to compute the Shannon capacity of
From playlist Mathematics
Stability of Linear Dynamical Systems | The Practical Guide to Semidefinite Programming (3/4)
Third video of the Semidefinite Programming series. In this video, we will see how to use semidefinite programming to check whether a linear dynamical system is asymptotically stable. Thanks to Lyapunov's theory, this task can be reduced to searching for a so-called Lyapunov function. Pyth
From playlist Semidefinite Programming
What Does It Mean For a Matrix to be POSITIVE? The Practical Guide to Semidefinite Programming(1/4)
Video series on the wonderful field of Semidefinite Programming and its applications. In this first part, we explore the question of how we can generalize the notion of positivity to matrices. -------------------------- Timestamps: 0:00 Intro 0:41 Questions 2:50 Definition 6:09 PSD vs
From playlist Semidefinite Programming
(ML 19.5) Positive semidefinite kernels (Covariance functions)
Definition of a positive semidefinite kernel, or covariance function. A simple example. Explanation of terminology: autocovariance, positive definite kernel, stationary kernel, isotropic kernel, covariogram, positive definite function.
From playlist Machine Learning
Goemans-Williamson Max-Cut Algorithm | The Practical Guide to Semidefinite Programming (4/4)
Fourth and last video of the Semidefinite Programming series. In this video, we will go over Goemans and Williamson's algorithm for the Max-Cut problem. Their algorithm, which is still state-of-the-art today, is one of the biggest breakthroughs in approximation theory. Remarkably, it is
From playlist Semidefinite Programming
Inner & Outer Semidirect Products Derivation - Group Theory
Semidirect products are a very important tool for studying groups because they allow us to break a group into smaller components using normal subgroups and complements! Here we describe a derivation for the idea of semidirect products and an explanation of how the map into the automorphism
From playlist Group Theory
Lieven Vandenberghe: "Bregman proximal methods for semidefinite optimization."
Intersections between Control, Learning and Optimization 2020 "Bregman proximal methods for semidefinite optimization." Lieven Vandenberghe - University of California, Los Angeles (UCLA) Abstract: We discuss first-order methods for semidefinite optimization, based on non-Euclidean projec
From playlist Intersections between Control, Learning and Optimization 2020
Irène Waldspurger: Rank optimality for the Burer-Monteiro factorization
The Burer-Monteiro factorization is a classical heuristic used to speed up the solving of large scale semidefinite programs when the solution is expected to be low rank: One writes the solution as the product of thinner matrices, and optimizes over the (low-dimensional) factors instead of
From playlist Control Theory and Optimization
Motion Planning Via Moment Optimization
Motion planning is a fundamental problem in robotics. In this talk we attack this problem with techniques from the fields of "Moment Optimization" and "Semidefinite Programming". Our method shows promise in handling obstacles that vary with time, and provides formal guarantees on the qual
From playlist Conference Talks
An incredible semicircle problem!
A semicircle contains an inscribed semicircle dividing its diameter into two lengths a and b. Can you find the formula for the inscribed semicircle's diameter in terms of the lengths a and b? What is the locus of the center of the inscribed semicircle? Thanks to Nick from Greece for the su
From playlist Math Puzzles, Riddles And Brain Teasers
Introduction to Continuous Combinatorics I: the semidefinite method of flag... - Leonardo Coregliano
Computer Science/Discrete Mathematics Seminar II Topic: Introduction to Continuous Combinatorics I: the semidefinite method of flag algebras Speaker: Leonardo Coregliano Affiliation: Member, School of Mathematics Date: November 02, 2021 The field of continuous combinatorics studies lar
From playlist Mathematics
Shmuel Onn: Sparse integer programming is FPT
We show that sparse integer programming, in variable dimension, with linear or separable convex objective, is fixed-parameter tractable. This is a culmination of a long line of research with many colleagues. We also discuss some of the many consequences of this result, which provides a new
From playlist Workshop: Tropical geometry and the geometry of linear programming
Nonlinear algebra, Lecture 11: "Semidefinite Programming", by Bernd Sturmfels
This is the eleventh lecture in the IMPRS Ringvorlesung, the advanced graduate course at the Max Planck Institute for Mathematics in the Sciences.
From playlist IMPRS Ringvorlesung - Introduction to Nonlinear Algebra
Mario Berta: "Characterising quantum correlations of fixed dimension"
Entropy Inequalities, Quantum Information and Quantum Physics 2021 "Characterising quantum correlations of fixed dimension" Mario Berta - Imperial College London Abstract: We give a converging semidefinite programming hierarchy of outer approximations for the set of quantum correlations
From playlist Entropy Inequalities, Quantum Information and Quantum Physics 2021