21 double *v,
double lambda1,
double lambda2,
22 int p,
int g,
double * w,
double *G){
24 int i, j, newZeroNum, iterStep=0;
68 printf(
"\n Identify Zero Group: iterStep= %d. The code might have a bug! Check it!", iterStep);
82 for(j=(
int) w[3*i] ; j<= (int) w[3*i +1]; j++){
86 twoNorm=sqrt(twoNorm);
95 if (twoNorm<= lambda2 * w[3*i+2] ){
98 for(j=(
int) w[3*i] ; j<= (int) w[3*i +1]; j++)
126 if (zeroGroupFlag[i]==0)
132 double *u,
double *Y,
133 int p,
int g,
int *zeroGroupFlag,
134 double *G,
double *w){
143 if(zeroGroupFlag[i]){
145 for(j=(
int) w[3*i] ; j<= (int) w[3*i +1]; j++){
146 x[ (int) G[j] ] -= Y[j];
163 double *xnew,
double *Ynew,
164 double lambda2,
int g,
int *zeroGroupFlag,
165 double *G,
double *w){
168 double twoNorm, temp;
171 if(zeroGroupFlag[i]){
174 for(j=(
int) w[3*i] ; j<= (int) w[3*i +1]; j++){
175 temp=xnew[ (int) G[j] ];
181 twoNorm=sqrt(twoNorm);
184 temp=lambda2 * w[3*i+2] / twoNorm;
186 for(j=(
int) w[3*i] ; j<= (int) w[3*i +1]; j++)
191 for(j=(
int) w[3*i] ; j<= (int) w[3*i +1]; j++)
199 double *x,
double *Y,
int g,
int *zeroGroupFlag,
200 double *G,
double *w,
double lambda2){
203 double temp, twoNorm, innerProduct;
208 if(zeroGroupFlag[i]){
210 twoNorm=0;innerProduct=0;
212 for(j=(
int) w[3*i] ; j<= (int) w[3*i +1]; j++){
213 temp=x[ (int) G[j] ];
217 innerProduct+=temp * Y[j];
220 twoNorm=sqrt(twoNorm)* w[3*i +2];
224 twoNorm=lambda2 * twoNorm;
225 if (twoNorm > innerProduct)
226 *gap+=twoNorm-innerProduct;
232 double *v,
int p,
int g,
double lambda1,
double lambda2,
233 double *w,
double *G,
double *Y,
int maxIter,
int flag,
double tol){
235 int YSize=(int) w[3*(g-1) +1]+1;
236 double *u=(
double *)malloc(
sizeof(
double)*p);
237 double *y=(
double *)malloc(
sizeof(
double)*p);
239 double *xnew=(
double *)malloc(
sizeof(
double)*p);
240 double *Ynew=(
double *)malloc(
sizeof(
double)* YSize );
242 int *zeroGroupFlag=(
int *)malloc(
sizeof(
int)*g);
243 int *entrySignFlag=(
int *)malloc(
sizeof(
int)*p);
246 double twoNorm,temp, L=1, leftValue, rightValue, gapR, penalty2R;
247 int nextRestartStep=0;
277 if(zeroGroupFlag[i]){
282 for(j=(
int) w[3*i] ; j<= (int) w[3*i +1]; j++){
284 if (! u[ (
int) G[j] ] )
289 twoNorm=sqrt(twoNorm);
291 if (twoNorm > lambda2 * w[3*i+2] ){
292 temp=lambda2 * w[3*i+2] / twoNorm;
294 for(j=(
int) w[3*i] ; j<= (int) w[3*i +1]; j++)
299 for(j=(
int) w[3*i] ; j<= (int) w[3*i +1]; j++)
324 xFromY(x, y, u, Y, p, g, zeroGroupFlag, G, w);
329 for(iterStep=0;iterStep<maxIter;iterStep++){
352 if(zeroGroupFlag[i]){
355 for(j=(
int) w[3*i] ; j<= (int) w[3*i +1]; j++){
356 Ynew[j]= Y[j] + x[ (int) G[j] ] / L;
358 twoNorm+=Ynew[j]*Ynew[j];
360 twoNorm=sqrt(twoNorm);
362 if (twoNorm > lambda2 * w[3*i+2] ){
363 temp=lambda2 * w[3*i+2] / twoNorm;
365 for(j=(
int) w[3*i] ; j<= (int) w[3*i +1]; j++)
379 xFromY(xnew, y, u, Ynew, p, g, zeroGroupFlag, G, w);
384 if (entrySignFlag[i]){
387 leftValue+= temp * ( 0.5 * temp + y[i]);
393 if(zeroGroupFlag[i]){
395 for(j=(
int) w[3*i] ; j<= (int) w[3*i +1]; j++){
398 rightValue+=temp * temp;
402 rightValue=rightValue/2;
404 if ( leftValue <= L * rightValue){
406 temp= L * rightValue / leftValue;
414 temp=leftValue / rightValue;
424 if (rightValue < 1e-16){
429 printf(
"\n GD: leftValue=%e, rightValue=%e, ratio=%e", leftValue, rightValue, temp);
431 printf(
"\n L=%e > 2 * %d * %d. There might be a bug here. Otherwise, it is due to numerical issue.", L, g, g);
446 dualityGap(gap, penalty2, xnew, Ynew, g, zeroGroupFlag, G, w, lambda2);
462 if ( (flag==0) || (flag==1 && iterStep < nextRestartStep )){
465 memcpy(x, xnew,
sizeof(
double) * p);
466 memcpy(Y, Ynew,
sizeof(
double) * YSize);
493 YFromx(Y, xnew, Ynew, lambda2, g, zeroGroupFlag, G, w);
503 xFromY(x, y, u, Y, p, g, zeroGroupFlag, G, w);
512 dualityGap(&gapR, &penalty2R, x, Y, g, zeroGroupFlag, G, w, lambda2);
517 memcpy(x, xnew,
sizeof(
double) * p);
518 memcpy(Y, Ynew,
sizeof(
double) * YSize);
532 nextRestartStep=iterStep+ (int) sqrt(gapR / *gap);
555 penalty2[3]=iterStep;
559 if (zeroGroupFlag[i]==0)
560 penalty2[4]=penalty2[4]+1;
562 for(j=(
int) w[3*i] ; j<= (int) w[3*i +1]; j++){
563 if (x[ (
int) G[j] ] !=0)
567 if (j>(
int) w[3*i +1])
568 penalty2[4]=penalty2[4]+1;
576 if (entrySignFlag[i]==-1){
585 free (zeroGroupFlag);
586 free (entrySignFlag);
590 double *LL,
double *u,
double *y,
int *entrySignFlag,
double lambda2,
591 double *x,
double *Y,
int p,
int g,
int * zeroGroupFlag,
592 double *G,
double *w){
594 double twoNorm, temp, L=*LL, leftValue, rightValue;
606 if(zeroGroupFlag[i]){
609 for(j=(
int) w[3*i] ; j<= (int) w[3*i +1]; j++){
610 Ynew[j]= Y[j] + x[ (int) G[j] ] / L;
612 twoNorm+=Ynew[j]*Ynew[j];
614 twoNorm=sqrt(twoNorm);
616 if (twoNorm > lambda2 * w[3*i+2] ){
617 temp=lambda2 * w[3*i+2] / twoNorm;
619 for(j=(
int) w[3*i] ; j<= (int) w[3*i +1]; j++)
633 xFromY(xnew, y, u, Ynew, p, g, zeroGroupFlag, G, w);
638 if (entrySignFlag[i]){
641 leftValue+= temp * ( 0.5 * temp + y[i]);
647 if(zeroGroupFlag[i]){
649 for(j=(
int) w[3*i] ; j<= (int) w[3*i +1]; j++){
652 rightValue+=temp * temp;
656 rightValue=rightValue/2;
662 if ( leftValue <= L * rightValue){
664 temp= L * rightValue / leftValue;
672 temp=leftValue / rightValue;
679 if ( L / g - 2* g >0 ){
681 if (rightValue < 1e-16){
686 printf(
"\n One Gradient Step: leftValue=%e, rightValue=%e, ratio=%e", leftValue, rightValue, temp);
688 printf(
"\n L=%e > 2 * %d * %d. There might be a bug here. Otherwise, it is due to numerical issue.", L, g, g);
700 double *v,
int p,
int g,
double lambda1,
double lambda2,
701 double *w,
double *G,
double *Y,
int maxIter,
int flag,
double tol){
703 int YSize=(int) w[3*(g-1) +1]+1;
704 double *u=(
double *)malloc(
sizeof(
double)*p);
705 double *y=(
double *)malloc(
sizeof(
double)*p);
707 double *xnew=(
double *)malloc(
sizeof(
double)*p);
708 double *Ynew=(
double *)malloc(
sizeof(
double)* YSize );
710 double *xS=(
double *)malloc(
sizeof(
double)*p);
711 double *YS=(
double *)malloc(
sizeof(
double)* YSize );
714 double *Yp=(
double *)malloc(
sizeof(
double)* YSize );
716 int *zeroGroupFlag=(
int *)malloc(
sizeof(
int)*g);
717 int *entrySignFlag=(
int *)malloc(
sizeof(
int)*p);
721 double twoNorm,temp, L=1, leftValue, rightValue, gapR, penalty2R;
722 int nextRestartStep=0;
724 double alpha, alphap=0.5, beta, gamma;
753 if(zeroGroupFlag[i]){
758 for(j=(
int) w[3*i] ; j<= (int) w[3*i +1]; j++){
760 if (! u[ (
int) G[j] ] )
765 twoNorm=sqrt(twoNorm);
767 if (twoNorm > lambda2 * w[3*i+2] ){
768 temp=lambda2 * w[3*i+2] / twoNorm;
770 for(j=(
int) w[3*i] ; j<= (int) w[3*i +1]; j++)
775 for(j=(
int) w[3*i] ; j<= (int) w[3*i +1]; j++)
788 YS[i]=Yp[i]=Ynew[i]=0;
806 xFromY(x, y, u, Y, p, g, zeroGroupFlag, G, w);
819 &L, u, y,entrySignFlag,lambda2,
820 x, Y, p, g, zeroGroupFlag,
836 memcpy(Yp, Y,
sizeof(
double) * YSize);
839 memcpy(Y, Ynew,
sizeof(
double) * YSize);
850 for(iterStep=0;iterStep<maxIter;iterStep++){
863 alpha= ( - gamma + sqrt( gamma * gamma + 4 * L * gamma ) ) / 2 / L;
865 beta= gamma * (1-alphap)/ alphap / (gamma + L * alpha);
872 if(zeroGroupFlag[i]){
874 for(j=(
int) w[3*i] ; j<= (int) w[3*i +1]; j++){
876 YS[j]=Y[j] + beta * (Y[j]-Yp[j]);
886 xFromY(xS, y, u, YS, p, g, zeroGroupFlag, G, w);
895 if(zeroGroupFlag[i]){
898 for(j=(
int) w[3*i] ; j<= (int) w[3*i +1]; j++){
900 Ynew[j]= YS[j] + xS[ (int) G[j] ] / L;
902 twoNorm+=Ynew[j]*Ynew[j];
904 twoNorm=sqrt(twoNorm);
906 if (twoNorm > lambda2 * w[3*i+2] ){
907 temp=lambda2 * w[3*i+2] / twoNorm;
909 for(j=(
int) w[3*i] ; j<= (int) w[3*i +1]; j++)
924 xFromY(xnew, y, u, Ynew, p, g, zeroGroupFlag, G, w);
929 if (entrySignFlag[i]){
932 leftValue+= temp * ( 0.5 * temp + y[i]);
938 if(zeroGroupFlag[i]){
940 for(j=(
int) w[3*i] ; j<= (int) w[3*i +1]; j++){
943 rightValue+=temp * temp;
947 rightValue=rightValue/2;
949 if ( leftValue <= L * rightValue){
951 temp= L * rightValue / leftValue;
959 temp=leftValue / rightValue;
968 if ( L / g - 2* g >0 ){
970 if (rightValue < 1e-16){
975 printf(
"\n AGD: leftValue=%e, rightValue=%e, ratio=%e", leftValue, rightValue, temp);
977 printf(
"\n L=%e > 2 * %d * %d. There might be a bug here. Otherwise, it is due to numerical issue.", L, g, g);
993 xnew, Ynew, g, zeroGroupFlag,
1004 memcpy(x, xnew,
sizeof(
double) * p);
1005 memcpy(Y, Ynew,
sizeof(
double) * YSize);
1026 if ( (flag==0) || (flag==1 && iterStep < nextRestartStep )){
1030 memcpy(Yp, Y,
sizeof(
double) * YSize);
1033 memcpy(Y, Ynew,
sizeof(
double) * YSize);
1035 gamma=gamma * (1-alpha);
1064 YFromx(YS, xnew, Ynew, lambda2, g, zeroGroupFlag, G, w);
1074 xFromY(xS, y, u, YS, p, g, zeroGroupFlag, G, w);
1083 dualityGap(&gapR, &penalty2R, xS, YS, g, zeroGroupFlag, G, w, lambda2);
1095 memcpy(Yp, Y,
sizeof(
double) * YSize);
1098 memcpy(Y, Ynew,
sizeof(
double) * YSize);
1100 gamma=gamma * (1-alpha);
1104 nextRestartStep=iterStep+ (int) sqrt(gapR / *gap);
1110 *penalty2=penalty2R;
1114 memcpy(x, xS,
sizeof(
double) * p);
1115 memcpy(Y, YS,
sizeof(
double) * YSize);
1134 &L, u, y, entrySignFlag,lambda2,
1135 xS, YS, p, g, zeroGroupFlag,
1139 memcpy(Yp, YS,
sizeof(
double) * YSize);
1160 penalty2[3]=iterStep+1;
1168 if (zeroGroupFlag[i]==0)
1169 penalty2[4]=penalty2[4]+1;
1171 for(j=(
int) w[3*i] ; j<= (int) w[3*i +1]; j++){
1172 if (x[ (
int) G[j] ] !=0)
1176 if (j>(
int) w[3*i +1])
1177 penalty2[4]=penalty2[4]+1;
1186 if (entrySignFlag[i]==-1){
1203 free (zeroGroupFlag);
1204 free (entrySignFlag);
1208 double *v,
int p,
int g,
double lambda1,
double lambda2,
1209 double *w,
double *G,
double *Y,
int maxIter,
int flag,
double tol){
1215 v, p, g, lambda1, lambda2,
1216 w, G, Y, maxIter, flag,tol);
1222 v, p, g, lambda1, lambda2,
1223 w, G, Y, maxIter, flag-2,tol);
1230 v, p, g, lambda1, lambda2,
1231 w, G, Y, maxIter, 0,tol);