The Karush-Kuhn-Tucker (KKT) Conditions and the Interior Point Method for Convex Optimization
ฝัง
- เผยแพร่เมื่อ 29 พ.ค. 2024
- A gentle and visual introduction to the topic of Convex Optimization (part 3/3). In this video, we continue the discussion on the principle of duality, which ultimately leads us to the "interior point method" in optimization. Along the way, we derive the celebrated Karush-Kuhn-Tucker (KKT) conditions.
This is the third video of the series.
Part 1: What is (Mathematical) Optimization? ( • What Is Mathematical O... )
Part 2: Convexity and the Principle of (Lagrangian) Duality ( • Convexity and The Prin... )
Part 3: Algorithms for Convex Optimization (Interior Point Methods). ( • The Karush-Kuhn-Tucker... )
--------------------------------
References:
- Boyd and Vandenberghe's wonderful book on convex optimization: stanford.edu/~boyd/cvxbook/
--------------------------------
Typos and precisions:
- At 12:50 by "grad_f and grad_g are inversely proportional", I mean grad_f and grad_g are proportional to each other with a negative coefficients.
- At 13:47, the correct feasibility equation for x is g(x) \le 0, and not g(x) \ge 0 as stated in the video. This typo goes away starting from 15:11
--------------------------------
Timestamps:
0:00 Previously
0:25 Working Example
8:03 Duality for Convex Optimization Problems
10:38 KKT Conditions
15:00 Interior Point Method
21:00 Conclusion
--------------------------
Credit:
🐍 Manim and Python : github.com/3b1b/manim
🐵 Blender3D: www.blender.org/
🗒️ Emacs: www.gnu.org/software/emacs/
This video would not have been possible without the help of Gökçe Dayanıklı.
--------------------------
🎵 Music
- Vincent Rubinetti (vincerubinetti.bandcamp.com/)
- Carefree by Kevin MacLeod ( • Thinking Music ) - วิทยาศาสตร์และเทคโนโลยี
Thank you to every one who watched the video and spotted a typo or correction. I will group them in this comment so new viewers can have easy access to them.
- At 12:50 by "grad_f and grad_g are inversely proportional", I mean grad_f and grad_g are proportional to each other with a negative coefficients.
- At 13:47, the correct feasibility equation for x is g(x) \le 0, and not g(x) \ge 0 as stated in the video. This typo goes away starting from 15:11
I worked out the gradient by hand (17:00) and found out that our solutions don't match, you have an extra ' - ' (minus sign) in the argument of log. The equation should be :
grad[ f(x) - t log( +g(x)) ] and not grad[ f(x) - t log( -g(x)) ]. The gradient of log(g(x)) is grad(g(x))/g(x), no minus sign.
@@artashesasoyan6272 Thanks for working this out. Your reasoning would be correct if g were positive, but in this case g
At 05:44, P(y) = max u*y subject to u≥0 results in "max{0,...,∞}=∞, if y>0" and "max{-∞,...,0}=0, if y≤0".
It's confusing after 6:46 when you say "u goes first", but that's actually when X "goes" first, etc. You do the same thing again at 9:48, where it is particularly misleading.
Love your content! I hope you are somehow finding time to make more. The world could really use more videos giving concise explanations related to convex optimization. I'm particularly interested in manifold learning.
20mins content better than my professor for half a semester. Thank you
you should submit this to 3b1b's summer of math exposition contest
The author must be a genius for making such a great video! Only a man with deep understanding of optimization can explain it virtually
The best video on Lagrangian method that I've ever seen! Great work, thank you!
Wow, thanks!
Fantastic video! Please keep more coming, these are super-useful!
I have actually worked through Boyd's book and the reason I still prefer this is, it's so much quick to refresh your memory with a short video like this. I worked through Boyd's book many years ago and barely remember much now (except that it was fun!).. I suddenly need to recall duality/IP as a quick reference, it's not practical to read that book (or even Boyd's slides). This video is just perfect for that.
Another use case I see is, before you deep dive into a convex optimization book, watching this video will give you a great idea and intuition for what's coming next!
Thanks, I am glad you find them useful!
I can't thank you enough for this video and all the content you produce. This has to become the standard for teaching mathematics in schools. It makes everything so much clear, learning becomes so much more efficient. People in education should look at this and reward people like you who innovate and outpeform any classic math teacher. Thank you once again.
I've finally known where the hell Lagrangian comes from
Such a great video
Excellent job! This is a new subject for me and it felt really intuitive and interesting all the way through. I hope your channel get the exposure and success that this material deserves.
It is mind blowing to see all these ideas visually. Keep it coming, thank you
What a fantastic series! Thank you so much! Keep up the beautiful work! This is the future of math education at work.
Amazing job! I think that in a lot of subjets, there are many encysted text-book explanations , with a bottom-top approach that overwhelms and trap newcomers and practicioners, making this knowledge a specialized tool. Channels like yours unblock that bottleneck, democratizing very useful insights and tools and speeding up progress, thanks!
Amazing video, could not understand this for the life of me but this helped tremendously. Videos like this must take a long time to make, but I feel that they will be used for generations. Thank you :)
This video is just absoloutely amazing, for anyone just learning optimization. especially the KKT conditions its after 3 months that I have finally understood the actual intuition behind them
Amazing visuals with great explanations. I'm so grateful for channels with high quality content like this.
Much appreciated! I am glad you liked the channel.
Fantastic video!. You have really motivated the ideas so well and you have beautifully developed the intuition through the narrative. Kudos!
Your insights and visualizations are immensely helpful!
I can't wait till this channel explodes and becomes very popular and I can say that I was here in the beginning. Thank you for the amazing content, keep it up!
Your explanation is genius! Thank you for taking the time to create such a beautiful explanation. You make learning fun.
I have spent a great deal of time trying to understand this topic, and this video series is the single best resource I have ever come across.
Thanks. I am really glad it was helpful
Thankyou for this :) I don't think there is a better resource in internet for this topic:) Please keep the videos coming, I already binge watched all of your existing videos, Your way of storytelling is just amazing!
Thank you! Will do!
Thank you so much for putting in all these hours to make a video like that. But it really helped me to understand the topic a lot better!
thanks for the visualization, you made it so simpler for us to understand the problem and also understand what prof said in lecture
Great video, one of the best and most intuitive ones I have seen. I think you could have included a short discussion on what does it mean for the multiplier (u or v) to be binding.
This magic! How can you represent such difficult concepts so beautifully! This is best youtube video ever
Amazing video! Thank you! I hope there will be a lot more optimization videos from you in the future!
In fact, the virtual videos are incredible when it comes to learning new stuff, specially in math problems.
the way you are presenting equations using animations its amazing sir. even a person with tiny knowledge in math can easily understand it.
Great presentation. You make it so simple...!
I must say, the insight that the visual approach provided just made it so intuitive. This is quite useful. Keep up the great work.
Awesome, thank you!
Very clear and concise explanation. Thank you so much.
Very nice series(and channel in general). I am a big fan of the work of Prof. Boyd, and this series makes the concept very intuitive and nicer to think about. Great work!
Thank you, I appreciate that!
really amazing videos, visually and intuitively explanation are really important to me, thank you for doing these great videos
Wow! great explanation. This is one topic that I find it intimidating when reading the book, but you explain it beautifully. Keep up the good work man!
It's always nice to hear that this was useful, thanks!!
The best explanation of the duality problem and KKT condition that I have seen! Thank you
From a convergent, convex (lens) or syntropic perspective everything looks divergent, concave or entropic -- the 2nd law of thermodynamics.
According to the 2nd law of thermodynamics all observers have a syntropic perspective.
My syntropy is your entropy and your syntropy is my entropy -- duality!
Syntropy (prediction) is dual to increasing entropy -- the 4th law of thermodynamics.
Homology (convergence, syntropy) is dual to co-homology (divergence, entropy).
Teleological physics (syntropy) is dual to non teleological physics (entropy).
Duality creates reality.
"Always two there are" -- Yoda.
Points are dual to lines -- the principle of duality in geometry.
thank you , this serie of videos helped me a lot to understand and deepen my knowledge of these concepts. keep up the great work
You're very welcome!
Amazing video! Video's like this make me excited to learn, keep it up!
Second time I watch this video, fantastic content! Analogies are a piece of art.
Making a complex math concept simple ... well done!
elegant explanation! It should be recommended to whoever wants to learn optimization theory.
thank you for the amazing background music! It helps me sleep immediately.
It was genuinely helpful. Thank you for the insightful teaching
one of the best series of vids posted on the internet
Awesome and illustrative, thank you.
These are like how I imagined math lectures would look in the future. Great work, instant sub.
Welcome aboard!
Amazing intuition behind KKT!
Very helpful stuff! Thank you very much for your effort.
Thank you very much for this video!! I'm just getting started with semidefinite programming
I don’t comment much on yt, but these series are awesome! Thanks and keep us the good work!
Exceptional video.... It's so clear Bravo.
Beautifullly explained.
you put soo much effort. subscribed right away!!
You are just amazing..Thank you so much
That's the best video i have watched till now. Thanks a lot
Awesome video, thanks for make this available.
Subscribed. Your content is invaluable to CS grad students.
Amazing exposiotion! Thanks a lot and it really helps me!
Thank you for this quality content ! Best explanation on this topic
Such a beautiful video. Thanks a ton for this
this is the greatest thing I have ever seen! sooo good!!!!
absolutely outstanding! thank you so much. as a discrete algorithm designer unexpectedly thrown into the trenches of solving a difficult bi-level mixed-integer linear optimization problem, this was very intuitive and much less scary than the Wikipedia article.
Yay, glad this was helpful!
Hello Bachir! , This is so amazing ! I can just say - god bless you !!! Best Duality explanation so far !!
Thanks a lot!!!
From a convergent, convex (lens) or syntropic perspective everything looks divergent, concave or entropic -- the 2nd law of thermodynamics.
According to the 2nd law of thermodynamics all observers have a syntropic perspective.
My syntropy is your entropy and your syntropy is my entropy -- duality!
Syntropy (prediction) is dual to increasing entropy -- the 4th law of thermodynamics.
Homology (convergence, syntropy) is dual to co-homology (divergence, entropy).
Teleological physics (syntropy) is dual to non teleological physics (entropy).
Duality creates reality.
"Always two there are" -- Yoda.
Points are dual to lines -- the principle of duality in geometry.
Wonderfully explained, I am in awe
Happy to hear that!
Awesome explanation! keep these videos up...
Just sth aside but I really like the background music. Gives me a sense of calm and peace for learning.
thanks mate. was having some doubts after going through Boyd's book... now many things are clear
You are most welcome
Holy?! The NIP derivation makes so much sense!!
My professor did teach quite well but I'm missing some intuitive visualizations. All makes sense now thanks to your video!
brilliantly explained, thanks a ton
Very helpful video!!! Thank you very much
Why I can only give one like to this video?! This video is awesome!!! Thanks for making it!
Very well explained! Tbarkllah elik
Great Video and explanation.
Great video. Thank you
Very well explained
That was a very nice presentation and a lot of fun to watch!
ps: Maybe you could also make a video on the duality gap and Slater's condition?
excellent explanation. can you also explain the weak duality theorem in detail. Why dual problem gives lower bound than primal. Is penalty function same as lagrange multiplier
This video is amazing, thanks!
excellent video! Thanks you so much!
Thank you so much, it helps me a lot.
thank you so much for the great video. You saved me from hours of reading on text book but not understand anything
Brilliant effort!
Thank you so much for this amazing video 💯
My pleasure!
Thank you for this great explanation
Glad it was helpful!!
amazing video!!! Thank you!
Thank you very much for this video. It has been very helpful 😊. Keep it up 👍.
I just have a question about the gradients v_i of the "penalty functions" for the equality constraints h_i (at 8.31 in the video). Instead of finding the max of v_i >= 0, shouldn't we instead find the maximum of |v_i| (the absolute value of the v_i's)? Considering the figure at 5.39 in the video, for constrains that require equality to zero (i.e., the h_i's), surely we would want to consider negative slopes in a way that make the corresponding penalty function effectively +infinity for all values except for where these constraints are equal to zero.
Please let me know where I may be going wrong.
Love the video! Student should really start from your video than the standard textbooks!!!!!!
Please slowly lead us to the sum of squares optimization :))) I hope that this kind of knowledge dissemination will bring exoteric optimization algorithm to the general population and industry. Understanding from industry people will help scientist receive more funding regarding their research endeavour.
I absolutely love this!!! It's so good! please keep on making videos like this! Is there any way you could be persuaded to make 4 to 5 small assignments to each video? Maybe just for patrons or something like that?
Wonderful Video! It helped so much
Yaay!
Thank you for this amazing video! But I was wondering if g(x) should be smaller to 0 at 13:50?
have you thought about covering primal dual interior point method? That would be great!
Excellent! Really helpful
Great video! Thank you so much!!!
Glad you enjoyed it!
20min better than a whole 1hour lecture from my professor
Fantastic! However, in 9:38, why the dual function gives a lower bound of the prime?
extremely helpful tysm. Two questions though: 1. at 7:06 , why that quantity is convex? because if you take max of u it is no longer linear right? 2. at 16:07, if we know u * g(x) =0, we can discuss case by case (i.e. when u = 0 and when g(x) = 0 ). Why that wouldn't work?
Thnak you so much for this video, it's so nice:)
You're welcome 😊
This is amazing!!! thanks!!!
Very good!
Just wish you had added a link to the book at the video description.
Good point, I have added a link. Thanks for your comment!