24 double *v,
double lambda1,
double lambda2,
25 int p,
int g,
double * w,
double *G){
27 int i, j, newZeroNum, iterStep=0;
71 printf(
"\n Identify Zero Group: iterStep= %d. The code might have a bug! Check it!", iterStep);
85 for(j=(
int) w[3*i] ; j<= (int) w[3*i +1]; j++){
89 twoNorm=sqrt(twoNorm);
98 if (twoNorm<= lambda2 * w[3*i+2] ){
101 for(j=(
int) w[3*i] ; j<= (int) w[3*i +1]; j++)
129 if (zeroGroupFlag[i]==0)
135 double *u,
double *Y,
136 int p,
int g,
int *zeroGroupFlag,
137 double *G,
double *w){
146 if(zeroGroupFlag[i]){
148 for(j=(
int) w[3*i] ; j<= (int) w[3*i +1]; j++){
149 x[ (int) G[j] ] -= Y[j];
166 double *xnew,
double *Ynew,
167 double lambda2,
int g,
int *zeroGroupFlag,
168 double *G,
double *w){
171 double twoNorm, temp;
174 if(zeroGroupFlag[i]){
177 for(j=(
int) w[3*i] ; j<= (int) w[3*i +1]; j++){
178 temp=xnew[ (int) G[j] ];
184 twoNorm=sqrt(twoNorm);
187 temp=lambda2 * w[3*i+2] / twoNorm;
189 for(j=(
int) w[3*i] ; j<= (int) w[3*i +1]; j++)
194 for(j=(
int) w[3*i] ; j<= (int) w[3*i +1]; j++)
202 double *x,
double *Y,
int g,
int *zeroGroupFlag,
203 double *G,
double *w,
double lambda2){
206 double temp, twoNorm, innerProduct;
211 if(zeroGroupFlag[i]){
213 twoNorm=0;innerProduct=0;
215 for(j=(
int) w[3*i] ; j<= (int) w[3*i +1]; j++){
216 temp=x[ (int) G[j] ];
220 innerProduct+=temp * Y[j];
223 twoNorm=sqrt(twoNorm)* w[3*i +2];
227 twoNorm=lambda2 * twoNorm;
228 if (twoNorm > innerProduct)
229 *gap+=twoNorm-innerProduct;
235 double *v,
int p,
int g,
double lambda1,
double lambda2,
236 double *w,
double *G,
double *Y,
int maxIter,
int flag,
double tol){
238 int YSize=(int) w[3*(g-1) +1]+1;
239 double *u=(
double *)malloc(
sizeof(
double)*p);
240 double *y=(
double *)malloc(
sizeof(
double)*p);
242 double *xnew=(
double *)malloc(
sizeof(
double)*p);
243 double *Ynew=(
double *)malloc(
sizeof(
double)* YSize );
245 int *zeroGroupFlag=(
int *)malloc(
sizeof(
int)*g);
246 int *entrySignFlag=(
int *)malloc(
sizeof(
int)*p);
249 double twoNorm,temp, L=1, leftValue, rightValue, gapR, penalty2R;
250 int nextRestartStep=0;
280 if(zeroGroupFlag[i]){
285 for(j=(
int) w[3*i] ; j<= (int) w[3*i +1]; j++){
287 if (! u[ (
int) G[j] ] )
292 twoNorm=sqrt(twoNorm);
294 if (twoNorm > lambda2 * w[3*i+2] ){
295 temp=lambda2 * w[3*i+2] / twoNorm;
297 for(j=(
int) w[3*i] ; j<= (int) w[3*i +1]; j++)
302 for(j=(
int) w[3*i] ; j<= (int) w[3*i +1]; j++)
327 xFromY(x, y, u, Y, p, g, zeroGroupFlag, G, w);
332 for(iterStep=0;iterStep<maxIter;iterStep++){
355 if(zeroGroupFlag[i]){
358 for(j=(
int) w[3*i] ; j<= (int) w[3*i +1]; j++){
359 Ynew[j]= Y[j] + x[ (int) G[j] ] / L;
361 twoNorm+=Ynew[j]*Ynew[j];
363 twoNorm=sqrt(twoNorm);
365 if (twoNorm > lambda2 * w[3*i+2] ){
366 temp=lambda2 * w[3*i+2] / twoNorm;
368 for(j=(
int) w[3*i] ; j<= (int) w[3*i +1]; j++)
382 xFromY(xnew, y, u, Ynew, p, g, zeroGroupFlag, G, w);
387 if (entrySignFlag[i]){
390 leftValue+= temp * ( 0.5 * temp + y[i]);
396 if(zeroGroupFlag[i]){
398 for(j=(
int) w[3*i] ; j<= (int) w[3*i +1]; j++){
401 rightValue+=temp * temp;
405 rightValue=rightValue/2;
407 if ( leftValue <= L * rightValue){
409 temp= L * rightValue / leftValue;
417 temp=leftValue / rightValue;
427 if (rightValue < 1e-16){
432 printf(
"\n GD: leftValue=%e, rightValue=%e, ratio=%e", leftValue, rightValue, temp);
434 printf(
"\n L=%e > 2 * %d * %d. There might be a bug here. Otherwise, it is due to numerical issue.", L, g, g);
449 dualityGap(gap, penalty2, xnew, Ynew, g, zeroGroupFlag, G, w, lambda2);
465 if ( (flag==0) || (flag==1 && iterStep < nextRestartStep )){
468 memcpy(x, xnew,
sizeof(
double) * p);
469 memcpy(Y, Ynew,
sizeof(
double) * YSize);
496 YFromx(Y, xnew, Ynew, lambda2, g, zeroGroupFlag, G, w);
506 xFromY(x, y, u, Y, p, g, zeroGroupFlag, G, w);
515 dualityGap(&gapR, &penalty2R, x, Y, g, zeroGroupFlag, G, w, lambda2);
520 memcpy(x, xnew,
sizeof(
double) * p);
521 memcpy(Y, Ynew,
sizeof(
double) * YSize);
535 nextRestartStep=iterStep+ (int) sqrt(gapR / *gap);
558 penalty2[3]=iterStep;
562 if (zeroGroupFlag[i]==0)
563 penalty2[4]=penalty2[4]+1;
565 for(j=(
int) w[3*i] ; j<= (int) w[3*i +1]; j++){
566 if (x[ (
int) G[j] ] !=0)
570 if (j>(
int) w[3*i +1])
571 penalty2[4]=penalty2[4]+1;
579 if (entrySignFlag[i]==-1){
588 free (zeroGroupFlag);
589 free (entrySignFlag);
593 double *LL,
double *u,
double *y,
int *entrySignFlag,
double lambda2,
594 double *x,
double *Y,
int p,
int g,
int * zeroGroupFlag,
595 double *G,
double *w){
597 double twoNorm, temp, L=*LL, leftValue, rightValue;
609 if(zeroGroupFlag[i]){
612 for(j=(
int) w[3*i] ; j<= (int) w[3*i +1]; j++){
613 Ynew[j]= Y[j] + x[ (int) G[j] ] / L;
615 twoNorm+=Ynew[j]*Ynew[j];
617 twoNorm=sqrt(twoNorm);
619 if (twoNorm > lambda2 * w[3*i+2] ){
620 temp=lambda2 * w[3*i+2] / twoNorm;
622 for(j=(
int) w[3*i] ; j<= (int) w[3*i +1]; j++)
636 xFromY(xnew, y, u, Ynew, p, g, zeroGroupFlag, G, w);
641 if (entrySignFlag[i]){
644 leftValue+= temp * ( 0.5 * temp + y[i]);
650 if(zeroGroupFlag[i]){
652 for(j=(
int) w[3*i] ; j<= (int) w[3*i +1]; j++){
655 rightValue+=temp * temp;
659 rightValue=rightValue/2;
665 if ( leftValue <= L * rightValue){
667 temp= L * rightValue / leftValue;
675 temp=leftValue / rightValue;
682 if ( L / g - 2* g >0 ){
684 if (rightValue < 1e-16){
689 printf(
"\n One Gradient Step: leftValue=%e, rightValue=%e, ratio=%e", leftValue, rightValue, temp);
691 printf(
"\n L=%e > 2 * %d * %d. There might be a bug here. Otherwise, it is due to numerical issue.", L, g, g);
703 double *v,
int p,
int g,
double lambda1,
double lambda2,
704 double *w,
double *G,
double *Y,
int maxIter,
int flag,
double tol){
706 int YSize=(int) w[3*(g-1) +1]+1;
707 double *u=(
double *)malloc(
sizeof(
double)*p);
708 double *y=(
double *)malloc(
sizeof(
double)*p);
710 double *xnew=(
double *)malloc(
sizeof(
double)*p);
711 double *Ynew=(
double *)malloc(
sizeof(
double)* YSize );
713 double *xS=(
double *)malloc(
sizeof(
double)*p);
714 double *YS=(
double *)malloc(
sizeof(
double)* YSize );
717 double *Yp=(
double *)malloc(
sizeof(
double)* YSize );
719 int *zeroGroupFlag=(
int *)malloc(
sizeof(
int)*g);
720 int *entrySignFlag=(
int *)malloc(
sizeof(
int)*p);
724 double twoNorm,temp, L=1, leftValue, rightValue, gapR, penalty2R;
725 int nextRestartStep=0;
727 double alpha, alphap=0.5, beta, gamma;
756 if(zeroGroupFlag[i]){
761 for(j=(
int) w[3*i] ; j<= (int) w[3*i +1]; j++){
763 if (! u[ (
int) G[j] ] )
768 twoNorm=sqrt(twoNorm);
770 if (twoNorm > lambda2 * w[3*i+2] ){
771 temp=lambda2 * w[3*i+2] / twoNorm;
773 for(j=(
int) w[3*i] ; j<= (int) w[3*i +1]; j++)
778 for(j=(
int) w[3*i] ; j<= (int) w[3*i +1]; j++)
791 YS[i]=Yp[i]=Ynew[i]=0;
809 xFromY(x, y, u, Y, p, g, zeroGroupFlag, G, w);
822 &L, u, y,entrySignFlag,lambda2,
823 x, Y, p, g, zeroGroupFlag,
839 memcpy(Yp, Y,
sizeof(
double) * YSize);
842 memcpy(Y, Ynew,
sizeof(
double) * YSize);
853 for(iterStep=0;iterStep<maxIter;iterStep++){
866 alpha= ( - gamma + sqrt( gamma * gamma + 4 * L * gamma ) ) / 2 / L;
868 beta= gamma * (1-alphap)/ alphap / (gamma + L * alpha);
875 if(zeroGroupFlag[i]){
877 for(j=(
int) w[3*i] ; j<= (int) w[3*i +1]; j++){
879 YS[j]=Y[j] + beta * (Y[j]-Yp[j]);
889 xFromY(xS, y, u, YS, p, g, zeroGroupFlag, G, w);
898 if(zeroGroupFlag[i]){
901 for(j=(
int) w[3*i] ; j<= (int) w[3*i +1]; j++){
903 Ynew[j]= YS[j] + xS[ (int) G[j] ] / L;
905 twoNorm+=Ynew[j]*Ynew[j];
907 twoNorm=sqrt(twoNorm);
909 if (twoNorm > lambda2 * w[3*i+2] ){
910 temp=lambda2 * w[3*i+2] / twoNorm;
912 for(j=(
int) w[3*i] ; j<= (int) w[3*i +1]; j++)
927 xFromY(xnew, y, u, Ynew, p, g, zeroGroupFlag, G, w);
932 if (entrySignFlag[i]){
935 leftValue+= temp * ( 0.5 * temp + y[i]);
941 if(zeroGroupFlag[i]){
943 for(j=(
int) w[3*i] ; j<= (int) w[3*i +1]; j++){
946 rightValue+=temp * temp;
950 rightValue=rightValue/2;
952 if ( leftValue <= L * rightValue){
954 temp= L * rightValue / leftValue;
962 temp=leftValue / rightValue;
971 if ( L / g - 2* g >0 ){
973 if (rightValue < 1e-16){
978 printf(
"\n AGD: leftValue=%e, rightValue=%e, ratio=%e", leftValue, rightValue, temp);
980 printf(
"\n L=%e > 2 * %d * %d. There might be a bug here. Otherwise, it is due to numerical issue.", L, g, g);
996 xnew, Ynew, g, zeroGroupFlag,
1007 memcpy(x, xnew,
sizeof(
double) * p);
1008 memcpy(Y, Ynew,
sizeof(
double) * YSize);
1029 if ( (flag==0) || (flag==1 && iterStep < nextRestartStep )){
1033 memcpy(Yp, Y,
sizeof(
double) * YSize);
1036 memcpy(Y, Ynew,
sizeof(
double) * YSize);
1038 gamma=gamma * (1-alpha);
1067 YFromx(YS, xnew, Ynew, lambda2, g, zeroGroupFlag, G, w);
1077 xFromY(xS, y, u, YS, p, g, zeroGroupFlag, G, w);
1086 dualityGap(&gapR, &penalty2R, xS, YS, g, zeroGroupFlag, G, w, lambda2);
1098 memcpy(Yp, Y,
sizeof(
double) * YSize);
1101 memcpy(Y, Ynew,
sizeof(
double) * YSize);
1103 gamma=gamma * (1-alpha);
1107 nextRestartStep=iterStep+ (int) sqrt(gapR / *gap);
1113 *penalty2=penalty2R;
1117 memcpy(x, xS,
sizeof(
double) * p);
1118 memcpy(Y, YS,
sizeof(
double) * YSize);
1137 &L, u, y, entrySignFlag,lambda2,
1138 xS, YS, p, g, zeroGroupFlag,
1142 memcpy(Yp, YS,
sizeof(
double) * YSize);
1163 penalty2[3]=iterStep+1;
1171 if (zeroGroupFlag[i]==0)
1172 penalty2[4]=penalty2[4]+1;
1174 for(j=(
int) w[3*i] ; j<= (int) w[3*i +1]; j++){
1175 if (x[ (
int) G[j] ] !=0)
1179 if (j>(
int) w[3*i +1])
1180 penalty2[4]=penalty2[4]+1;
1189 if (entrySignFlag[i]==-1){
1206 free (zeroGroupFlag);
1207 free (entrySignFlag);
1211 double *v,
int p,
int g,
double lambda1,
double lambda2,
1212 double *w,
double *G,
double *Y,
int maxIter,
int flag,
double tol){
1218 v, p, g, lambda1, lambda2,
1219 w, G, Y, maxIter, flag,tol);
1225 v, p, g, lambda1, lambda2,
1226 w, G, Y, maxIter, flag-2,tol);
1233 v, p, g, lambda1, lambda2,
1234 w, G, Y, maxIter, 0,tol);
void identifySomeZeroEntries(double *u, int *zeroGroupFlag, int *entrySignFlag, int *pp, int *gg, double *v, double lambda1, double lambda2, int p, int g, double *w, double *G)
void YFromx(double *Y, double *xnew, double *Ynew, double lambda2, int g, int *zeroGroupFlag, double *G, double *w)
void overlapping_gd(double *x, double *gap, double *penalty2, double *v, int p, int g, double lambda1, double lambda2, double *w, double *G, double *Y, int maxIter, int flag, double tol)
void gradientDescentStep(double *xnew, double *Ynew, double *LL, double *u, double *y, int *entrySignFlag, double lambda2, double *x, double *Y, int p, int g, int *zeroGroupFlag, double *G, double *w)
void dualityGap(double *gap, double *penalty2, double *x, double *Y, int g, int *zeroGroupFlag, double *G, double *w, double lambda2)
void overlapping(double *x, double *gap, double *penalty2, double *v, int p, int g, double lambda1, double lambda2, double *w, double *G, double *Y, int maxIter, int flag, double tol)
void overlapping_agd(double *x, double *gap, double *penalty2, double *v, int p, int g, double lambda1, double lambda2, double *w, double *G, double *Y, int maxIter, int flag, double tol)
void xFromY(double *x, double *y, double *u, double *Y, int p, int g, int *zeroGroupFlag, double *G, double *w)