人教版六年级上册语文主题学习《回顾·拓展四》课件模板

5.优化设计5.3

一维搜索的优化方法西南科技大学网络教育系列课程5.优化设计5.3一维搜索的优化方法西南科技大学网15.3.1确定搜索区间的方法—进退法实际问题数学模型数值计算方法程序设计上机计算求出结果

数值解法：利用计算机通过反复迭代计算，求得实际问题的近似值。5.3.1确定搜索区间的方法—进退法实际问题数学模型数值25.3.1确定搜索区间的方法—进退法

下降迭代算法中在搜索方向S(k)上寻求最优步长ak时通常采用一维搜索法。

一维搜索法就是一元函数极小化的数值迭代算法，其求解过程称一维搜索。一维搜索问题指目标函数为单变量的非线性规划问题。又称线性搜索问题。其模型为：t为实数或一般一维搜索问题有效一维搜索问题5.3.1确定搜索区间的方法—进退法35.3.1确定搜索区间的方法—进退法

一维搜索问题的算法分类：

1）精确一维搜索（最优一维搜索）

2）非精确一维搜索（可接受一维搜索）1、进退法确定搜索区间的方法在函数的任一单谷区间上必存在一个极小点，而且在极小点的左侧，函数呈下降趋势，在极小点的右侧函数呈上升趋势。若已知方向S(k)上的三点x1＜x2＜x3及其函数值f(x1)、f(x2)和f(x3)，便可通过比较三个函数值的大小估计出极小点所在的位置，如图5.11所示。5.3.1确定搜索区间的方法—进退法一维搜索问题45.3.1确定搜索区间的方法—进退法图5.11极小点的估计5.3.1确定搜索区间的方法—进退法图5.11极小点的55.3.1确定搜索区间的方法—进退法2、进退法的定义在某一方向上按一定方式逐次产生一些探测点，并比较这些探测点上函数值的大小，就可以找出函数值呈“大-小-大”变化的三个相邻点，其中两端点所确定的闭区间必定包含着极小点，这样的区间称为初始区间，记作[a,b]。这种寻找初始区间的方法称为进退法。

α

x*

x1x2

b5.3.1确定搜索区间的方法—进退法2、进退法的定义6若对任意x1,x2,α≤x1<x2

≤b满足：

1)若x1

≤x*，则φ(x1)>φ(x*);

2)若x2

≥x*，则φ(x*)<φ(x2).则称φ(x)在[α,b]

上强单峰。若只有当x1≠x*，x2≠x*时，上述1),2)式才成立，则称φ(x)在[α,b]

上单峰。

αx1x*x2

b

强单峰

α

x*b

单峰若对任意x1,x2,α≤x1<x27其具体的程序见右图：其具体的程序见右图：85.3.1确定搜索区间的方法—进退法

一维搜索法：就是一元函数极小化的数值迭代算法，其求解过程称一维搜索。一维搜索法是构成非线性优化方法的基本算法，因为多元函数的迭代解法可归结为在一系列逐步产生的下降方向上的一维搜索。一维搜索法一般分两步：1）确定初始搜索区间，该区间应是包括一维函数极小点在内的单峰区间；2）在搜索区间内寻找极小点。5.3.1确定搜索区间的方法—进退法一维91、定义

黄金分割法：又称0.618法，是一种通过不断缩小区间得到极小点的一维搜索算法。问题：凸函数是不是单谷函数？严格凸函数是不是单谷函数？单谷函数是不是凸函数？单谷函数5.3.2

黄金分割法1、定义问题：凸函数是不是单谷函数？严格凸函数是不是单谷函10搜索法求解：或2、基本过程：

给出[a,b],使得x*在[a,b]中。[a,b]称为搜索区间。

迭代缩短[a,b]的长度。

当[a,b]的长度小于某个预设的值，或者导数的绝对值小于某个预设的正数，则迭代终止。搜索法求解：或2、基本过程：11假定：已经确定了单谷区间[a,b]x1x2ababx1x2新搜索区间为[a,x2]新搜索区间为[x1,b]假定：已经确定了单谷区间[a,b]x1x2ababx1x2新12区间缩小比例的确定：区间缩短比例为(x2-a)/(b-a)缩短比例为(b-x1)/(b-a)缩短比例满足：

每次插入搜索点使得两个区间[a,x2]和[x1,b]相等；

每次迭代都以相等的比例缩小区间。0.618法x1x2ababx1x2区间缩小比例的确定：区间缩短比例为(x2-a)/(b-a)缩13确定[a,b],计算探索点x1=a+0.382(b-a)x2=a+0.618(b-a)0.618法解题步骤：是否是停止，输出x1否以[a,x2]为新的搜索区间是停止，输出x2否以[x1,b]为新的搜索区间确定[a,b],计算探索点0.618法解题步骤：是否是停止，145.3.2黄金分割法例1：用黄金分割法求的初始区间，设初始点，初始步长。解：用进退法确定初始区间：

比较，因作前进运算：5.3.2黄金分割法例1：用黄金分割法求155.3.2黄金分割法因，再作前进运算：故初始搜索区间为：5.3.2黄金分割法16例2：解：x1x230x1)、第一轮：x1=1.146,x2=1.854x2-0>0.5例2：解：x1x230x1)、第一轮：x2-0>0.5171.4160xx2x12)、第二轮：x2=1.146,x1=0.708x2-0=1.146>0.53)、第三轮：x1=0.438,x2=0.708b-x1=1.146-0.438>0.51.8540xx2x11.4160xx2x12)、第二轮：x2-0=1.146>0184)、第四轮：x2=0.876,x1=0.708b-x1=1.146-0.708<0.5输出：x*=x2=0.876为最优解，最优值为-0.079801.416xx1x24)、第四轮：b-x1=1.146-0.708<0.5输出：195.3.3

Newton法Newton法基本思想：用探索点xk处的二阶Taylor展开式近似代替目标函数，以展开式的最小点为新的探索点。5.3.3Newton法Newton法基本思想：用探索点20解题步骤：给定初始点x1和精度是是停止，输出x1是否停止，解题失败否停止，输出x2否解题步骤：给定初始点x1和精度是是停止，输出x1是否停止，解21

5.3.4

二次插值法5.3.4二次插值法22

1、定义：

二次插值法又称抛物线法，它是以目标函数的二次插值函数的极小点作为新的中间插入点，进行区间缩小的一维搜索算法。

用f(x)在2或3个点的函数值或导数值，构造2次或3次多项式作为f(x)的近似值，以这多项式的极小点为新的迭代点。

3点2次，2点2次，4点3次，3点3次，2点3次等以3点2次为例：取x1，x

2，x3，求出f(x1)，f(x2)，f(x3)

5.3.4

二次插值法1、定义：5.3.4二次插值法235.3.4二次插值法设二次插值多项式：f(x)

=a0+a1x+a2x2f(x1)=

a0+a1x1+a2x12f(x2

)=a0+a1x2+a2x22

f(x3)

=

a0

+a1x3+a2x32解得a1a25.3.4二次插值法设二次插值多项式：f(x)245.3.4二次插值法5.3.4二次插值法255.3.4二次插值法f2<fp的新搜索区间f2>fp的新搜索区间5.3.4二次插值法f2<fp的新搜索区间f2>fp的新搜265.3.4二次插值法2、特点：1）二次插值法的中间插入点包含了函数在三个点上的函数值信息，因此这样的插入点比较接近函数的极小值。2）二次插值法以两个中间插入点的距离充分小作为收敛准则，即当成立时，把

作为此次一维搜索的极小点。二次插值法的计算程序如下图:5.3.4二次插值法2、特点：27人教版六年级上册语文主题学习《回顾·拓展四》课件模板285.3.4二次插值法

例2.用二次插值法求函数的极小点，给定解：1）确定初始区间：由于，应加大步长继续向前探测，

由于，可知初始区间已经找到，即5.3.4二次插值法例2.用二次插值法求函数295.3.4二次插值法2）用二次插值法逼近极小点记此初始区间内的相邻三点及其函数值依次为：将它们代入式，得插值函数的极小点，即新的插入点及其函数值：

由于，故新区间5.3.4二次插值法2）用二次插值法逼近极小点305.3.4二次插值法由于，故应继续作第二次插值计算。在新的区间内，相邻三点及其函数值依次为：将它们代入式，得由于，新区间5.3.4二次插值法由于，315.3.4二次插值法由于，故一维搜索到此结束，极小点和极小值为：5.3.4二次插值法由于，325.优化设计5.4

多维优化方法西南科技大学网络教育系列课程5.优化设计5.4多维优化方法西南科技大学网络教335.4

多维优化方法多维优化方法是进行多变量优化设计的数值迭代法。它包括了无约束优化方法和约束优化方法两种。1、无约束优化问题的一般形式：求解设计变量：X=[x1,x2,…,xn]T,X∈Rn满足目标函数minf(X)的无约束最优化解X*和最优化函数minf(X

*)。2、无约束优化的分类根据搜索方向的不同构成形式，可分类以下两类：5.4多维优化方法多维优化方法是进行多345.4

多维优化方法1）导数法：利用目标函数的一阶和二阶导数信息构成搜索方向的算法，称为导数法，如梯度法和共轭梯度法。

注：其收敛性和收敛速度都是比较好的。

2）模式法：通过几个已知点上函数值的比较构造搜索方向的算法。如鲍威尔法。对于较复杂的目标函数优化是有利的。3、约束优化方法

minf(X)s.t.gu(X)≤0(u=1,2,…,m)

hv(X)=0(v=1,2,…,p<n)5.4多维优化方法1）导数法：利用目标函355.4

多维优化方法根据处理条件的不同，约束优化方法分为直接法和间接法两类。直接法是指在迭代过程中逐点考察约束，并使迭代点始终局限于可行域之内的算法。如可行方向法和复合法。间接法是指把约束条件引入目标函，将约束优化问题转化为无约束问题求解的算法。如惩罚函数法。5.4多维优化方法根据处理条件的不同，约365.4.1梯度法1定义什么方向是函数下降最快的方向呢？答案是负梯度方向。

梯度法又称最速下降法，是无约束优化方法中间接法的一种。其基本原理：是将一个多维无约束优化问题转化为一系列沿目标函数负梯度方向进行一维搜索寻优的一种方法，即是在每一迭代点，选取搜索方向为负梯度方向：

5.4.1梯度法1定义375.4.1梯度法再沿进行一维搜索，以确定步长因子，找到新的设计点按照上述迭代公式进行若干次一维搜索，每次迭代的初始点取上次迭代的终点，即可使迭代点逐渐逼近目标函数的极小点。5.4.1梯度法再沿进行一维38梯度法程序框图梯度法程序框图395.4.1梯度法2梯度法的特点

1）梯度法理论明确，程序简单，计算量和存储量较少，对初始点的要求不严格。2）负梯度方向不是理想的搜索方向，梯度法也不是一种理想的方法，梯度法的收敛速度并不快。这是因为最速下降方向仅仅是指某点的一个局部性质，一旦离开这点，就不能保证仍是最速下降方向了。

3）梯度法的迭代全过程的搜索路线呈锯齿状。由于梯度法的相邻两次搜索方向的正交性决定的，如图5.14所示，故前几次迭代函数值下降较快，但以后的迭代下降越来越慢。5.4.1梯度法2梯度法的特点405.4.1梯度法图5.14二维目标函数的梯度法搜索过程5.4.1梯度法图5.14二维目标函数的梯度法搜索过程415.4.1梯度法所以，梯度法常与其它方法联合使用，即在迭代的第一步或前几步使用，当接近极小点时，改为用其它算法，以此加快收敛速度。特点：全局收敛，线性收敛，易产生扭摆现象而造成早停。5.4.1梯度法所以，梯度法常与其它方法联425.4.1梯度法例1用梯度法求下列无约束优化问题，已知函数X(0)=[1

1]T，ε＝0.1。min

解：1）第一次迭代求

令则

5.4.1梯度法例1用梯度法求下列无约束优化问题，已知函435.4.1梯度法对这种简单的一元函数，可以直接用解析法对求极小。令解得因还应继续迭代计算。5.4.1梯度法445.4.1梯度法

2)第二次迭代因

解得5.4.1梯度法2)第二次迭代455.4.1梯度法因可知X(2)不是极小点，还应继续进行迭代。最后得此问题的最优解为：

5.4.1梯度法因465.4.2共轭梯度法共轭方向的概念：设H为一正定对称矩阵，若有一组非零向量S1,S2,…,Sn满足则称这组向量关于矩阵H共轭。以正定二元二次函数为例。5.4.2共轭梯度法共轭方向的概念：475.4.2共轭梯度法任选初始点X(0)并沿某一下降方向S(0)作一维搜索，得由于梯度的迭代过程中，相邻的搜索方向相互垂直。可知

对函数f(X)求点X(1)的梯度从点X(1)开始沿另一下降方向S(1)作一维搜索，得5.4.2共轭梯度法任选初始点X(0)并485.4.2共轭梯度法

欲使X(2)成为极小点，则必有将式代入得

展开得化简为左乘[S(0)]T，且得5.4.2共轭梯度法欲使X(2)成为极小点，则495.4.2共轭梯度法这就是说，若要使第二个迭代点X(2)成为该正定二元二次函数的极小点，只要使两次一维搜索的搜索方向S(0)和S(1)关于函数的二阶导数矩阵H为共轭就可以了。换句话说，如果能够找到以H为共轭的两个向量，则无论从哪个初始点出发，依次沿这两个共轭方向作一维搜索，经两次迭代即可达到此正定二元二次函数的极小点。5.4.2共轭梯度法这就是说，若要使505.4.2共轭梯度法对于一般函数，共轭方向具有以下性质：（1）若是以H共轭的n个向量，则对于正定二次函数从任意初始点出发，依次沿这n个方向进行一维搜索，最多n次即可达到极小点。（2）从任意两个点和出发，分别沿同一方向进行一维搜索，得到两个一维极小