I was wondering what's the proper way to implement Quadprog to solve quadratic programming.
I have the following question(ripped from the internet)and also was looking at the following http://cbio.ensmp.fr/~thocking/mines-course/2011-04-01-svm/svm-qp.pdf
What would be the proper way to solve this issue? Would this tutorial be useful to solve if i was given a question like above? http://www.r-bloggers.com/solving-quadratic-progams-with-rs-quadprog-package/
Here is an implementation, for linear C-SVM, which is based on the primal optimization problem:
where
N
is the number of data points.Note that using
quadprog
to solve this is, to some degree, more of a pedagogical exercise, asquadprog
relies on an interior point algorithm, while in practice a specialized algorithm would be used, such as Platt's SMO, which takes advantage of particular properties of the SVM optimization problem.In order to use
quadprog
, given the equations above, it all boils down to setting up the matrices and vectors that specify the optimization problem.One issue, however, is that
quadprog
requires the matrix appearing in the quadratic function to be positive definite (see, for example, http://www.r-bloggers.com/more-on-quadratic-progamming-in-r/), while the implementation used here leads to it being positive semi-definite, since the interceptbeta_0
and thezeta_i
do not appear in the quadratic function. To go around this issue, I set the diagonal elements corresponding to these values in the matrix to a very small value.To setup the example code, using the
spam
dataset, a binary classification problem:In order to setup the optimization problem, keep in mind the format employed by package
quadprog
:Then, organizing the parameter vector as:
such that:
Finally, solve the optimization problem and retrieve the parameter values:
Afterwards, given a matrix
X_test
, the model can be used to predict via: