#include "stdio.h"
#include "math.h"
#include "conio.h"
#define N 2
#define N1 1
#define N2 1
#define derta 0.000001

#define epslion1 0.00001
#define epslion2 0.00001

#define beta 0.618
#define ls0
#define F
double la,lb;
int control_df=-1;
int n=N;
      
double max(double a,double b)          /*求最大值和最小值*/
{
  double c;
  //printf("\n**************       The Max         ***********\n");
  if(a>=b)c=a;
  if(a<b)c=b;
  //printf("the max=%f\n**************  The Max end     ***********\n",c);
  return (c);
 }

double min(double a,double b)
 {
  double c;
  //printf("\n**************           The Min          ***********\n");*/
  if(a<=b)c=a;
  if(a>b)c=b;
  /*printf("the min=%f\n**************     The Min end    ***********\n",c);*/
  return (c);
 }

double function(double b[],int j,int n,double a_v[],double a_lumda[],double a_miu,int n1,int n2)   /*函數(shù)*/
 {
  double result,t,t1=0;
  /*printf("\n**************           The function         *************\n");*/
  
   t=a_v[0]-2*a_miu*(-b[0]+b[1]-2);
   //printf("t=%f \n",t);
   t=max(t1,t);
  //printf("t1=%f t=%f\n",t1,t);
   
 result=b[0]*b[0]+2*b[1]*b[1]+(1.0/(4*a_miu))*(t*t-a_v[0]*a_v[0])-a_lumda[0]*(b[0]+b[1]-6)+a_miu*(b[0]+b[1]-6)*(b[0]+b[1]-6);
  
 //printf("result=%f\n**************         The function end         *************\n",result); 
  //getch();
  return (result);

 }

double d_fun(double a[],int j,int n,double a_v[],double a_lumda[],double a_miu,int n1,int n2)      /*求導(dǎo)數(shù)control_df=-1表示只求函數(shù)值*/
 {
  double t1,t2,result;
  /*printf("\n&&&&&&&&&&&&&&&    The d_fun         &&&&&&&&&&&&&\n"); */
  if(j!=-1){a[j]=a[j]+derta;}
  t1=function(a,j,n,a_v,a_lumda,a_miu,n1,n2);
  //printf("t1=%f\n",t1);
  if(j!=-1)a[j]=a[j]-derta;
  t2=function(a,control_df,n,a_v,a_lumda,a_miu,n1,n2);
  //printf("t2=%f\n",t2);
  result=(t1-t2)/derta;
  //printf("result=%f\n",result);
 // printf("f(derta)=%f f=%f f'=%f\n**************       The d_fun end       *************\n",t1,t2,result); 
  return (result);
 }

double function_s(double a_xk[],int j)
{
 double result;
 //printf("\n******************** the function_s *********************\n");
 switch(j)
	{
     case 0: result=-a_xk[0]+a_xk[1]-2;break;
    }
  //printf("function_s=%f\n",result);
 //getch();
 //printf("\n******************** the function_s end!!! *********************\n");
 return (result);

}

double function_h(double a_xk[],int j)
{
  double result;
  //printf("\n******************** the function_h  *********************\n");
  switch(j)
	{
	 case 0:result=a_xk[0]+a_xk[1]-6;break;
	 
	}
    printf("function_h=%f\n",result);
  //getch();
  //printf("\n******************** the function_h end!!!! *********************\n");
  return(result);
}

double fai_k(double a_xk[],double a_v[],int n1,int n2,double a_miu)
{
 double result,sum=0,sum1=0,vi,h,s,m;
 int i;
 //printf("\n******************** the fai_k *********************\n"); 
 for(i=0;i<n1;i++)
	{
     s=function_s(a_xk,i);
	 vi=a_v[i]/(2*a_miu);
	 printf("s=%f vi=%f (in the fai_k)\n",s,vi);
	 m=min(s,vi);
	 sum1=sum1+pow(m,2);
	 printf("the sum1=%f pow(%f,2)=%f\n",sum1,m,pow(m,2));
	}

   for(i=0;i<n2;i++)
	{
	 h=function_h(a_xk,i);
	 printf("the h=%f (in fai_k)\n",h);
	 sum=sum+pow(h,2);
	 printf("sum=%f pow(%f,2)=%f\n",sum,h,pow(h,2));
	}
      
      sum=sum+sum1;
	  result=sqrt(sum);
	  printf("sum=%f result=%f\n",sum,result);
	 // printf("\n********************  the fai_k end!!!!  *********************\n");
	  //getch();
	return (result);
}

double fanshu(double c[],int n)
{
 int i;
 double result,sum=0;
 /*printf("\n*************            The fanshu            ************\n");*/
 //getch();
 for(i=0;i<n;i++)
 {
     sum=sum+pow(c[i],2);
  }
 // printf("\nfanshu c[%d]'s sum=%f\n",i,sum);
 result=sqrt(sum);
 //printf("fanshu=%f\n",result);
 //printf("\n*************         The fanshu end          ************\n",result);*/
 return (result);
}

void keeplastp(double a_xk[],double a_xk_last[],double a_gk[],double a_gk_last[],double a_pk[],double a_pk_last[],int n)
{
 int i;
  //printf("*************          The keeplastp        ************\n");
  for(i=0;i<n;i++)
  {
   a_xk_last[i]=a_xk[i];
   a_gk_last[i]=a_gk[i];
   a_pk_last[i]=a_pk[i];
  }
}

void change_xk(double t,double a_xk[],double a_pk[],int n)
 {
  int i;
  /*printf("\n************           The change_xk      *************\n");*/
  for(i=0;i<n;i++)
    a_xk[i]=a_xk[i]+t*a_pk[i];
    
 }

void changeback(double t,double a_xk[],double a_pk[],int n,double a_xk_last[])
 {
   int i;
   /*printf("\n*************         The changeback     ************\n");*/
  for(i=0;i<n;i++)
   a_xk[i]=a_xk_last[i];
   
 }

void interzone(double t0,double h,double *a,double *b,double a_xk[],double a_pk[],int n,double a_v[],double a_lumda[],double a_miu,int n1,int n2,double a_xk_last[])  /*搜索區(qū)間*/
{
 int m=0;
 double fai0,fai1,fai2,t1,t2;
  printf("\n************        The interzone     *************\nt0=%f h0=%f\n",t0,h);
   change_xk(t0,a_xk,a_pk,n);   
 fai0=function(a_xk,control_df,n,a_v,a_lumda,a_miu,n1,n2);
   changeback(t0,a_xk,a_pk,n,a_xk_last);
 t2=t0+h;
   change_xk(t2,a_xk,a_pk,n);
 fai2=function(a_xk,control_df,n,a_v,a_lumda,a_miu,n1,n2);
   changeback(t2,a_xk,a_pk,n,a_xk_last);
  printf("fai0=%f fai2=%f \nt0=%f t2=%f h=%f\n",fai0,fai2,t0,t2,h);
  //getch();
     if(fai2>fai0)
      {
      // printf("fai2=%f>=fai0=%f",fai2,fai0);
       t1=t2;
       fai1=fai2;
       h=-h;
       t2=t0+h;
       change_xk(t2,a_xk,a_pk,n);
       fai2=function(a_xk,control_df,n,a_v,a_lumda,a_miu,n1,n2);
       changeback(t2,a_xk,a_pk,n,a_xk_last);
      }

       while(fai2<=fai0)
        {
		 ++m;
         t1=t0;
         fai1=fai0;
         t0=t2;
         fai0=fai2;
         h=2*h;
         t2=t0+h;
         change_xk(t2,a_xk,a_pk,n);
         fai2=function(a_xk,control_df,n,a_v,a_lumda,a_miu,n1,n2);
         changeback(t2,a_xk,a_pk,n,a_xk_last);
         printf("t0=%.4f t1=%.4f t2=%.4f h=%.4f f0=%.4f f1=%.4f f2=%.4f time=%d\n",t0,t1,t2,h,fai0,fai1,fai2,m );

        }
        *a=min(t1,t2);
        *b=max(t1,t2);
        printf("la=%f   and    lb=%f\n************      The interzone end        *************\n",*a,*b);
        //getch();

}


double ls0618(double a_xk[],double a_pk[],int n,double a_v[],double a_lumda[],double a_miu,int n1,int n2,double a_xk_last[])
{
  double t0=0.000001;
  double h=0.0001;
  int time=0;
  double fai1,fai2,result;
  double t1,t2,t3=0,a,b,t;
  printf("*************The ls0618************\n");
  interzone(t0,h,&la,&lb,a_xk,a_pk,n,a_v,a_lumda,a_miu,n1,n2,a_xk_last);
  a=la;
  b=lb;
  printf("a=%f  and b=%f  \n",a,b);
  t2=a+beta*(b-a);
  t1=a+b-t2;
  t3=t2-t1;
  
  printf("t1=%f t2=%f t3=%f\n",t1,t2,t3);
  
  change_xk(t2,a_xk,a_pk,n);
  fai2=function(a_xk,control_df,n,a_v,a_lumda,a_miu,n1,n2);
  changeback(t2,a_xk,a_pk,n,a_xk_last);

  change_xk(t1,a_xk,a_pk,n);
  fai1=function(a_xk,control_df,n,a_v,a_lumda,a_miu,n1,n2);
  changeback(t1,a_xk,a_pk,n,a_xk_last);
  
  printf("fai1=%f fai2=%f\n",fai1,fai2);
                 //getch();
  while(fabs(t3)>0.01)    /*remember the conclusion*/
  {    ++time;
    if(fai1<=fai2)

     {
      b=t2;
      t2=t1;
      fai2=fai1;
      t1=a+b-t2;
      change_xk(t1,a_xk,a_pk,n);
      fai1=function(a_xk,control_df,n,a_v,a_lumda,a_miu,n1,n2);
      changeback(t1,a_xk,a_pk,n,a_xk_last);

     }
     else
     {
      a=t1;
      t1=t2;
      fai1=fai2;
      t2=a+beta*(b-a);
      change_xk(t2,a_xk,a_pk,n);
      fai2=function(a_xk,control_df,n,a_v,a_lumda,a_miu,n1,n2);
      changeback(t2,a_xk,a_pk,n,a_xk_last);
     }
   t3=t2-t1;
   printf("t1=%.4f t2=%.4f t3=%.4f a=%.4f b=%.4f time=%d\n",t1,t2,t3,a,b,time);

  }
                           //getch();
  //if(time==100){printf("the time is the max and search is fail\n");result=time;}
  //else {
      t=(t1+t2)/2.0;
       change_xk(t,a_xk,a_pk,n);
      // result=function(a_xk,control_df,n,a_v,a_lumda,a_miu,n1,n2);
       //changeback(t,a_xk,a_pk,n,a_xk_last);
       result=t;//}
  printf("\nt=%f\n\n*************         The ls0618 end        ************\n",result);
                          // getch();
  return (result);
}



double lsno_accurate(double a_xk[],double a_gk[],double a_pk[],int n,double a_v[],double a_lumda[],double a_miu,int n1,int n2,double a_xk_last[])
{
 double rou=0.1,xigema=0.4,beta1=2.0,a=0,b=20000;
 double fait=0,tk,g1=0,g2=0,f1,f2,t=0.00001;
 int i,m=0;
  printf("************    The lsno_accurate   *************\n");
                         
                         //getch();

                         for(i=0;i<n;i++)
			  {printf("xk%d=%f gk%d=%f pk%d=%f \n",i,a_xk[i],i,a_gk[i],i,a_pk[i]);}

  f1=function(a_xk,control_df,n,a_v,a_lumda,a_miu,n1,n2);
                         printf("f1=%f\n",f1);
  g1=0;						 //getch();
  for(i=0;i<n;i++)
     g1=g1+a_gk[i]*a_pk[i];
     
                        printf("g1=%f\n",g1);
   
  do
    {		
		
		for(i=0;i<n;i++)
          a_xk[i]=a_xk[i]+t*a_pk[i];
		           for(i=0;i<n;i++)
					   printf("xk%d=%f ",i,a_xk[i]);
				       printf("\n");
					   //getch();
       
	     f2=function(a_xk,control_df,n,a_v,a_lumda,a_miu,n1,n2);
	               printf("f2=%f\n\n",f2);

       for(i=0;i<n;i++)
        a_gk[i]=d_fun(a_xk,i,n,a_v,a_lumda,a_miu,n1,n2);
            
	          for(i=0;i<n;i++)
				  printf("gk%d=%f ",i,a_gk[i]);
			      //getch();
	   changeback(t,a_xk,a_pk,n,a_xk_last);     /*將改變xk點(diǎn)改回*/ 
	   
	   
	   g2=0;
       for(i=0;i<n;i++)
        g2=g2+a_gk[i]*a_pk[i];
      
	   
	   if(g2<(xigema*g1))
        {
         a=t;
         t=min((a+b)/2.0,2*a);
        }
       else if((f1-f2)<(-rou*t*g1))
				{
                 b=t;
                 t=(a+b)/2.0;
				}
             else
              {
               tk=t;
               fait=1;
              }
    g1=g2;f1=f2;  
     printf("times_m=%d\n",++m);
	}while(fait!=1);
	      for(i=0;i<n;i++)
			  printf("xk%d=%f gk%d=%f\n",i,a_xk[i],i,a_gk[i]);
	printf("\nthe tk=%f\nthe times(lsno_accurate) is %d\n************    The lsno_accurate end!!   *************\n",tk,m);
	              //getch();
    return(tk);

}


int Him(double a_xk[],double a_xk_last[],double a_gk[],double a_gk_last[],int n,double a_v[],double a_lumda[],double a_miu,int n1,int n2)
 {
  int i,neap=0;
  double c[N],look1,look2,look3,look4,look5,t1,t2,lok4,lok5,t;

   //printf("\n*************The Him************\n");
    for(i=0;i<n;i++)
      printf("xk%d=%f xk_%d=%f,gk%d=%f gk%d=%f\n",i,a_xk[i],i,a_xk_last[i],i,a_gk[i],i,a_gk_last[i]);
      
   for(i=0;i<n;i++)
    {
     a_gk[i]=d_fun(a_xk,i,n,a_v,a_lumda,a_miu,n1,n2);
     c[i]=a_xk[i]-a_xk_last[i];
     printf("c%d=%f xk%d=%f xk_%d=%f\n",i,c[i],i,a_xk[i],i,a_xk_last[i]);
    }
    look1=fanshu(a_gk,n);
                printf("look1=%f\n",look1);
    look2=fanshu(c,n);
                 printf("look2=%f\n",look2);
    look3=fanshu(a_xk_last,n)+1;
		printf("look3=%f\n",look3);
    t1=function(a_xk,control_df,n,a_v,a_lumda,a_miu,n1,n2);
    t2=function(a_xk_last,control_df,n,a_v,a_lumda,a_miu,n1,n2);
    t=t1-t2;
                printf("t=%f\n",t);
    lok4=fabs(t);
                 printf("lok4=%f\n",lok4);
    t1=function(a_xk_last,control_df,n,a_v,a_lumda,a_miu,n1,n2);
    lok5=fabs(t1)+1;
                printf("look5=%f\n",lok5);
    look4=fabs(function(a_xk,control_df,n,a_v,a_lumda,a_miu,n1,n2)-function(a_xk_last,control_df,n,a_v,a_lumda,a_miu,n1,n2));
    look5=fabs(function(a_xk_last,control_df,n,a_v,a_lumda,a_miu,n1,n2))+1;
    printf("\nl1=%f l2=%f l3=%f l4=%f l5=%f",look1,look2,look3,look4,look5); 
    //printf("\nlo1=%f lo2=%f lo3=%f lo4=%f lo5=%f",fanshu(a_gk,n),fanshu(c,n),fanshu(a_xk,n)+1,fabs(function(a_xk,control_df,n,a_v,a_lumda,a_miu,n1,n2)-function(a_xk_last,control_df,n,a_v,a_lumda,a_miu,n1,n2)),fabs(function(a_xk_last,control_df,n,a_v,a_lumda,a_miu,n1,n2))+1);
    //printf("\nlo1=%f lo2=%f lo3=%f",fanshu(a_gk,n),fanshu(c,n)/(fanshu(a_xk,n)+1),fabs(function(a_xk,control_df,n,a_v,a_lumda,a_miu,n1,n2)-function(a_xk_last,control_df,n,a_v,a_lumda,a_miu,n1,n2))/(fabs(function(a_xk_last,control_df,n,a_v,a_lumda,a_miu,n1,n2))+1)); 
    printf("\nlook1=%f look2/look3=%f look4/look5=%f\n",look1,look2/look3,look4/look5);
	if((look1<0.001)&&((look2/look3)<0.00001)&&((look4/look5)<0.00001))
	//{
		neap=1;
	 //getch();}
      printf("\nneap=%d\n",neap);
	     for(i=0;i<n;i++)
			 printf("xk%d=%f xk_%d=%f gk%d=%f gk_%d=%f\n",i,a_xk[i],i,a_xk_last[i],i,a_gk[i],i,a_gk_last[i]);
	  //printf("\n*************  The Him end!!!  ************\n");

     return (neap);

 }

double FR(double a_xk[],double a_xk_last[],double a_gk[],double a_gk_last[],double a_pk[],double a_pk_last[],int n,double a_v[],double a_lumda[],double a_miu,int n1,int n2)
{
  int k=0,m=15,i,result,M=0,time_k=0;
  double t1,t2,sum1,result1,alpha;
  double t;
  printf("\n************The FR*************\n");
      while(++M)
         {
                //#ifdef ls0
                t=ls0618(a_xk,a_pk,n,a_v,a_lumda,a_miu,n1,n2,a_xk_last);
                //printf("the ls0618's t=%f(FR)\n",t);