?? solver.cs
字號(hào):
float[] Q_j = Q.get_Q(j, active_size);
double C_i = get_C(i);
double C_j = get_C(j);
double old_alpha_i = alpha[i];
double old_alpha_j = alpha[j];
if (y[i] != y[j])
{
double quad_coef = Q_i[i] + Q_j[j] + 2 * Q_i[j];
if (quad_coef <= 0)
quad_coef = 1e-12;
double delta = (-G[i] - G[j]) / quad_coef;
double diff = alpha[i] - alpha[j];
alpha[i] += delta;
alpha[j] += delta;
if (diff > 0)
{
if (alpha[j] < 0)
{
alpha[j] = 0;
alpha[i] = diff;
}
}
else
{
if (alpha[i] < 0)
{
alpha[i] = 0;
alpha[j] = -diff;
}
}
if (diff > C_i - C_j)
{
if (alpha[i] > C_i)
{
alpha[i] = C_i;
alpha[j] = C_i - diff;
}
}
else
{
if (alpha[j] > C_j)
{
alpha[j] = C_j;
alpha[i] = C_j + diff;
}
}
}
else
{
double quad_coef = Q_i[i] + Q_j[j] - 2 * Q_i[j];
if (quad_coef <= 0)
quad_coef = 1e-12;
double delta = (G[i] - G[j]) / quad_coef;
double sum = alpha[i] + alpha[j];
alpha[i] -= delta;
alpha[j] += delta;
if (sum > C_i)
{
if (alpha[i] > C_i)
{
alpha[i] = C_i;
alpha[j] = sum - C_i;
}
}
else
{
if (alpha[j] < 0)
{
alpha[j] = 0;
alpha[i] = sum;
}
}
if (sum > C_j)
{
if (alpha[j] > C_j)
{
alpha[j] = C_j;
alpha[i] = sum - C_j;
}
}
else
{
if (alpha[i] < 0)
{
alpha[i] = 0;
alpha[j] = sum;
}
}
}
// update G
double delta_alpha_i = alpha[i] - old_alpha_i;
double delta_alpha_j = alpha[j] - old_alpha_j;
for (int k = 0; k < active_size; k++)
{
G[k] += Q_i[k] * delta_alpha_i + Q_j[k] * delta_alpha_j;
}
// update alpha_status and G_bar
{
bool ui = is_upper_bound(i);
bool uj = is_upper_bound(j);
update_alpha_status(i);
update_alpha_status(j);
int k;
if (ui != is_upper_bound(i))
{
Q_i = Q.get_Q(i, l);
if (ui)
for (k = 0; k < l; k++)
G_bar[k] -= C_i * Q_i[k];
else
for (k = 0; k < l; k++)
G_bar[k] += C_i * Q_i[k];
}
if (uj != is_upper_bound(j))
{
Q_j = Q.get_Q(j, l);
if (uj)
for (k = 0; k < l; k++)
G_bar[k] -= C_j * Q_j[k];
else
for (k = 0; k < l; k++)
G_bar[k] += C_j * Q_j[k];
}
}
}
// calculate rho
si.rho = calculate_rho();
// calculate objective value
{
double v = 0;
int i;
for (i = 0; i < l; i++)
v += alpha[i] * (G[i] + p[i]);
si.obj = v / 2;
}
// put back the solution
{
for (int i = 0; i < l; i++)
alpha_[active_set[i]] = alpha[i];
}
si.upper_bound_p = Cp;
si.upper_bound_n = Cn;
Debug.Write("\noptimization finished, #iter = " + iter + "\n");
}
// return 1 if already optimal, return 0 otherwise
protected virtual int select_working_set(int[] working_set)
{
// return i,j such that
// i: maximizes -y_i * grad(f)_i, i in I_up(\alpha)
// j: mimimizes the decrease of obj value
// (if quadratic coefficeint <= 0, replace it with tau)
// -y_j*grad(f)_j < -y_i*grad(f)_i, j in I_low(\alpha)
double Gmax = -INF;
double Gmax2 = -INF;
int Gmax_idx = -1;
int Gmin_idx = -1;
double obj_diff_min = INF;
for (int t = 0; t < active_size; t++)
if (y[t] == +1)
{
if (!is_upper_bound(t))
if (-G[t] >= Gmax)
{
Gmax = -G[t];
Gmax_idx = t;
}
}
else
{
if (!is_lower_bound(t))
if (G[t] >= Gmax)
{
Gmax = G[t];
Gmax_idx = t;
}
}
int i = Gmax_idx;
float[] Q_i = null;
if (i != -1) // null Q_i not accessed: Gmax=-INF if i=-1
Q_i = Q.get_Q(i, active_size);
for (int j = 0; j < active_size; j++)
{
if (y[j] == +1)
{
if (!is_lower_bound(j))
{
double grad_diff = Gmax + G[j];
if (G[j] >= Gmax2)
Gmax2 = G[j];
if (grad_diff > 0)
{
double obj_diff;
double quad_coef = Q_i[i] + QD[j] - 2 * y[i] * Q_i[j];
if (quad_coef > 0)
obj_diff = -(grad_diff * grad_diff) / quad_coef;
else
obj_diff = -(grad_diff * grad_diff) / 1e-12;
if (obj_diff <= obj_diff_min)
{
Gmin_idx = j;
obj_diff_min = obj_diff;
}
}
}
}
else
{
if (!is_upper_bound(j))
{
double grad_diff = Gmax - G[j];
if (-G[j] >= Gmax2)
Gmax2 = -G[j];
if (grad_diff > 0)
{
double obj_diff;
double quad_coef = Q_i[i] + QD[j] + 2 * y[i] * Q_i[j];
if (quad_coef > 0)
obj_diff = -(grad_diff * grad_diff) / quad_coef;
else
obj_diff = -(grad_diff * grad_diff) / 1e-12;
if (obj_diff <= obj_diff_min)
{
Gmin_idx = j;
obj_diff_min = obj_diff;
}
}
}
}
}
if (Gmax + Gmax2 < eps)
return 1;
working_set[0] = Gmax_idx;
working_set[1] = Gmin_idx;
return 0;
}
private bool be_shrunken(int i, double Gmax1, double Gmax2)
{
if (is_upper_bound(i))
{
if (y[i] == +1)
return (-G[i] > Gmax1);
else
return (-G[i] > Gmax2);
}
else if (is_lower_bound(i))
{
if (y[i] == +1)
return (G[i] > Gmax2);
else
return (G[i] > Gmax1);
}
else
return (false);
}
protected virtual void do_shrinking()
{
int i;
double Gmax1 = -INF; // max { -y_i * grad(f)_i | i in I_up(\alpha) }
double Gmax2 = -INF; // max { y_i * grad(f)_i | i in I_low(\alpha) }
// find maximal violating pair first
for (i = 0; i < active_size; i++)
{
if (y[i] == +1)
{
if (!is_upper_bound(i))
{
if (-G[i] >= Gmax1)
Gmax1 = -G[i];
}
if (!is_lower_bound(i))
{
if (G[i] >= Gmax2)
Gmax2 = G[i];
}
}
else
{
if (!is_upper_bound(i))
{
if (-G[i] >= Gmax2)
Gmax2 = -G[i];
}
if (!is_lower_bound(i))
{
if (G[i] >= Gmax1)
Gmax1 = G[i];
}
}
}
// shrink
for (i = 0; i < active_size; i++)
if (be_shrunken(i, Gmax1, Gmax2))
{
active_size--;
while (active_size > i)
{
if (!be_shrunken(active_size, Gmax1, Gmax2))
{
swap_index(i, active_size);
break;
}
active_size--;
}
}
// unshrink, check all variables again before sealed iterations
if (unshrinked || Gmax1 + Gmax2 > eps * 10) return;
unshrinked = true;
reconstruct_gradient();
for (i = l - 1; i >= active_size; i--)
if (!be_shrunken(i, Gmax1, Gmax2))
{
while (active_size < i)
{
if (be_shrunken(active_size, Gmax1, Gmax2))
{
swap_index(i, active_size);
break;
}
active_size++;
}
active_size++;
}
}
protected virtual double calculate_rho()
{
double r;
int nr_free = 0;
double ub = INF, lb = -INF, sum_free = 0;
for (int i = 0; i < active_size; i++)
{
double yG = y[i] * G[i];
if (is_lower_bound(i))
{
if (y[i] > 0)
ub = Math.Min(ub, yG);
else
lb = Math.Max(lb, yG);
}
else if (is_upper_bound(i))
{
?? 快捷鍵說(shuō)明
復(fù)制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號(hào)
Ctrl + =
減小字號(hào)
Ctrl + -