niudun.c

最优化课程中要用到的所有最优化算法

                //////////////////////////////
                //////   最优化      /////////
                //////信号与信息处理 /////////
                //////    刘君       /////////
                //////06020810021009//////////
                //////////////////////////////

//此程序使用牛顿法,割线法,抛物线法,用于计算目标函数在给定初点时的最小值//

//////////////////////////////////////////////////////
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
////////the area of calculation///////////////////////
#define   FUN   "3*pow(x,4) - 4*pow(x,3) - 12*pow(x,2)"
#define   N     3        //迭代次数
#define   H     0.1
#define   X0    -1.2

#define   X11   -1.2
#define   X12   -0.8

#define   X21   -1.2
#define   X22   -1.1
#define   X23   -0.8
////////////the declaration of functions//////////////
float fun( float x);

float get_derivatives_1n( float x );  //使用五点法求一阶导数
float get_derivatives_2n( float x );  //使用五点法求二阶导数

float get_min_niu( void );    //牛顿法
float get_min_ge( void );     //割线法
float get_min_pao( void );    //抛物线法

float (* get_min)( void );

float get_group_fun( float x[3] );   //get xk used in pao method
void  reorder( float xk, float x[3] );  //get new x1,x2,x3 in pao method
/////////////////////////////////////////////////////
int main( void )
{
	float xk;
	char  input;

	printf( "目标函数为 " );
	printf( FUN );
	printf( "\n" );

LOOP1:
	printf( "请输入函数逼近法种类:\n" );
	printf( "a:牛顿法 b:割线法 c:抛物线法 e:退出\n");

	scanf( "%c", &input );
	fflush( stdin );   //清除标准输入缓存里的回车,否则还会继续错误执行
	switch ( input )
	{
	case 'a':
		printf( "你选择了牛顿法\n" );
		printf( "迭代次数为：%d\n", N );
		printf( "初值为: x0=%f\n", X0 );
		get_min = get_min_niu;
		break;
	case 'b':
		printf( "你选择了割线法\n" );
		printf( "迭代次数为：%d\n", N );
		printf( "初值为: x1=%f, x2=%f\n", X11, X12 );
		get_min = get_min_ge;
		break;
	case 'c':
		printf( "你选择了抛物线法\n" );
		printf( "迭代次数为：%d\n", N );
		printf( "初值为: x1=%f, x2=%f, x3=%f\n", X21, X22, X23 );
		get_min = get_min_pao;
		break;
	case 'e':
		goto LOOP2;
	default: 
		printf( "你输入了无效命令!!\n" );
		printf( "请重新输入:\n" );
		goto LOOP1;
	}

	xk = get_min();

	printf( "\n经过 %d 次迭代，得到点xk为 %f\n", N, xk );

	goto LOOP1;

LOOP2:
	return 1;
	
}



////////the function of destionation////// 
float fun( float x)
{
	float result;
	result = 3*pow(x,4) - 4*pow(x,3) - 12*pow(x,2);
	return result;
}
////////get derivatives///////////////////
float get_derivatives_1n( float x )
{
	float z[5], y[5];
	float m;
	int   i;

	z[0] = x - 2*H;
	for( i = 1; i < 5; i ++ )
		z[i] = z[0] + i * H;
	for( i = 0; i < 5; i ++ )
		y[i] = fun( z[i] );

	m = ( y[0] - 8*y[1] + 8*y[3] - y[4] )  / (12*H);

	return m;
}
float get_derivatives_2n( float x )
{
	float z[5], y[5];
	float M;
	int   i;

	z[0] = x - 2*H;
	for( i = 1; i < 5; i ++ )
		z[i] = z[0] + i * H;
	for( i = 0; i < 5; i ++ )
		y[i] = fun( z[i] );

	M = ( - y[0] + 16*y[1] - 30*y[2] +16*y[3] - y[4] ) / (12*H*H);

	return M;
}
///////////////////////////////////////////
float get_group_fun( float x[3] )
{
	float B1, B2, B3, C1, C2, C3;
	float xk;
	float y0, y1, y2;

	y0 = fun( x[0] );
	y1 = fun( x[1] );
	y2 = fun( x[2] );

	B1 = ( pow( x[1], 2 ) - pow( x[2], 2 ) ) * y0;
	B2 = ( pow( x[2], 2 ) - pow( x[0], 2 ) ) * y1;
	B3 = ( pow( x[0], 2 ) - pow( x[1], 2 ) ) * y2;

	C1 = ( x[1] - x[2] ) * y0;
	C2 = ( x[2] - x[0] ) * y1;
	C3 = ( x[0] - x[1] ) * y2;

	xk = ( B1 + B2 + B3 ) / ( 2 * ( C1 + C2 +C3 ) );
	
	return xk;
}

void  reorder( float xk, float x[3] )
{
	float y[4];
	float y1, y2;

	y1 = fun( xk );
	y2 = fun( x[1] );

	if( xk >= x[1] )
	{
		if( y1 >= y2 )
		{
			x[2] = xk;
		}
		else
		{
			x[0] = x[1];
			x[1] = xk;
		}
			
	}
	else
	{		
		if( y1 > y2 )
		{
			x[0] = xk;
		}
		else
		{			
			x[2] = x[1];
			x[1] = xk;
		}
	}

}
////////get xk through three methods//////
float get_min_niu( void )    //牛顿法
{
	float xk;
	float y1, y2;
	int   k;

	xk = X0;

	for( k = 1; k <= 3; k ++ )
	{
		y1 = get_derivatives_1n( xk );
		y2 = get_derivatives_2n( xk );
		xk = xk - y1 / y2;
		printf( "第 %d 次迭代，得到xk 为 %f\n", k, xk );
	}

	return xk;
}

float get_min_ge( void )    //割线法
{
	float xk1, xk2, xk3;
	float y1, y2;
	int   k;

	
	xk1 = X11;
	xk2 = X12;

	for( k = 1; k <= 3; k ++ )
	{ 
		y1  = get_derivatives_1n( xk1 );
		y2  = get_derivatives_1n( xk2 );
		xk3 = xk2 - ( xk2 - xk1 ) / ( y2 - y1 ) * y2;
		printf( "第 %d 次迭代，得到xk 为 %f\n", k, xk3 );
		xk1  = xk2;
		xk2  = xk3;
	}

	return xk3;
}

float get_min_pao( void )   //抛物线法
{
	float x[3];
	float xk;
	int   k;

	x[0] = X21;
	x[1] = X22;
	x[2] = X23;

	for( k = 1; k <=3; k ++)
	{
		xk = get_group_fun( x );
		printf( "第 %d 次迭代，得到xk 为 %f\n", k, xk );

		reorder( xk, x );
	}

	return xk;
}