Deriving the KKT conditions for Inequality-Constrained Optimization | Introduction to Duality

Equality-Constrained Optimization Problems can be solved by Lagrange Multipliers. How about Inequality-Constrained ones? Here are the notes: https://raw.githubusercontent.com/Cey...

One could try to also just build the Lagrangian and then minimizing the (unconstrained) Lagrangian. However, this will result in finding an optimum that lies on the boundary of our feasible region. This will also signal that Inequality constraints are more difficult to handle than equality constraints.

In this video we will derive the Karush-Kuhn-Tucker conditions that (together with regularity) are necessary in order to find an optimizer of the constrained problem. The path towards them will introduce the duality or the dual of the problem.

Feel free to write a comment if something was unclear or if you have troubles understanding :)

-------

📝 : Check out the GitHub Repository of the channel, where I upload all the handwritten notes and source-code files (contributions are very welcome): https://github.com/Ceyron/machine-lea...

📢 : Follow me on LinkedIn or Twitter for updates on the channel and other cool Machine Learning & Simulation stuff:   / felix-koehler   and   / felix_m_koehler  

💸 : If you want to support my work on the channel, you can become a Patreon here:   / mlsim  

-------

⚙️ My Gear:

(Below are affiliate links to Amazon. If you decide to purchase the product or something else on Amazon through this link, I earn a small commission.)

- 🎙️ Microphone: Blue Yeti: https://amzn.to/3NU7OAs
- ⌨️ Logitech TKL Mechanical Keyboard: https://amzn.to/3JhEtwp
- 🎨 Gaomon Drawing Tablet (similar to a WACOM Tablet, but cheaper, works flawlessly under Linux): https://amzn.to/37katmf
- 🔌 Laptop Charger: https://amzn.to/3ja0imP
- 💻 My Laptop (generally I like the Dell XPS series): https://amzn.to/38xrABL
- 📱 My Phone: Fairphone 4 (I love the sustainability and repairability aspect of it): https://amzn.to/3Jr4ZmV

If I had to purchase these items again, I would probably change the following:

- 🎙️ Rode NT: https://amzn.to/3NUIGtw
- 💻 Framework Laptop (I do not get a commission here, but I love the vision of Framework. It will definitely be my next Ultrabook): https://frame.work

As an Amazon Associate I earn from qualifying purchases.

-------

Timestamps:
00:00 Introduction
00:33 Why not use the gradient of Lagrangian?
03:31 Recovering Target from Lagrangian
09:03 Transformation to unconstrained problem
10:30 Disclaimer: inf instead of min
11:20 Hint: We need the standard form
12:43 Min-Max Inequality
14:09 Duality
16:30 Primal and Dual
17:15 The Duality Gap
17:45 Regularity & Strong Duality
18:40 Assuming a regular problem
21:58 Deducing the KKT
23:10 KKT: Primal Feasibility
23:25 KKT: Stationarity
24:24 KKT: Dual Feasibility
24:49 KKT: Complimentary Slackness
25:16 Simplifying Complimentary Slackness
26:46 Summary KKT
27:03 Regularity & Constraint Qualification
28:58 Outro