linesearch.h

线性搜索方法。用梯度法求单峰极值。适合初学者参考

#define PRECI 0.00001   // [ 精度要求 ]
#define R 0.618         // [ 搜索区间长度的缩短率 ]

//double fun( double x );  // [ 目标函数的原型说明 ]

// [ 进退法确定搜索区间 ]
void FindSearchingArea( double(*pf)(double x), double firstpoint, double &a, double &b )
{
	int h = 1;   // [ 步长 ]
	int t = 2;   // [ 步长加倍系数 ]

	// [ 找目标函数下降方向 ]
	if( pf(firstpoint) < pf( firstpoint + h ) )   // [ 正方向不成功 ]
	{
		h = -1;   // [反方向搜索]
		if( pf(firstpoint) < pf( firstpoint + h ) )  // [ 初始点选择的不合适 ]
		{
			firstpoint += 1;   // [ 修改初始点 ]
		}
	}

	// [ 找目标函数的上升点 ]
	while( pf(firstpoint) > pf( firstpoint + h ) )
	{
		firstpoint += h;
		h *= t;
	}

	// [ 给出搜索区间的两端点 ]
	//a = min( (firstpoint-h),(firstpoint+h) );
	//b = max( (firstpoint-h),(firstpoint+h) );
	a = (firstpoint-h)<(firstpoint+h)?(firstpoint-h):(firstpoint+h);
	b = (firstpoint-h)>(firstpoint+h)?(firstpoint-h):(firstpoint+h);
}

// [ 黄金分割法求一维优化极小 ]
double  LineSearch( double(*pf)(double x),double firstpoint )
{
	double m,n;         // [ 两个试探点 ]
	double a,b;         // [ 搜索区间的两个端点 ]

	FindSearchingArea( pf,firstpoint,a,b );  // [ 确定搜索区间 ]
    
	// [ 计算试探点 ]
	n = a + (b-a)*R;
	//m = a + b - n;
	m = a + (b-a)*(1-R);
	while( (b-a) > PRECI )
	{
		if( pf(m)<pf(n))   // [ 应截断(n,b) ]
		{
			b = n;
			n = m;
			//m = b + a - n;
		    m = a + (b-a)*(1-R);
		}
		else             // [ 应截断(a,m)  ] 
		{
			a = m;
			m = n;
			n = a + (b-a)*R;
		}
	}
		
		
	// [ 做最后一次分割 ]
	if( pf(m)<=pf(n) )
	{
		b = n;
	}
	else
	{
		a = m;
	}
	return (a+b)/2;
}