return 1 if already optimal, return 0 otherwise
| 968 | |
| 969 | // return 1 if already optimal, return 0 otherwise |
| 970 | int |
| 971 | Solver::select_working_set(int& out_i, int& out_j) |
| 972 | { |
| 973 | // return i,j such that |
| 974 | // i: maximizes -y_i * grad(f)_i, i in I_up(\alpha) |
| 975 | // j: minimizes the decrease of obj value |
| 976 | // (if quadratic coefficient <= 0, replace it with tau) |
| 977 | // -y_j*grad(f)_j < -y_i*grad(f)_i, j in I_low(\alpha) |
| 978 | |
| 979 | double Gmax = -INF; |
| 980 | double Gmax2 = -INF; |
| 981 | int Gmax_idx = -1; |
| 982 | int Gmin_idx = -1; |
| 983 | double obj_diff_min = INF; |
| 984 | |
| 985 | for (int t = 0; t < active_size; t++) |
| 986 | if (y[t] == +1) { |
| 987 | if (!is_upper_bound(t)) |
| 988 | if (-G[t] >= Gmax) { |
| 989 | Gmax = -G[t]; |
| 990 | Gmax_idx = t; |
| 991 | } |
| 992 | } |
| 993 | else { |
| 994 | if (!is_lower_bound(t)) |
| 995 | if (G[t] >= Gmax) { |
| 996 | Gmax = G[t]; |
| 997 | Gmax_idx = t; |
| 998 | } |
| 999 | } |
| 1000 | |
| 1001 | int i = Gmax_idx; |
| 1002 | |
| 1003 | const Qfloat* Q_i = nullptr; |
| 1004 | |
| 1005 | if (i != -1) // NULL Q_i not accessed: Gmax=-INF if i=-1 |
| 1006 | Q_i = Q->get_Q(i, active_size); |
| 1007 | |
| 1008 | for (int j = 0; j < active_size; j++) { |
| 1009 | if (y[j] == +1) { |
| 1010 | if (!is_lower_bound(j)) { |
| 1011 | double grad_diff = Gmax + G[j]; |
| 1012 | |
| 1013 | if (G[j] >= Gmax2) |
| 1014 | Gmax2 = G[j]; |
| 1015 | |
| 1016 | if (grad_diff > 0) { |
| 1017 | double obj_diff; |
| 1018 | double quad_coef = QD[i] + QD[j] - 2.0 * y[i] * Q_i[j]; |
| 1019 | |
| 1020 | if (quad_coef > 0) |
| 1021 | obj_diff = -(grad_diff * grad_diff) / quad_coef; |
| 1022 | else |
| 1023 | obj_diff = -(grad_diff * grad_diff) / TAU; |
| 1024 | |
| 1025 | if (obj_diff <= obj_diff_min) { |
| 1026 | Gmin_idx = j; |
| 1027 | obj_diff_min = obj_diff; |