question: 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 = 1000 ; 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 = 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 ) ; }
target:  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