View Single Post
Old 02-25-2013, 11:30 AM
hemphill hemphill is offline
Join Date: Jan 2013
Posts: 18
Default Re: What Quadratic Programming Package?

I've tried the C package below, and it gives mostly correct results (as far as I know), although the running time varies widely, and sometimes it seems to loop forever. It is a fairly minimal implementation, e.g. it is assumed that the caller will provide a feasible solution to start with. Fortunately, alpha = 0 satisfies the bounds and is therefore a feasible solution of the quadratic program.

I've also downloaded SupportVectorMachines.nb and MathSVM.m for Mathematica from the below URL. I've examined the code and it appears to do more or less the right thing, but also seems like a minimal implementation.

I finally went with CGAL in C++ which has an exceptional pedigree. It was also very easy to install on my Fedora Linux system. ("yum install CGAL\*"). I can get around in C++, but I am hardly an expert. What I did was take a couple of the example programs and cobble them together.

"/usr/share/CGAL/QP_solver/print_first_nonnegative_qp_from_mps.cpp" almost did what I wanted, but I changed the prototyping to use floating point instead of integer arithmetic, borrowing the prototypes from "/usr/share/CGAL/QP_solver/cycling.cpp". The code solves both linear and quadratic programs, and if you define them using integers, then it gives exact rational solutions using multiple precision arithmetic. If you use floating point, it also works out the solution using exact, multiple precision arithmetic. (Which is why it prints the weights as ratios of two floating point numbers.) This particular example program reads the quadratic program from an .mps file, which is defined in the CGAL manual. I modified the example program to read from the standard input. It already wrote the solution on the standard output. This meant that I had a utility program that I could now call from any programming language. My language of choice for this exercise was C. The CGAL manual was not part of the Fedora Linux package, but I was able to obtain it from:

Lastly, if you want to roll your own, a nice overview can be had in

Keerthi, S.S. & Gilbert, E.G.(2002)Convergence of a Generalized SMO Algorithm for SVM Classifier Design. Machine Learning, 46, 351--360, 2002, Kluwer Academic Publishers.

Additional details can be found in the references, including:

Keerthi, S.S., Shevade, S.K., Bhattacharyya, C. & Murthy, K.R.K.(1999)Improvements to Platt's SMO algorithm for SVM classifier design. Technical Report CD-99-14, Control Division, Dept. of Mechanical and Production Engineering, National University of Singapore.

I had no trouble obtaining free copies of these documents by Googling on their titles.
Reply With Quote