文档介绍：§ 一维搜索方法
一维搜索问题:目标函数为单变量的非线性规划问题,即
()
对的取值为的()称为一维搜索问题,即;对的取值为的()称为有效一维搜索问题,即。
1、(近似黄金分割法)
单谷函数:称函数是区间上的单谷函数,若存在,使得在上严格递减,且在上严格递增。区间称为的单谷区间。
求解一维搜索问题的方法:先设法给出一个搜索区间,然后通过迭代不断缩小搜索区间,当区间的长度充分小是,可取这个区间中的任一点作为一个近似极小点。
考虑问题
()
其中是的单谷区间, 下面将通过迭代不断缩小搜索区间, 获得的唯一极小点的近似解。在内任取两点,设,由于是区间上的单谷函数,所以有
<1> 若,则;
<2> 若,则。
证<1>:若,则,所以,因为在上严格递减,所以,矛盾。同理可证<2>。
通过比较和的大小,可将搜索区间缩小为或。不妨设为,则在只需另找一个点,比较和的目标函数值,又可以进一步缩小搜索区间。这些点称为探索点。因此,除了第一次要计算两个探索点的函数值外,以后每次迭代只需计算一个探索点的函数值。
a t1 t2 b
近似黄金分割法:总是选搜索区间内的两个黄金分割点(左黄金分割点和右黄金分割点)作为探索点。
结论:设搜索区间的左黄金分割点为,右黄金分割点为,则是的右黄金分割点,是的左黄金分割点。即
若,则

第1步确定单谷区间[a,b],给定最后区间精度;
第2步计算最初两个探索点
,
并计算,;
第3步若,转第4步。否则转第5步;
第4步若,停止迭代,输出。否则令,,,,计算,转第3步;
第5步若,停止迭代,输出。否则令,,,,计算,转第3步。
例

其中,的单谷区间为
解:
0
1
2
3
4
0
0
0

3