Q1 Quadratic Programming

[alasdairj]

From that well known source, wikipedia:

Quadratic programming (QP) is a special type of mathematical optimization problem. It is the problem of optimizing (minimizing or maximizing) a quadratic function of several variables subject to linear constraints on these variables.

The hard-margin SVM problem is to minimize 0.5w'w subject to (yn(w'xn + b) >= 1.

So is this a quadratic programming problem?

[Elroch]

A quadratic function of a set of variables is a linear combination of constants and products of one or two of the variables (including squares of them).

A linear constraint is an inequality which only contains a linear combination of constants and individual variables.

How do these relate to your description of the hard margin SVM problem? (The variables are the components of )

[alasdairj]

Well, the problem was to minimize wrt w and b the value w'w (which is a combination of 2 values of our variable) subject to yn(w'xn + b) >= 1 where yn and xn are constants (our training data) i.e. a linear combination of our variable w.

So, the original problem for hard-margin SVM seems like a "quadratic programming" problem - so my real question is this: why do we do the "dual" mapping to get the problem stated in terms of alpha? Is this purely to get it into a more convenient form for QP packages? I am missing something, but I don't know what :-).

[Elroch]

Originally Posted by alasdairj

Well, the problem was to minimize wrt w and b the value w'w (which is a combination of 2 values of our variable) subject to yn(w'xn + b) >= 1 where yn and xn are constants (our training data) i.e. a linear combination of our variable w.

So, the original problem for hard-margin SVM seems like a "quadratic programming" problem - so my real question is this: why do we do the "dual" mapping to get the problem stated in terms of alpha? Is this purely to get it into a more convenient form for QP packages? I am missing something, but I don't know what :-).

If I understand correctly, the motivation is that it is often computationally efficient to do so.

[yaser]

Originally Posted by alasdairj

the original problem for hard-margin SVM seems like a "quadratic programming" problem - so my real question is this: why do we do the "dual" mapping to get the problem stated in terms of alpha? Is this purely to get it into a more convenient form for QP packages? I am missing something, but I don't know what :-).

The number of variables in the original problem depends on the dimensionality of the weight space, whereas the number of variables in the dual problem does not. This makes a difference if that dimensionality is high, which is often the case in nonlinear transforms.

[alasdairj]

Thank you Professor! I understand now!