Table of Contents

🎓 Intended learning outcomes

At the end of this lesson, students are expected to:

• Understand and explain the motivation for the dual formulation
• Be able to describe and characterize the duality principle
• Explain the difference between strong duality and weak duality and their conditions
• Be able to apply the Lagrangian to constrained optimization formulations
• Give an intuition behind the Lagrange multiplier
• Formulate the primal & dual objective with the Lagrangian
• Be able to check for strong duality with KKT
• Formulate the dual in standard constrained optimization form
• Understand how to solve the dual formulation with coordinate descent / SMO

🌽 Motivation: Kernel SVM ★★☆

In 2.3 Gradient-based Optimization and 2.4 Constrained Optimization we considered linear classification problems — problems that could be solved by drawing a separating hyperplane (or line in 2D) to separate the classes. Now consider what would happen if we applied our previous methods to a dataset like this