cccccccccccccccccccccccccccccccccccccccccccccccccccccccccccc
c
c  SVM-QP, written by Katya Scheinberg, IBM Research, 2005.
c  to contact the author email at katyas'at'us'dot'ibm'dot'com
c
cccccccccccccccccccccccccccccccccccccccccccccccccccccccccccc

SVM-QP is a Fortran 77 code that aims at solving convex QPs defined by
SVM training. It is designed for the user who is able to parse the
data and set some paramters and then call SVM-QP as a subroutine and
interprete the results. A stand alone user friendly C++ version is
under development.

The algorithms used is described in the paper:

http://www.research.ibm.com/people/k/katya/incas.pdf


PARAMETER DESCRIBTION:
The call to SVM-QP looks as follows:
      subroutine svmqp(x, a, points, ipoints, lpnt, 
     .              lipnts, ipntr, lipntr,  c, r, maxn, 
     .              k, nrnka, dgr, shft, iprint, fullmem, 
     +              ninit, presolve, tol, wrk, lwrk,  iwrk, liwrk)

cccccccccccccccccccccccccccccccccccccccccccccccc
c   parameters of the routine
cccccccccccccccccccccccccccccccccccccccccccccccc
c
c   x      - the array of the Lagrange multimpliers (alphas, in the SVM literature)
c   y      - the negative bias of the linear separator (b or beta in SVM literature)
c   a      - the array of labels
c   points - the array containing the data in the sparse format, if the data is sparse
c            and if data is dense, then in dense format, storing one point after the other.
c   ipoints- the idices of the nonzero elements of the data points, if "points" is
c            a sparse array, otherwise ignore
c   lpnt   - the lenght of points
c   lipnts - length of ipoints
c   ipntr  - the array of pointers to the begining of each  data point in "points"
c            and "ipoints". 
c   linpnr - length of array 'ipntr'
c   c      - the penalty parameter
c   r      - the right hand side vector of length 'maxn', whose elements should all equal -1.
c            Subsequent versions will allow for different values of 'r'.
c   maxn   - the total number of points
c   maxns  - the maximum number of active support vectors allowed (see note at the end)
c   k      - the dimension of the data
c   nrnka  - maximum rank of the approximate Hessian used in presolve. See "presolve" details.
c   dgr    - the kernel parameter indicating degree for polynomial kernels (dgr=1 - linear kernel)
c            of indicating the RBF kernel (dgr=-1). Any other kernel has to be coded into
c            kernl.f file and idicated by another value of "dgr". 
c  shft    - the kernel parameter, shift in poly kernels and sigma in RBF kernels.
c  iprint  - print level. >=2, then each iteration info is printed, =1, then each 10th
c            iteration infor is printed, =0, then no iteration info is printed, only the
c            final output. If iprint < 0 then all output is supressed, even error messages.
c            ATTN: If printe level is >=3 then the list of support vectors will be printed at
c            the end of the run (if this set is large then pone should use caution with the option)
c  fullmem - the memory use level. Right now set fullmem=2 at all times.
c  ninit   - number of initial points, if an incremental mode is used.
c  presolve- a logical variable idicating if a presolve of the approximate low-rank
c            problems with an IPM is desired.
c  tol     - tolerance for solution
c  wrk     - double precision working space
c  lwrk    - the length of double precision working space (see note at the end)
c  iwrk    - integer working space
c  liwrk   - the length of integer working space (see note at the end)
c  
c
c

EXAMPLE OF THE ROUTINE CALL
For an example of a call to svmqp() see file main_svmqp.f. This file contains a main routine which 
reads a file incas.spc where some parameter values are set and also the test number is determined.
The test numbers are coded into the main routine and correspond to certain test case, that is
a certain file and the dimension of the data. For instance the following means a dense data set
called "random_dense" with 1000 points and dimension 10, stored in the file './random_ense'.
       if ( itest .eq. 1) then
c random dense problem
         maxn=1000
         k=10
         sparse=.false.
        data1 = './random_dense'

The file 'random_dense' is in a specific format convinient for Fortran use. Only  data files for
two simple test cases are  distributed with the code. If the user wants to use the main_svmqp
routine, but with his/her own data, he/she should contact the author. 

KERNELS:
The list of currently implemented kernel functions is: linear, polynomial and RBF, to add more kernel functions
either contact the author or modify the file kernl.f accordingly.

NOTE ON MEMORY: This version of SVM-QP has no memory saving mode. It is efficient in terms of time
to store the entire columns of the Kenrel matrix whose indices are in the set of active support vectors (
correspoding to data points on the margin). Since this is a Fortan 77  implementation, the momory is 
allocated statically in the beginning. Hecne, it is important to give an upper bound on the number
of columns we will store, i.e., the number of active support vectors. The bound can be arbitrarily
large, as long as the real working space that is provided is sufficient. Sepcifically
1. "lwrk" has to be no less that 11*maxn+maxns*maxns+maxn*maxns, with additional space of
(12*maxn+2*nrnka+3*maxns*nrnka) is preprocessing is used.
2. "liwrk" has to be no less than  (13*maxn+2*maxns) with additional space of maxn is preprocessing is used.

The user has to make sure that if 'maxn' or 'maxns'  increases then the working space
has to be increased accordingly.

A memory saving version is under development which will require only (11*maxn+maxns*maxns+50*maxn)
real memory, at the expense of the CPU time. Interested user should contact the author.


CONTACT:
For problems, questions, bug reports and imporvements requests please contact the author Katya Scheinberg,
at katyas@us.ibm.com

