一维搜索法课件

§3－1概述一、问题的提出1、实际设计工作中会遇到一维优化设计问题在长为350cm、宽为260cm的长方形不锈钢板的四角，各剪去一个小正方形，做成一个无盖的储水箱，试确定正方形的边长，使储水箱的容积最大。§3－1概述一、问题的提出1、实际设计工作中会遇到一维12、多维优化设计转化为一维优化设计问题多维优化问题求解过程：2、多维优化设计转化为一维优化设计问题多维优化问题求解过程：2二、一维优化方法的分类1.解析法2.数值法由方程求根法区间收缩法二分法、切线法、割线法等分数（Fibonacci）法、黄金分割（0.618)法、插值法等得二、一维优化方法的分类1.解析法2.数值法由方程求根法区间收3§3－2单峰区间的确定定义设α*是(α)的极小点，若存在闭区间[a，b]，使得α*∈[a，b]，且使函数值呈“高—低—高”的形态，即函数(α)在闭区间[a，b]中有唯一极小点，则称[a，b]是(α)单峰区间.一、单峰区间的定义非单峰区间单峰区间§3－2单峰区间的确定定义设α*是(α)的极小点4二、单峰区间的确定确定搜索区间的一种简单的方法是进退法，其基本思想是从某一点出发，按一定的步长，确定函数值呈“高—低—高”的三点。如果一个方向不成功，就退回来，再沿相反的方向寻找。具体算法步骤如下：(4)如果k=1,则置μ2=μ,2=,和h=-h,转(2);否则置μ1=μ2,1=2,μ2=μ3,2=3,μ3=μ,3=,并令a=min{μ1,μ3},b=max{μ1,μ3},停止计算.(1)取初始步长h，置初始值μ3=0，3=(μ3)，并置k=0.(2)置μ=μ3+h，=(μ)和k=k+1.(3)如果<3,则置μ2=μ3,2=3,μ3=μ,3=和h=2h,k=k+1,转(2);二、单峰区间的确定确定搜索区间的一种简单的方法是进退法，其基5二、单峰区间的确定二、单峰区间的确定6开始输入：h置μ3=0，3=(μ3)，k=0置μ=μ3+h，=(μ),k=k+1μ2=μ3,2=3,μ3=μ,

3=,h=2h,k=k+1<3?k=1?μ2=μ,2=,h=-h,μ1=μ2,1=2,μ2=μ3,2=3,μ3=μ,3=,a=min{μ1,μ3},b=max{μ1,μ3}结束yesnoyesno三、算法框图开始输入：h置μ3=0，3=(μ3)，k=0置μ=μ37四、区间收缩原则与区间收缩率1>2?yesnoa=a1b=ba=ab=a2四、区间收缩原则与区间收缩率1>2?yesnoa=a1a8黄金分割法(Golden

Section

Method)又称为0.618法，是用于在单峰函数区间上求极小的一种方法。其基本思想是通过取试探点和进行函数值比较，使包含极小点的搜索区间不断减少，当区间长度缩短到一定程度时，就得到函数极小点的近似值。§3－3黄金分割法一、黄金分割法的取点原则1.对称取点2.等区间收缩率3.留点可用黄金分割法(GoldenSectionMethod)又称9二、黄金分割法的区间收缩率二、黄金分割法的区间收缩率10(1)置初始搜索区间[a,b]，并置精度要求ε，并计算左右试探点

al=a+0.382(b-a)a2=a+0.618(b-a)及相应的函数值l=(al)，2=(a2).三、黄金分割法的步骤(3)若|b-a|≤ε,做:如果l<2，则置*=a1；否则置*=a2，停止计算(*作为问题的解)。否则转(2).(2)如果l<2,则置b=a2，a2=a1，2＝1，并计算

al=a+0.382(b-a)，l=(al)

否则置a=a1，a1=a2，1＝2，并计算

a2=a+0.618(b-a)及相应的函数值，2=(a2).(1)置初始搜索区间[a,b]，并置精度要求ε，并计算左右试11四、黄金分割法的程序框图四、黄金分割法的程序框图12【例】用0.618法求解一维问题

min(α)=eα-5α，在区间[1,2]内的极小点，计算4步.

解

a=1，b=2，al=1.382，a2=1.618，

l=-2.927，2=-3.047,

所以l>2，去掉区间[1，al].详细计算结果见下表【例】用0.618法求解一维问题13

不要求每次迭代区间的收缩比不变,而希望在试验点个数相同的情况下，找出一种选取试验点的最佳策略，使得最终的极小区间的长度达到最小，换句话说，如果规定试验点的个数为n，且最终区间长度为1，问如何选取这n个点，使得原始区间的长度最大？令Ln表示试验点数为n、最终区间长度为1时，原始区间[a,b]的最大可能长度。设l为左试探点，r为右试探点，如果极小点*位于区间[a，l]，则在此区间内至多还可以有n-2个试验点，因此l-a≤Ln－2.§3－4Fibonacci法不要求每次迭代区间的收缩比不变,而希望在试验点个数相同的14另一方面,如果极小点*位于区间[l,b]内,则包括r在内,还可以作n-1个试验点，所以

b-l≤Ln-1.

因此b-a=(b-l)+(l-a)≤Ln－2+Ln-1,故有如下关系式:

Ln≤Ln－2+Ln-1显然,不计算函数值和仅计算一点处的函数值都不能使极小区间缩小，即L0=L1=1.由此可得，如果原始区间长度满足递推关系

F0=F1，Fn=Fn－2+Fn-1则Fn将是最大原始区间的长度.另一方面,如果极小点*位于区间[l,b]内,则包括r15Fn称为Fibonacci数。Fibonacci方法的基本思想与0.618法相同.在搜索区间[a,b]上,先取左、右试验点l

和r

比较函数值f(l)和f(r)重新确定搜索区间.(1)若f(l)<f(r)，去掉区间[r，b]，令a′=a，

b′=r，再计算新的试探点。Fn称为Fibonacci数。Fibonacci方法的基本思16(2)若f(l)>f(r)，去掉区间[a,r],令a′=l，b′=b,再计算新的试探点(2)若f(l)>f(r)，去掉区间[a,r],17所以Fibonacci方法与0.618法一样,除第一次外,以后每次只计算一个点处的函数值.Fibonacci方法每次保留的区间长度为Fk-1Fk,因此若计算n个试验点,最终的区间长度。因此,任给一精度要求ε,要求最终的区间长度小于ε,即有因此,任给一精度要求ε,要求最终的区间长度小于ε,即有那么选择n满足所以Fibonacci方法与0.618法一样,除第一次外,以18(1)置初始搜索区间[a，b]，并置精度要求ε，选取分离间隔δ<ε，求最小正整数n，使得Fn>（b-a）ε，并计算左右试探点l=a+Fn-2/

Fn(b-a)，r=a+Fn-1/

Fn(b-a)及相应的函数值fl＝f(l),fr＝f(r)。算法步骤(2)置n=n-1。(3)如果fr＝f(r)，则置b=r，r=l

，fr

＝fl

，。如果n>2,则计算l=a+Fn-2/

Fn(b-a)，fl＝f(l)；否则计算l=r-δ，fl＝f(l)。(4)fl≥fr

，置a=l

，l=r

，fl

＝fr

；如果n>2，则计算r=a+Fn-1/

Fn(b-a)，fr＝f(r)；否则计算r=l+δ，fr＝f(r)。(5)若n=1，做：如果fr＝f(r)，则置μ=r

；否则置μ=r

，停止计算(μ作为问题的极小点)。否则转(2)。(1)置初始搜索区间[a，b]，并置精度要求ε，选取分离间隔19

插值法是一类重要的一维搜索方法，其基本思想是利用搜索区间上某些点的信息构造插值多项式(通常不超过三次)p(α)，逐步用p(α)的极小点来逼近(α)的极小点α*。当(α)有比较好的解析性质时,插值法比区间收缩法(如0.618法)的效果好.本节介绍三种较为常见的插值法.§3－4二次插值法

在单峰区间[a,b]中，已知函数在三点μ1、μ2、μ3

（μ1<μ2<μ3)处的函数值为1、2、3，并满足1>2、3>2，即三点满足“两端高中间低”。这三个点可由得到：一、二次插值法的思想插值法是一类重要的一维搜索方法，其基本思想是利用搜索20由数值分析的知识,得到过三个点(μ1，1)、(μ2，2)、(μ3，3)的二次插值公式为对上式求导数，并求解方程p’(α)=0，得到p(α)的极小点由数值分析的知识,得到过三个点(μ1，1)、(μ2，221用μ作为α*的估计值,并计算μ处的函数值=(μ)。第一次的近似结果往往不够理想，需要作进一步的近似。现已得到四个点(μ1，1)、(μ2，2)、(μ3，3)和(μ，),如何选取三个点呢?

仍然按照最初的原则，选取满足“两端高中间低”的三个点。二、二次插值法的区间收缩过程用μ作为α*的估计值,并计算μ处的函数值=(μ)。二、二22(1)取初始点μ1<μ2<μ3，计算i=(μi)，i=1,2,3，并且满足

1>

2，

2<

3

，置精度要求ε.三、二次插值法算法步骤：(2)计算

A=2[1(μ2-μ3)+2(μ3-μ1)+3(μ1-μ2)]

若A=0，则置μ=μ2,=2,停止计算(输出μ,的信息).(3)计算

μ=[1(μ22-μ32)+2(μ32

–μ12)+3(μ12-μ22)]/A

若μ<μ1或μ>μ3，则置μ=μ2,=2，停止计算(输出μ,的信息)

。(1)取初始点μ1<μ2<μ3，计算i=(μi)，i=123(4)计算=(μ)。若|μ-μ2|<ε,则停止计算(μ作为极小点)。(5)如果μ∈(μ2,μ3)，则:

若<2，则置μ1=μ2，1=2

，μ2=μ，2=；

否则置μ3=μ,

3=;

否则(μ∈(μ1,μ2)):

若<2，则置μ3=μ2,3=2

，μ2=μ,2=；

否则置μ1=μ,2=，转(2).(4)计算=(μ)。若|μ-μ2|<ε,则停止计算(μ作24四、二次插值法程序框图：四、二次插值法程序框图：25一维搜索法课件26作业用黄金分割法编程求解函数的极小点X（1）。作业用黄金分割法编程求解函数的极小点X（1）。27优化方法程序实现之一用黄金分割法编程求解函数的极小点X（1）。优化方法程序实现之一用黄金分割法编程求解函数的极小点X（1）28§3－1概述一、问题的提出1、实际设计工作中会遇到一维优化设计问题在长为350cm、宽为260cm的长方形不锈钢板的四角，各剪去一个小正方形，做成一个无盖的储水箱，试确定正方形的边长，使储水箱的容积最大。§3－1概述一、问题的提出1、实际设计工作中会遇到一维292、多维优化设计转化为一维优化设计问题多维优化问题求解过程：2、多维优化设计转化为一维优化设计问题多维优化问题求解过程：30二、一维优化方法的分类1.解析法2.数值法由方程求根法区间收缩法二分法、切线法、割线法等分数（Fibonacci）法、黄金分割（0.618)法、插值法等得二、一维优化方法的分类1.解析法2.数值法由方程求根法区间收31§3－2单峰区间的确定定义设α*是(α)的极小点，若存在闭区间[a，b]，使得α*∈[a，b]，且使函数值呈“高—低—高”的形态，即函数(α)在闭区间[a，b]中有唯一极小点，则称[a，b]是(α)单峰区间.一、单峰区间的定义非单峰区间单峰区间§3－2单峰区间的确定定义设α*是(α)的极小点32二、单峰区间的确定确定搜索区间的一种简单的方法是进退法，其基本思想是从某一点出发，按一定的步长，确定函数值呈“高—低—高”的三点。如果一个方向不成功，就退回来，再沿相反的方向寻找。具体算法步骤如下：(4)如果k=1,则置μ2=μ,2=,和h=-h,转(2);否则置μ1=μ2,1=2,μ2=μ3,2=3,μ3=μ,3=,并令a=min{μ1,μ3},b=max{μ1,μ3},停止计算.(1)取初始步长h，置初始值μ3=0，3=(μ3)，并置k=0.(2)置μ=μ3+h，=(μ)和k=k+1.(3)如果<3,则置μ2=μ3,2=3,μ3=μ,3=和h=2h,k=k+1,转(2);二、单峰区间的确定确定搜索区间的一种简单的方法是进退法，其基33二、单峰区间的确定二、单峰区间的确定34开始输入：h置μ3=0，3=(μ3)，k=0置μ=μ3+h，=(μ),k=k+1μ2=μ3,2=3,μ3=μ,

3=,h=2h,k=k+1<3?k=1?μ2=μ,2=,h=-h,μ1=μ2,1=2,μ2=μ3,2=3,μ3=μ,3=,a=min{μ1,μ3},b=max{μ1,μ3}结束yesnoyesno三、算法框图开始输入：h置μ3=0，3=(μ3)，k=0置μ=μ335四、区间收缩原则与区间收缩率1>2?yesnoa=a1b=ba=ab=a2四、区间收缩原则与区间收缩率1>2?yesnoa=a1a36黄金分割法(Golden

Section

Method)又称为0.618法，是用于在单峰函数区间上求极小的一种方法。其基本思想是通过取试探点和进行函数值比较，使包含极小点的搜索区间不断减少，当区间长度缩短到一定程度时，就得到函数极小点的近似值。§3－3黄金分割法一、黄金分割法的取点原则1.对称取点2.等区间收缩率3.留点可用黄金分割法(GoldenSectionMethod)又称37二、黄金分割法的区间收缩率二、黄金分割法的区间收缩率38(1)置初始搜索区间[a,b]，并置精度要求ε，并计算左右试探点

al=a+0.382(b-a)a2=a+0.618(b-a)及相应的函数值l=(al)，2=(a2).三、黄金分割法的步骤(3)若|b-a|≤ε,做:如果l<2，则置*=a1；否则置*=a2，停止计算(*作为问题的解)。否则转(2).(2)如果l<2,则置b=a2，a2=a1，2＝1，并计算

al=a+0.382(b-a)，l=(al)

否则置a=a1，a1=a2，1＝2，并计算

a2=a+0.618(b-a)及相应的函数值，2=(a2).(1)置初始搜索区间[a,b]，并置精度要求ε，并计算左右试39四、黄金分割法的程序框图四、黄金分割法的程序框图40【例】用0.618法求解一维问题

min(α)=eα-5α，在区间[1,2]内的极小点，计算4步.

解

a=1，b=2，al=1.382，a2=1.618，

l=-2.927，2=-3.047,

所以l>2，去掉区间[1，al].详细计算结果见下表【例】用0.618法求解一维问题41

不要求每次迭代区间的收缩比不变,而希望在试验点个数相同的情况下，找出一种选取试验点的最佳策略，使得最终的极小区间的长度达到最小，换句话说，如果规定试验点的个数为n，且最终区间长度为1，问如何选取这n个点，使得原始区间的长度最大？令Ln表示试验点数为n、最终区间长度为1时，原始区间[a,b]的最大可能长度。设l为左试探点，r为右试探点，如果极小点*位于区间[a，l]，则在此区间内至多还可以有n-2个试验点，因此l-a≤Ln－2.§3－4Fibonacci法不要求每次迭代区间的收缩比不变,而希望在试验点个数相同的42另一方面,如果极小点*位于区间[l,b]内,则包括r在内,还可以作n-1个试验点，所以

b-l≤Ln-1.

因此b-a=(b-l)+(l-a)≤Ln－2+Ln-1,故有如下关系式:

Ln≤Ln－2+Ln-1显然,不计算函数值和仅计算一点处的函数值都不能使极小区间缩小，即L0=L1=1.由此可得，如果原始区间长度满足递推关系

F0=F1，Fn=Fn－2+Fn-1则Fn将是最大原始区间的长度.另一方面,如果极小点*位于区间[l,b]内,则包括r43Fn称为Fibonacci数。Fibonacci方法的基本思想与0.618法相同.在搜索区间[a,b]上,先取左、右试验点l

和r

比较函数值f(l)和f(r)重新确定搜索区间.(1)若f(l)<f(r)，去掉区间[r，b]，令a′=a，

b′=r，再计算新的试探点。Fn称为Fibonacci数。Fibonacci方法的基本思44(2)若f(l)>f(r)，去掉区间[a,r],令a′=l，b′=b,再计算新的试探点(2)若f(l)>f(r)，去掉区间[a,r],45所以Fibonacci方法与0.618法一样,除第一次外,以后每次只计算一个点处的函数值.Fibonacci方法每次保留的区间长度为Fk-1Fk,因此若计算n个试验点,最终的区间长度。因此,任给一精度要求ε,要求最终的区间长度小于ε,即有因此,任给一精度要求ε,要求最终的区间长度小于ε,即有那么选择n满足所以Fibonacci方法与0.618法一样,除第一次外,以46(1)置初始搜索区间[a，b]，并置精度要求ε，选取分离间隔δ<ε，求最小正整数n，使得Fn>（b-a）ε，并计算左右试探点l=a+Fn-2/

Fn(b-a)，r=a+Fn-1/

Fn(b-a)及相应的函数值fl＝f(l),fr＝f(r)。算法步骤(2)置n=n-1。(3)如果fr＝f(r)，则置b=r，r=l

，fr

＝fl

，。如果n>2,则计算l=a+Fn-2/

Fn(b-a)，fl＝f(l)；否则计算l=r-δ，fl＝f(l)。(4)fl≥fr

，置a=l

，l=r

，fl

＝fr

；如果n>2，则计算r=a+Fn-1/

Fn(b-a)，fr＝f(r)；否则计算r=l+δ，fr＝f(r)。(5)若n=1，做：如果fr＝f(r)，则置μ=r

；否则置μ=r

，停止计算(μ作为问题的极小点)。否则转(2)。(1)置初始搜索区间[a，b]，并置精度要求ε，选取分离间隔47

插值法是一类重要的一维搜索方法，其基本思想是利用搜索区间上某些点的信息构造插值多项式(通常不超过三次)p(α)，逐步用p(α)的极小点来逼近(α)的极小点α*。当(α)有比较好的解析性质时,插值法比区间收缩法(如0.618法)的效果好.本节介绍三种较为常见的插值法.§3－4二次插值法

在单峰区间[a,b]中，已知函数在三点μ1、μ2、μ3

（μ1<μ2<μ3)处的函数值为1、2、3，并满足1>2、3>2，即三点满足“两端高中间低”。这三个点可由得到：一、二次插值法的思想插值法是一类重要的一维搜索方法，其基本思想是利用搜索48由数值分析的知识,得到过三个点(μ1，1)、(μ2，2)、(μ3，3)的二次插值公式为对上式求导数，并求解方程p’(α)=0，得到p(α)的极小点由数值分析的知识,得到过三个点(μ1，1)、(μ2，2