The Karush–Kuhn–Tucker (KKT) Conditions and the Interior Point Method for Convex Optimization

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 Optimization?  )
Part 2: Convexity and the Principle of (Lagrangian) Duality (   • Convexity and The Principle of Duality  )
Part 3: Algorithms for Convex Optimization (Interior Point Methods). (   • The Karush–Kuhn–Tucker (KKT)  Conditi...  )

--------------------------------
References:
Boyd and Vandenberghe's wonderful book on convex optimization: https://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 : https://github.com/3b1b/manim
🐵 Blender3D: https://www.blender.org/
🗒️ Emacs: https://www.gnu.org/software/emacs/


This video would not have been possible without the help of Gökçe Dayanıklı.

--------------------------
🎵 Music

Vincent Rubinetti (https://vincerubinetti.bandcamp.com/)
Carefree by Kevin MacLeod (   • Thinking Music  )