用数值法对于维目标函数求解的过程是：①确定初始搜索区间[a,b]，使该区间内仅包含有目标函数的一个极小点x*；②在初始区间内，才用分割比较将包含有目标函数极小点的区间逐渐缩短，直到该区间缩短到足够小的程度后，求出极小点x*（并不需要求出最优步长）。因此，首先来讨论初始区间的确定。
§3—1 初始搜索区间的确定
对于所有一维优化方法，首先遇到的一个共同问题是如何确定一个初始搜索区间[a,b]，使该区间内必包含有一个、且唯一的函数极小点x*。这个搜索区间就是所要确定的初始搜索区间。然后再通过一维优化方法，即区间分割法（例如格点法、黄金分割法、二次插值法），将包含有极小点在内的区间逐渐分割缩小，直至将区间缩至足够小，即可求得最优点的近似解x*。 本节我们将介绍用进退法确定初始搜索区间。
由一元函数的性质可知，在极小点x*左侧函数值呈单调下降，而在极小点的右侧，则函数值呈单调上升。利用这一性质，在确定一元函数的初始搜索区间时，首先任取一个初始点x，并选取一个适当的初始进退距h，然后进行试探运算，并根据试探运算的00结果，选择作前进或后退运算。
一、试探运算，以确定作向前运算还是作后退运算。
先置ｈ←ｈ，ｘ←ｘ，计算初始点ｘ和前进点ｘ的目标函数值ｙ、ｙ，即： 2011021ｙ←ｆ(ｘ)；ｘ←ｘ+ｈ，ｙ←ｆ(ｘ)
211122
根据图3.3(a)所示的情况，比较ｙ、ｙ的大小，以确定作向前运算还是作后退运算。 21
做后退运算
做前进运算
①当ｙ＜ｙ时，如图3.3(a)中实线的情况，则极小点x*必在ｘ的右侧，应再作前121进搜索运算。 ②当ｙ≥ｙ时，如图3.3(a)中虚线的情况，则极小点x*必在ｘ的左侧，应作后退221搜索运算。 二、前进搜索运算（ｙ＜ｙ时） 12将进退距ｈ加倍，即：ｈ←2ｈ，在x的左侧取第三个点ｘ，即ｘ←ｘ+ｈ，并计2313算ｘ的函数值：ｙ＝ｆ(ｘ) 333．
比较函数值ｙ和ｙ的大小，分为如下两种情况： 32第一种情况，若ｙ＜ｙ，如图3.3(b)中的虚线所示，则相邻的三个点ｘ、ｘ、ｘ31322处的目标函数值ｙ、ｙ、ｙ呈大、小、大的变化。根据函数的连续性可知，在区间内[ｘ,1213ｘ]必定包含有目标函数ｆ(x)的极小点x*，即令：ａ←ｘ，ｂ←ｘ，这就搜索得到了初313始搜索区间[ａ,ｂ]。
第二种情况，若ｙ≥ｙ，如图3.3 (b)中的实线所示，则极小点x*有可能位于ｘ的右侧，232需继续作前进运算。为了使下一次作前进运算时能采用与本次前进运算相同的迭代格式，重复前进搜索运算，对各点作如下置换：
ｘ←ｘ，ｙ←ｙ；ｘ←ｘ，ｙ←ｙ 31322212并再次将进退距加倍，ｈ←2ｈ，计算新的点ｘ及其对应的函数值ｙ： 33ｘ←ｘ+ｈ，ｙ←ｆ(ｘ)。 3233重复上述比较ｙ、ｙ的过程，直到最后出现ｙ＜ｙ，即相邻三个点ｘ、ｘ、ｘ3312223的函数值ｙ、ｙ、ｙ呈两端大，中间小的情况时，取左、右两端点为初始点搜索区间。 321
做后退运算 做前进运
算
三、后退搜索运算（ｙ≥ｙ时） 12如图3.3(a)中虚线所示，若ｙ≥ｙ时，取向ｘ点的左侧搜索，即作后退运算。 112取进退距ｈ置为负的初始进退距，即：ｈ← —ｈ，置换点号，使他们自右向左反向0排列，如图3.3(c)所示，以便采用前进搜索运算的迭代格式进行计算，作置换： ｘ←ｘ，ｙ←ｙ；（变量ｘ、ｙ仅作为置换数据的暂用单元） 313313ｘ←ｘ，ｙ←ｙ；ｘ←ｘ，ｙ←ｙ； 32121223经过上述置换后，ｘ、ｘ 从右向左排列，采用前进运算的迭代格式进行后退运算。21．
将进退距加倍，即ｈ←2ｈ，计算出第三个后退点ｘ及其函数值ｙ： 33ｘ←ｘ+ｈ，ｙ←ｆ(ｘ)
3332
比较函数值ｙ、ｙ的大小。 32①若ｙ＜ｙ时，如图3.3(c)中虚线Ⅱ所示，则初始区间已确定；
ａ←ｘ，ｂ←ｘ； 1332②若ｙ≥ｙ时，如图3.3(c)中实线Ⅰ所示，则应继续作后退运算，对各点作如下置32换：
ｘ←ｘ，ｙ←ｙ；ｘ←ｘ，ｙ←ｙ 31321222并将进退距加倍，即ｈ←2ｈ，计算新的点ｘ及其函数值ｙ：ｘ←ｘ+ｈ，ｙ←ｆ(ｘ) 332333重复比较函数值ｙ、ｙ的大小，直到最后出现ｙ＜ｙ，即出现相邻三个点ｘ、ｘ、233221ｘ的函数值呈两端大、中间小的情况为止，取其ａ←ｘ，ｂ←ｘ；可到初始搜索区间133［ａ,ｂ］。
当已经确定了初始搜索区间［ａ,ｂ］之后，接着的问题就是要在这个已确定的区间中，如何迅速找到目标函数的最优点ｘ*。通常采用区间分割法，将包含有目标函数极小点的区间逐步分割缩小，直到区间缩小到足够小为止。取缩小到足够小的区间中点作为目标函数极小点的近似解。缩小后的区间大小可由计算者根据实际问题的需要，预先规定一个足够小的正数，称为收敛精度或迭代精度，但经过ｋ次区间搜缩后，如果满足：
(k)(k)(k)(k)
│≤ε—ａ│ｂ
）/2＋ｂ。常用的区间分割法有：格点法、黄金分割法、二则终止计算，取ｘ*＝（ａ次插值
法等。
§3—3 黄金分割法
黄金分割法也称为0.618法。这种方法是通过对搜索区间内插入黄金分割点，并计算分割点的函数值和比较它们的大小，将包含有最优点的区间逐次缩短，当区间缩短到小于预先给定的足够小的数值时，即可获得目标函数的极小点的近似解。 一、区间缩短的基本方法
如图３.８所示，设有一元函数ｆ(x)，在给定的初始搜索区间内［ａ,ｂ］仅存在一个
极小点ｘ*，试在该区间内寻求目标函数的极小点，即最优点ｘ*。
为了缩短区间，在初始区间［ａ,ｂ］内按一定的规则对称地插入两分割点ｘ、ｘ， 21
,
ｂ］分为三段。分别计算两插入分割点的函数值；ax＝xb，使区间［ａ且ｘ＜ｘ，2211) (ｘ(ｘ)；ｙ←ｆｙ←ｆ2211 、ｙ的大小，有下列两种情况；比较ｙ21],ｘx的左侧，即必定在区间[ａ1、若ｙ＜ｙ，如图3.8(a)所示，极小点x*一定在2221，获作为缩短后的新搜索区间，即令：ｂ←ｘａ[,ｘ]内。因此，舍去右段xb，将区间222 。得新的区间［ａ,ｂ］]ｂ的右侧，即必定在区间[ｘ,、若ｙ≥ｙ，如图3.8(b)所示，极小点x*一定在x21121
，获ｂ]作为缩短后的新搜
索区间，即令：ａ←ｘ内。因此，舍去左段ax，将区间[ｘ,111 ,ｂ］。得新的区间［ａ。在每次区间缩短过程中，把缩短后的新区间长这样就完成了一次区间缩短（收缩） 度与原区间长度之比称为该次区间缩短率，用λ来表示，即：baxx12＝λ＝
abab在缩短后的新区间
内，我们还需要去续按照一定的规则，对称地插入新的分割点，在缩短后的的一次比较后，区间即可缩短一次。来继续缩短新区间。经过函数值ｙ、ｙ21，故下一次缩短时，只需要按一定的规则，对称地补或x新区间内，因有一个保留点x21的比较，如此反复计算，区间插一个分割点，并计算该点的函数值，重复函数值ｙ、ｙ21 即可逐次地加以缩短，直到满足迭代计算终止准则后，方可停止分割收缩计算。问题的关键是在每一次迭代中，补插的分割点应按什么规律确定，才能使迭代计算 在次数相同的条件下，区间缩短得最快呢？ 二、黄金分割法的取点原则为了加快区间缩短的速率，黄金分割法的分割点选取的原则是：每次区间缩短都具有相等的区间缩短率，即在每一次区间缩短时，新区间的长度与原区间的长度之比值为 。先推到如下：λ＝0.618新区间的若经过第一次区间缩短后，3.8(a)所示，设初始搜索区间的长度为L，如图1。由·ab＝
λＬ＝λax，设第一次区间缩短率为λ，则∵λ＝ax／ab，∴ax长度为12112112；·Ｌ＝ax（1—λ）x,于两分割点ｘ、ｘ在区间［ａｂ］内是对称插入的，即：ax＝b＝ab—1112221内，需补插]点，因而，在新区间[ａ,ｘ]在第二次区间缩短时，新区间[ａ,ｘ内保留有x212、ｙｘ)。通过比较ｙ←ｆ对称的新分割一个与xx点，并计算其函数值y，记作ｙ(3331331，设第二次区间缩],的数值大小，由于ｙ＜ｙ，于是第二次区间缩短时新区间为[ａｘ131L)－λ(ax1－λ111１1＝＝＝λ 短率为λ，在每次区间缩短时， 2axλLλ1211根据黄金分割法取点原则：都具有相等的区间缩短率，因此： 即：2
1－5－λ1＝0.618λ＝λ＝，计算出： λ＝λ＝λ，即：
分割法的分割取点原则为：
1
21
。黄金 2λ于是，
ｘ＝ａ＋(１－λ)Ｌ＝ａ＋0.382(b－a) ｘ＝ａ＋λＬ＝ａ＋0.618(b－a)
2
三、迭代终止条件
＜ε —ａｂ可终止迭代计算，其中迭代精度ε是设计者根据计算精度要求而预先给定的足够
当区间缩短到满足迭代终止条件时，即：
(k)(k)
小的正数值。迭代终止条件也可写成：
１１()()1(2)(2)1(1)(1)2(k)(k)k
(b－，ｂ＝λ－aｂ—ａ—ａ)＝λ＝λa) (b－a)，ｂ(b—ａ－＝λa)(bln[ε／（b
－a）]?kk(k)(k)，其中λ取为0.618
ln0.618(k)(k)]小于迭代精度ε或区间缩短区最终间长度[ｂ次—ａ数ｋ满足：当ln[ε／（b－a）]?k时，即可终止迭代计算，取最终区间的中
a)＝λ≤ε或即ｂ(b—ａ－点以及相应的函数值作为
(k)(k)
ln0.618目标函数的最优解输出：
]／2，Ｆ*＋ｂ＝Ｆ(ｘ*)
ｘ*＝[ａ四、计算步骤及程序流程图
１、在初始搜索区间［ａ,ｂ］内，按黄金分割法的取点原则，插入分割点：
ｘ＝ａ＋(１－λ)Ｌ＝ａ＋0.382(b－a) ｘ＝ａ＋λＬ＝ａ＋0.618(b－a) 并计算区间内插入
1
2
分割点ｘ、ｘ处的函数值ｙ、ｙ，即：ｙ←ｆ(ｘ)，ｙ←ｆ(ｘ)
21211212
２、比较插入分割点处函数值ｙ、ｙ的大小： 21若ｙ＜ｙ，如图3.8(a)所示，则舍去b点，
取新区间为[ａ,ｘ]，并将作如下置换： 212ｂ←ｘ,ｘ←ｘ，ｙ←ｙ 12122在新区间［ａ,ｂ］内补插x点，并计算其函数值y，即： 11ｘ←ａ＋(１－λ)Ｌ＝ａ＋0.382(b－a) ｙ←ｆ(ｘ)， 11转第
1
三步；
若ｙ≥ｙ，如图3.8(b)所示，则舍去a点，取新区间为［ｘ,ｂ］，并将作如下置换： 121ａ←ｘ，ｘ←ｘ，ｙ←ｙ 21211在新区间［ａ,ｂ］内补插x点，并计算其函数值y，即： 22ｘ＝ａ＋0.618(b－a),ｙ←ｆ(ｘ)
222(k)
若满足迭代终止准则ｂ３、由迭代计算终止准则判断是否需要继续进行迭代计算，(k))时，转
第4步；否则转第2—ａ≤ε步，继续缩短区间； ４、输出最优解：
(k)(k)
]／2，Ｆ*＋ｂ＝Ｆ(ｘ*)
*ｘ＝[ａ并停机。 程序流程图如下：
机械优化设计备课笔记2教案资料
