优化设计2——一维优化及牛顿法.ppt

2018/2/19
1
一维优化问题
优化问题的数值解法:
X(k+1)=X (k)+λ(k) S(k)
F[X (k)+λ(k) S(k) ]=min F [X( k)+ λ(k) S(k) ]
从一个初始点X(0)出发,按一定规则确定一个搜索方向S(0),然后在S(0)上搜索到目标函数的极小值X(1);接着又以X(1),作为下一个迭代的出发点,重复以上过程,直到把目标函数达到最优值f(X*)为止。
在此过程中求λ(k)用到的方法叫一维搜索的优化方法。
2018/2/19
2
2018/2/19
3
单峰区间
1. 单峰区间
在单峰区间内,在极小点
左边,函数值随x的增加是严
格减小的;在极小点右边,
函数是严格增大的。因此在
单峰区间内,函数值具有
“高——低——高”的形态,
可利用这一特征来确定初始单峰区间。

一维搜索的各种方法的基本思想是“区间消去法”,而区间消去法的基本思想是:逐步缩小搜索的区间,直至最小点存在的范围小于给定的误差范围为止。
2018/2/19
4
基本思路:
对单峰函数f(x)任选一个初始点x1及初始步长h,通过比较这两点函数值的大小,来决定第三点的位置,比较这三点的函数值的大小,确定是否为“高——低——高”的形态,依此确定向前或后退搜索。
2018/2/19
5
确定单峰区间的进退算法
进退法:
通过比较函数值大小来确定单峰区间的方法。
给定的初始点和步长
单峰区间:
2018/2/19
6
进退步骤:
(1) 选定初始点x1、初始步长h(h>0)。
计算函数值f1=f(x1)和f2=f(x1+h)。比
较f1和f2,可分三种情况:
若f1>f2,则说明极小点x*必在x1的右方,应作前进运算,转(2);
若f1<f2,则说明x*必在x1的左方,应作后退运算,转(3);
若f1=f2,则说明极小点x*必在点x1和x1+h点之间,已形成“高—低—高”形态,则初始单峰区间为[x1,x1+h]。
(2) 当f1>f2,将步长加倍,取下一个计算点为x=x1+2h,计算f(x1+2h),并令f1= f(x1+h), f2= f(x1+2h)。再比较f1和f2:
若f1<f2,则相邻三点的函数值形成“高—低—高”形态,得到初始单峰区间[x1,x1+2h];
若f1>f2,则应再作前进计算,步长加倍,取下一计算点为x=x1+4h,并比较f1 = f(x1+2h)和f2 = f(x1+4h)的函数值。如此反复循环,直到相邻三点的函数值形成“高—低—高”形态为止;
若f1=f2,则初始单峰区间为[x1+h,x1+2h]
2018/2/19
7
(3) 当f1<f2,做后退运算。步长改为负值,
即从x1出发,向反方向搜索。取下一个计
算点为x=x1-h,计算f(x1-h),并令f2 =f(x1),
f1 = f(x1-h)。此时:
若f2<f1,则可确定初始单峰区间为[x1-h,x1+h]。
若f2>f1,将步长加倍,继续后退。再算出下一个点的函数值f(x1-2h),…。如此反复循环,直到相邻三点的函数值出现“高—低—高”形态为止;
若f2=f1,则初始单峰区间为[x1-h,x1]。
可自己画出进退法的程序框图。
2018/2/19
8
区间缩小的序列消去原理:
是通过对区间分割点函数值的计算和比较,将初始区间逐次进行缩小,当区间缩小到给定的精度要求时,可求得一维极小点的近似解。
若,则极小点必在区间
若,则极小点在
若,则归入上面任何一种情况。
区间消去法
a
b
2018/2/19
9
黄金分割法:
黄金分割:将一线段分成两段,使得整段长度与较长段的比值等于较长段与较短段的比值
解得
黄金分割法
2018/2/19
10
两个原则:
等比收缩原则:即区间每一次的缩短率λ不变;
对称取点原则:即所插入两点在区间中位置对称。