private static void solve_l2r_l1l2_svr(Problem prob,double[] w,Parameter param){
  int l=prob.l;
  double C=param.C;
  double p=param.p;
  int w_size=prob.n;
  double eps=param.eps;
  int i, s, iter=0;
  int max_iter=param.getMaxIters();
  int active_size=l;
  int[] index=new int[l];
  double d, G, H;
  double Gmax_old=Double.POSITIVE_INFINITY;
  double Gmax_new, Gnorm1_new;
  double Gnorm1_init=-1.0;
  double[] beta=new double[l];
  double[] QD=new double[l];
  double[] y=prob.y;
  double[] lambda=new double[]{0.5 / C};
  double[] upper_bound=new double[]{Double.POSITIVE_INFINITY};
  if (param.solverType == SolverType.L2R_L1LOSS_SVR_DUAL) {
    lambda[0]=0;
    upper_bound[0]=C;
  }
  for (i=0; i < l; i++)   beta[i]=0;
  for (i=0; i < w_size; i++)   w[i]=0;
  for (i=0; i < l; i++) {
    QD[i]=0;
    for (    Feature xi : prob.x[i]) {
      double val=xi.getValue();
      QD[i]+=val * val;
      w[xi.getIndex() - 1]+=beta[i] * val;
    }
    index[i]=i;
  }
  while (iter < max_iter) {
    Gmax_new=0;
    Gnorm1_new=0;
    for (i=0; i < active_size; i++) {
      int j=i + random.nextInt(active_size - i);
      swap(index,i,j);
    }
    for (s=0; s < active_size; s++) {
      i=index[s];
      G=-y[i] + lambda[GETI_SVR(i)] * beta[i];
      H=QD[i] + lambda[GETI_SVR(i)];
      for (      Feature xi : prob.x[i]) {
        int ind=xi.getIndex() - 1;
        double val=xi.getValue();
        G+=val * w[ind];
      }
      double Gp=G + p;
      double Gn=G - p;
      double violation=0;
      if (beta[i] == 0) {
        if (Gp < 0)         violation=-Gp;
 else         if (Gn > 0)         violation=Gn;
 else         if (Gp > Gmax_old && Gn < -Gmax_old) {
          active_size--;
          swap(index,s,active_size);
          s--;
          continue;
        }
      }
 else       if (beta[i] >= upper_bound[GETI_SVR(i)]) {
        if (Gp > 0)         violation=Gp;
 else         if (Gp < -Gmax_old) {
          active_size--;
          swap(index,s,active_size);
          s--;
          continue;
        }
      }
 else       if (beta[i] <= -upper_bound[GETI_SVR(i)]) {
        if (Gn < 0)         violation=-Gn;
 else         if (Gn > Gmax_old) {
          active_size--;
          swap(index,s,active_size);
          s--;
          continue;
        }
      }
 else       if (beta[i] > 0)       violation=Math.abs(Gp);
 else       violation=Math.abs(Gn);
      Gmax_new=Math.max(Gmax_new,violation);
      Gnorm1_new+=violation;
      if (Gp < H * beta[i])       d=-Gp / H;
 else       if (Gn > H * beta[i])       d=-Gn / H;
 else       d=-beta[i];
      if (Math.abs(d) < 1.0e-12)       continue;
      double beta_old=beta[i];
      beta[i]=Math.min(Math.max(beta[i] + d,-upper_bound[GETI_SVR(i)]),upper_bound[GETI_SVR(i)]);
      d=beta[i] - beta_old;
      if (d != 0) {
        for (        Feature xi : prob.x[i]) {
          w[xi.getIndex() - 1]+=d * xi.getValue();
        }
      }
    }
    if (iter == 0)     Gnorm1_init=Gnorm1_new;
    iter++;
    if (iter % 10 == 0)     info(".");
    if (Gnorm1_new <= eps * Gnorm1_init) {
      if (active_size == l)       break;
 else {
        active_size=l;
        info("*");
        Gmax_old=Double.POSITIVE_INFINITY;
        continue;
      }
    }
    Gmax_old=Gmax_new;
  }
  info("%noptimization finished, #iter = %d%n",iter);
  if (iter >= max_iter)   info("%nWARNING: reaching max number of iterations%nUsing -s 11 may be faster%n%n");
  double v=0;
  int nSV=0;
  for (i=0; i < w_size; i++)   v+=w[i] * w[i];
  v=0.5 * v;
  for (i=0; i < l; i++) {
    v+=p * Math.abs(beta[i]) - y[i] * beta[i] + 0.5 * lambda[GETI_SVR(i)] * beta[i]* beta[i];
    if (beta[i] != 0)     nSV++;
  }
  info("Objective value = %g%n",v);
  info("nSV = %d%n",nSV);
}

private static void solve_l2r_l1l2_svr ( Problem prob , double [ ] w , Parameter param ) { int l = prob . l ; double C = param . C ; double p = param . p ; int w_size = prob . n ; double eps = param . eps ; int i , s , iter = 0 ; int max_iter = param . getMaxIters ( ) ; int active_size = l ; int [ ] index = new int [ l ] ; double d , G , H ; double Gmax_old = Double . POSITIVE_INFINITY ; double Gmax_new , Gnorm1_new ; double Gnorm1_init = - 1.0 ; double [ ] beta = new double [ l ] ; double [ ] QD = new double [ l ] ; double [ ] y = prob . y ; double [ ] lambda = new double [ ] { 0.5 / C } ; double [ ] upper_bound = new double [ ] { Double . POSITIVE_INFINITY } ; if ( param . solverType == SolverType . L2R_L1LOSS_SVR_DUAL ) { lambda [ 0 ] = 0 ; upper_bound [ 0 ] = C ; } for ( i = 0 ; i < l ; i ++ ) beta [ i ] = 0 ; for ( i = 0 ; i < w_size ; i ++ ) w [ i ] = 0 ; for ( i = 0 ; i < l ; i ++ ) { QD [ i ] = 0 ; for ( Feature xi : prob . x [ i ] ) { double val = xi . getValue ( ) ; QD [ i ] += val * val ; w [ xi . getIndex ( ) - 1 ] += beta [ i ] * val ; } index [ i ] = i ; } while ( iter < max_iter ) { Gmax_new = 0 ; Gnorm1_new = 0 ; for ( i = 0 ; i < active_size ; i ++ ) { int j = i + random . nextInt ( active_size - i ) ; swap ( index , i , j ) ; } for ( s = 0 ; s < active_size ; s ++ ) { i = index [ s ] ; G = - y [ i ] + lambda [ GETI_SVR ( i ) ] * beta [ i ] ; H = QD [ i ] + lambda [ GETI_SVR ( i ) ] ; for ( Feature xi : prob . x [ i ] ) { int ind = xi . getIndex ( ) - 1 ; double val = xi . getValue ( ) ; G += val * w [ ind ] ; } double Gp = G + p ; double Gn = G - p ; double violation = 0 ; if ( beta [ i ] == 0 ) { if ( Gp < 0 ) violation = - Gp ; else if ( Gn > 0 ) violation = Gn ; else if ( Gp > Gmax_old && Gn < - Gmax_old ) { active_size -- ; swap ( index , s , active_size ) ; s -- ; continue ; } } else if ( beta [ i ] >= upper_bound [ GETI_SVR ( i ) ] ) { if ( Gp > 0 ) violation = Gp ; else if ( Gp < - Gmax_old ) { active_size -- ; swap ( index , s , active_size ) ; s -- ; continue ; } } else if ( beta [ i ] <= - upper_bound [ GETI_SVR ( i ) ] ) { if ( Gn < 0 ) violation = - Gn ; else if ( Gn > Gmax_old ) { active_size -- ; swap ( index , s , active_size ) ; s -- ; continue ; } } else if ( beta [ i ] > 0 ) violation = Math . abs ( Gp ) ; else violation = Math . abs ( Gn ) ; Gmax_new = Math . max ( Gmax_new , violation ) ; Gnorm1_new += violation ; if ( Gp < H * beta [ i ] ) d = - Gp / H ; else if ( Gn > H * beta [ i ] ) d = - Gn / H ; else d = - beta [ i ] ; if ( Math . abs ( d ) < 1.0e-12 ) continue ; double beta_old = beta [ i ] ; beta [ i ] = Math . min ( Math . max ( beta [ i ] + d , - upper_bound [ GETI_SVR ( i ) ] ) , upper_bound [ GETI_SVR ( i ) ] ) ; d = beta [ i ] - beta_old ; if ( d != 0 ) { for ( Feature xi : prob . x [ i ] ) { w [ xi . getIndex ( ) - 1 ] += d * xi . getValue ( ) ; } } } if ( iter == 0 ) Gnorm1_init = Gnorm1_new ; iter ++ ; if ( iter % 10 == 0 ) info ( "." ) ; if ( Gnorm1_new <= eps * Gnorm1_init ) { if ( active_size == l ) break ; else { active_size = l ; info ( "*" ) ; Gmax_old = Double . POSITIVE_INFINITY ; continue ; } } Gmax_old = Gmax_new ; } info ( "%noptimization finished, #iter = %d%n" , iter ) ; if ( iter >= max_iter ) info ( "%nWARNING: reaching max number of iterations%nUsing -s 11 may be faster%n%n" ) ; double v = 0 ; int nSV = 0 ; for ( i = 0 ; i < w_size ; i ++ ) v += w [ i ] * w [ i ] ; v = 0.5 * v ; for ( i = 0 ; i < l ; i ++ ) { v += p * Math . abs ( beta [ i ] ) - y [ i ] * beta [ i ] + 0.5 * lambda [ GETI_SVR ( i ) ] * beta [ i ] * beta [ i ] ; if ( beta [ i ] != 0 ) nSV ++ ; } info ( "Objective value = %g%n" , v ) ; info ( "nSV = %d%n" , nSV ) ; }
a coordinate descent algorithm for l1 - loss and l2 - loss epsilon - svr dual problem min_ \ beta 0 . 5 \ beta ^ t ( q + diag ( lambda ) ) \ beta - p \ sum_ { i = 1 } ^ l | \ beta_i | + \ sum_ { i = 1 } ^ l yi \ beta_i , s . t . - upper_bound_i < = \ beta_i < = upper_bound_i , where qij = xi ^ t xj and d is a diagonal matrix in l1 - svm case : upper_bound_i = c lambda_i = 0 in l2 - svm case : upper_bound_i = inf lambda_i = 1 / ( 2 * c ) given : x , y , p , c eps is the stopping tolerance solution will be put in w see algorithm 4 of ho and lin , 2012
