论文部分内容阅读
一、引言
黄金分割法的基本思想是:通过取试探点和进行函数值的比较,使包含极小点的搜索区间不断缩短,当区间长度缩短到一定程度时,区间上各点的函数值均接近极小值,从而各点可以看作为极小点的近似;也即是,依照"去坏留好"原则,对称原则,以及等比收缩原则来逐步缩小搜索范围。
当函数是凸函数时,我们可以利用函数的凸性,得到函数值的上界和下界,进而利用这些信息,缩短函数不确定区间,达到优化算法的效果。
二、改进的黄金分割法
很多人认为黄金分割法是搜索速度最快的方法,从程序编写角度来说,黄金分割法每次只需要插入一个点,每次只需要计算一次函数值,易于理解。就对区间缩短率来讲,黄金分割法的缩短率是0.618,舍弃的区间是0.382。
但是,如果一个函数是凸函数,根据已知的函数值,可以找到它的最大值和最小值,这些信息有利于得到最优解的位置,进而大大缩减不确定区间。
假设是定义在区间上的连续的,单变量可微的凸函数,给点初始不确定区间[]。下面介绍两种利用函数的凸性优化黄金分割的方法。
通过凸函数的一阶特征,定理1.3.11[4]:设为非空开凸集, 是定义在上的可微函数,则为凸函数的充分必要条件是:
(1)
证明:必要性
设是凸函数,于是对所有, ,有
因此,对于,
令,得
充分性
假设(1)成立,任取,。令,我们有,
于是得到:
所以是凸函数。
这个定理表明了根据局部导数的线性近似是函数的低估,即凸函数图形位于图形上任一点切线的上方。根据这个定理,所以函数的最小值一定在切线的上方。利用凸函数的一阶特征以及已知的最小函数值就可以确定不确定区间。函数两个端点处的切线和最小函数值的交点,即为缩小的不确定区间。
该算法的基本思想是:已知函数在区间端点两点的函数值,并比较两点函数值的大小,如果,最小值点为。否则,就取,并给该点的函数赋值;下一步求出函数在两点处的切线函数;最小函数与两切线的交点,即是新的迭代区间[]。由定理1.3.11,我们知道函数值一定在切线的上方,所以最小值也在新的迭代区间内。
算法2.1:
Step 0: 给定>0,点
Step1: 函数在两点处赋值;
Step2: 比较两点函数值的大小,如果 ,,否则:,并给点赋值;
Step3: 计算出 在点的切线方程 ;
Step4: 函数与直线的交点,即是新的迭代区间[]
Step5: 循环,直到满足精度要求
三、数值检验及结果分析
对于黄金分割法和算法2.1这两种算法,使用Mathematic5.2 进行数值试验,选用第二类检验函数:,其中;;;0.05,0.25
数值结果见表1,其中表示最优解,迭代步数和最优值。表中列出黄金分割法与算法2.1的结果,所有算法均使用如下终止条件:^(-4) ,迭代区间为[-10,10]。
评价一种算法的好坏当然不仅仅只看运算速度,如果其结果所取得精度不能达到预定的要求也是不合要求的。从表中可以看出,算法2.1对于第二类函数可以达到满意的精度要求,并且迭代的步数更少。
四、总结
本文通过缩短不确定区间的方法,对黄金分割法进行了尝试性的修改,对于简单的一维问题可能看不出修改后的差别,但是在实际应用中的多维问题的求解时,往往都会用到一维搜索方法,如果能够针对具体的问题采用合理的方法,则对于问题的求解应该可以节省很多计算时间。
参考文献:
[1]EDGAR DEN BOEF and DICK DEN HERTOG.Efficient line search methods for convex functions,SIAM J. OPTIM., Vol.18, No.1, pp. 338-363.
[2]M. Bendaya, Line search techniques for the logarithmic barrier function in quadraticprogramming, J. Oper. Res.Soc,46(1995),pp.332-338.
[3]陳宝林.最优化理论与算法[M].北京:清华大学出版社,1989.
[4]袁亚湘,孙文瑜.最优化理论与方法[M].北京:科学出版社,32-39.
黄金分割法的基本思想是:通过取试探点和进行函数值的比较,使包含极小点的搜索区间不断缩短,当区间长度缩短到一定程度时,区间上各点的函数值均接近极小值,从而各点可以看作为极小点的近似;也即是,依照"去坏留好"原则,对称原则,以及等比收缩原则来逐步缩小搜索范围。
当函数是凸函数时,我们可以利用函数的凸性,得到函数值的上界和下界,进而利用这些信息,缩短函数不确定区间,达到优化算法的效果。
二、改进的黄金分割法
很多人认为黄金分割法是搜索速度最快的方法,从程序编写角度来说,黄金分割法每次只需要插入一个点,每次只需要计算一次函数值,易于理解。就对区间缩短率来讲,黄金分割法的缩短率是0.618,舍弃的区间是0.382。
但是,如果一个函数是凸函数,根据已知的函数值,可以找到它的最大值和最小值,这些信息有利于得到最优解的位置,进而大大缩减不确定区间。
假设是定义在区间上的连续的,单变量可微的凸函数,给点初始不确定区间[]。下面介绍两种利用函数的凸性优化黄金分割的方法。
通过凸函数的一阶特征,定理1.3.11[4]:设为非空开凸集, 是定义在上的可微函数,则为凸函数的充分必要条件是:
(1)
证明:必要性
设是凸函数,于是对所有, ,有
因此,对于,
令,得
充分性
假设(1)成立,任取,。令,我们有,
于是得到:
所以是凸函数。
这个定理表明了根据局部导数的线性近似是函数的低估,即凸函数图形位于图形上任一点切线的上方。根据这个定理,所以函数的最小值一定在切线的上方。利用凸函数的一阶特征以及已知的最小函数值就可以确定不确定区间。函数两个端点处的切线和最小函数值的交点,即为缩小的不确定区间。
该算法的基本思想是:已知函数在区间端点两点的函数值,并比较两点函数值的大小,如果,最小值点为。否则,就取,并给该点的函数赋值;下一步求出函数在两点处的切线函数;最小函数与两切线的交点,即是新的迭代区间[]。由定理1.3.11,我们知道函数值一定在切线的上方,所以最小值也在新的迭代区间内。
算法2.1:
Step 0: 给定>0,点
Step1: 函数在两点处赋值;
Step2: 比较两点函数值的大小,如果 ,,否则:,并给点赋值;
Step3: 计算出 在点的切线方程 ;
Step4: 函数与直线的交点,即是新的迭代区间[]
Step5: 循环,直到满足精度要求
三、数值检验及结果分析
对于黄金分割法和算法2.1这两种算法,使用Mathematic5.2 进行数值试验,选用第二类检验函数:,其中;;;0.05,0.25
数值结果见表1,其中表示最优解,迭代步数和最优值。表中列出黄金分割法与算法2.1的结果,所有算法均使用如下终止条件:^(-4) ,迭代区间为[-10,10]。
评价一种算法的好坏当然不仅仅只看运算速度,如果其结果所取得精度不能达到预定的要求也是不合要求的。从表中可以看出,算法2.1对于第二类函数可以达到满意的精度要求,并且迭代的步数更少。
四、总结
本文通过缩短不确定区间的方法,对黄金分割法进行了尝试性的修改,对于简单的一维问题可能看不出修改后的差别,但是在实际应用中的多维问题的求解时,往往都会用到一维搜索方法,如果能够针对具体的问题采用合理的方法,则对于问题的求解应该可以节省很多计算时间。
参考文献:
[1]EDGAR DEN BOEF and DICK DEN HERTOG.Efficient line search methods for convex functions,SIAM J. OPTIM., Vol.18, No.1, pp. 338-363.
[2]M. Bendaya, Line search techniques for the logarithmic barrier function in quadraticprogramming, J. Oper. Res.Soc,46(1995),pp.332-338.
[3]陳宝林.最优化理论与算法[M].北京:清华大学出版社,1989.
[4]袁亚湘,孙文瑜.最优化理论与方法[M].北京:科学出版社,32-39.