Scribd
Upload
50 views10 pages

SVM Dual Problem Notes

The document discusses the Karush Kuhn Tucker (KKT) conditions, which are essential for deriving the dual problem in support vector machines (SVMs) and other optimization problems. It explains the duality principle in optimization, highlighting how the dual problem can simplify complex problems and provide bounds on the primal problem's solution. Additionally, it notes that only support vectors contribute to the dual variables in SVMs.

Uploaded by

saurabh kumar
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
50 views10 pages

SVM Dual Problem Notes

The document discusses the Karush Kuhn Tucker (KKT) conditions, which are essential for deriving the dual problem in support vector machines (SVMs) and other optimization problems. It explains the duality principle in optimization, highlighting how the dual problem can simplify complex problems and provide bounds on the primal problem's solution. Additionally, it notes that only support vectors contribute to the dual variables in SVMs.

Uploaded by

saurabh kumar
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Recap

16 July 2023 00:02

Session on SVM Dual Problem Page 1


SVM in n Dimensions
14 July 2023 17:42

Session on SVM Dual Problem Page 2


Constrained Optimization Problems with Inequality
16 July 2023 00:02

Session on SVM Dual Problem Page 3


Karush Kuhn Tucker Conditions (KKT conditions)
16 July 2023 11:55

They generalize the method of Lagrange multipliers to handle inequality


constraints. In the context of support vector machines (SVMs) and many
other optimization problems, the KKT conditions play a key role in
deriving the dual problem from the primal problem.
The KKT conditions are:

1. Stationarity: The derivative of the Lagrangian with respect to the


primal variables, the dual variables associated with inequality
constraints, and the dual variables associated with equality
constraints are all zero.

2. Primal feasibility: All the primal constraints are satisfied.

3. Dual feasibility: All the dual variables associated with inequality


constraints are nonnegative.

4. Complementary slackness: The product of each dual variable and its


associated inequality constraint is zero. This means that at the
optimal solution, for each constraint, either the constraint is active
(equality holds) and the dual variable can be nonzero, or the
constraint is inactive (strict inequality holds) and the dual variable is
zero.

Session on SVM Dual Problem Page 4


Example
16 July 2023 14:52

Session on SVM Dual Problem Page 5


Concept of Duality
16 July 2023 08:46

The duality principle is fundamental in optimization theory. It provides a powerful tool for
solving difficult or complex optimization problems by transforming them into simpler or
easier-to-solve problems. The solution to the dual problem provides a lower bound on the
solution of the primal problem. If strong duality holds (i.e., the optimal values of the primal
and dual problems are equal), then solving the dual problem can directly give the solution to
the primal problem.

The primal problem is the original optimization problem that you are trying to solve. It involves
finding the minimum or maximum of a particular objective function, subject to certain
constraints.

The dual problem is a related optimization problem that is derived from the primal problem. It
provides a lower or upper bound on the solution to the primal problem.

Session on SVM Dual Problem Page 6


SVM Dual Problem
15 July 2023 23:58

Session on SVM Dual Problem Page 7


Dual Problem Derivation
16 July 2023 01:14

Session on SVM Dual Problem Page 8


Session on SVM Dual Problem Page 9
Observations
15 July 2023 23:59

1. Alpha_i>0 only for support vectors -> the equation


is not as dangerous as it seems
2. Dot product

Session on SVM Dual Problem Page 10

You might also like