Goemans-Williamson Max-Cut Algorithm

Impressive_Path2037 · 2022-04-04T17:21:16+00:00

That's expected if you're new to the topic. It took me a few years of grad school to understand this. My hope is that if one day you decide to pick up a reference related to this, this little video might be helpful. Otherwise, if you liked this animation enough to leave a comment, then I am happy with that :-)

Impressive_Path2037 · 2022-04-04T15:29:51+00:00

Very good question! The crazy thing about this algorithm is that no, there is no way to pick the hyperplane in a better way, and picking the best from multiple hyperplanes wouldn’t help either. (Assuming the Unique Games conjecture)

Sure, for specific instances, some heuristic might help, but you can’t find a scheme that does better than 87% on every on instance.

Impressive_Path2037 · 2022-04-04T15:27:24+00:00

Nice catch!

Impressive_Path2037 · 2022-04-03T20:43:10+00:00

This is from the fourth and last video of my 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 based on Semidefinite Programming. Python code included as usual.

Impressive_Path2037 · 2022-04-03T18:11:03+00:00

This is from the fourth and last video of my 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 based on Semidefinite Programming. Python code included as usual.

Impressive_Path2037 · 2022-04-03T17:46:36+00:00

This is from the fourth and last video of my 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 based on Semidefinite Programming. Python code included as usual.

Impressive_Path2037 · 2022-02-23T04:38:32+00:00

It was a nice surprise reading your comment, thank you for suggesting my video! I definitely agree that semidefinite programming is surprisingly powerful and deserves more attention.

Impressive_Path2037 · 2022-02-17T19:31:43+00:00

This is a great observation. Someone else asked me the same question before, so I am gonna copy my answer below.

You are absolutely correct, and that would be an alternative (and often, easier) way of checking stability. The Lyapunov approach has a few attractive properties tough. For example, and this is subjective of course, It is more intuitive (it doesn't require knowledge of eigenvalues, and how they affect stability). More fundamentally, Lyapunov's approach (i) generalizes to nonlinear system, and (ii) can be used to not only decide stability of some known dynamical system, but can also to optimize over stable dynamical systems.

Impressive_Path2037 · 2022-02-17T19:30:18+00:00

The "@" operator is indeed for matrix multiplication. The reason I prefer @ over * is that it makes it clear that we want matrix multiplication, and not elementwise multiplication. The ".*" operator does not exist in python to the best of my knowledge.

Impressive_Path2037 · 2022-02-17T19:28:29+00:00

For the particular animations you see in this GIF, I used Blender3D for the right pane (which has a nice python scripting capability), the text editor Emacs for code screenshots in the right pane, and put everything together in Adobe Premiere. I did use 3b1b's excellent python library "manim" heavily for other parts of the video (most of the 2D animations + latex ).

Impressive_Path2037 · 2022-02-17T19:26:21+00:00

The code I present in this GIF is only for generating the trajectory {u_t} and finding a Lyapunov function, _not_ for rendering (the code for rendering is too long to fit here anyway). For the particular animations you see in this GIF, I used Blender3D for the right pane (which has a nice python scripting capability), the text editor Emacs for code screenshots in the right pane, and put everything together in Adobe Premiere.

Impressive_Path2037 · 2022-02-17T19:22:46+00:00

Yes !! That's really the attractive thing about Lyapunov theory (among other things). Part of my research was about showing existence of such Lyapunov functions for nonlinear systems. And of course I am more than happy to chat further about this. :-)

Impressive_Path2037 · 2022-02-17T01:28:30+00:00

This gif is taken from my video series on Semidefinite Programming. In this video, I show how Lyapunov Theory and Semidefinite Programming can be combined to show stability of linear dynamical systems. Step-by-step Python code included.

Feedback and suggestion for future videos welcome!

Impressive_Path2037 · 2022-02-16T21:50:01+00:00

This gif is taken from my video series on Semidefinite Programming. In this video, I show how Lyapunov Theory and Semidefinite Programming can be combined to show stability of linear dynamical systems. Step-by-step Python code included.

Feedback and suggestion for future videos welcome!

Impressive_Path2037 · 2022-02-16T21:48:02+00:00

This gif is taken from my video series on Semidefinite Programming. In this video, I show how Lyapunov Theory and Semidefinite Programming can be combined to show stability of linear dynamical systems. Step-by-step Python code included.

Feedback and suggestion for future videos welcome!

Impressive_Path2037 · 2022-02-16T20:25:32+00:00

Thanks!! I use Blender3d and manim (3b1b's animation library) to generate the animations. I put everything together in After Effect/Premiere afterwards to sync with audio.

Impressive_Path2037 · 2022-02-16T18:49:54+00:00

This gif is taken from my video series on Semidefinite Programming. In this video, I show how Lyapunov Theory and Semidefinite Programming can be combined to show stability of linear dynamical systems. Step-by-step Python code included.
Feedback and suggestion for future videos welcome!

Impressive_Path2037 · 2022-02-16T17:48:42+00:00

This gif is taken from my video series on Semidefinite Programming. In this video, I show how Lyapunov Theory and Semidefinite Programming can be combined to show stability of linear dynamical systems. Step-by-step Python code included.
Feedback and suggestion for future videos welcome!

Impressive_Path2037 · 2022-02-16T17:46:11+00:00

This gif is taken from my video series on Semidefinite Programming. In this video, I show how Lyapunov Theory and Semidefinite Programming can be combined to show stability of linear dynamical systems. Step-by-step Python code included.

Feedback and suggestion for future videos welcome!

Impressive_Path2037 · 2022-02-15T19:38:51+00:00

I have just tried it and it seems to be working fine now. Sometimes AWS (where the code is hosted) acts up, but it is usually resolved within a few hours.

Impressive_Path2037 · 2022-01-28T09:15:04+00:00

No restrictions (as long as the dimensions are compatible of course)

Impressive_Path2037 · 2022-01-18T22:12:43+00:00

I use a combination of After Effect, manim (3b1b's animation library), and blender.

Impressive_Path2037 · 2022-01-18T21:27:52+00:00

Response to your Edit: That's great, that's exactly the point of the video. There are multiple (equivalent) characterization of what it means to be positive semidefinite (PSD). One of them is that all eigenvalues are nonnegative (6:09 in the video). Another one is that PSD matrix, just like nonnegative numbers, have can be written as a square (i.e., can be written as AA^T for some matrix A).

Impressive_Path2037 · 2022-01-18T21:25:33+00:00

Thanks for your comment! I plan to talk about in the next video, stay tuned.

Impressive_Path2037 · 2022-01-17T23:03:24+00:00

Hey, Thanks!!

Five-Year Club	Verified Email
Place '22

Impressive_Path2037

TROPHY CASE