x2?x1?h x3?x2?h

具体步骤为：

⑴任意选取初始点x0和恰当的初始步长h； ⑵令x1?x0，取x2?x1?h，计算f(x1)、f(x2)；

⑶若f(x1)?f(x2)，说明极小点在x2右侧，应加大步长向前搜索。转⑷； 若f(x1)?f(x2)，说明极小点在x1左侧，应以x1点为基准反向小步搜索。转⑹； ⑷大步向前搜索：令h?2h，取x3?x2?h，计算f(x3)；

⑸若f(x2)?f(x3)，则f(x1)、f(x2)、f(x3)呈“高——低——高”排列，说明[x1,x3]即为所求的单峰区间；

若f(x2)?f(x3)，说明极小点在x3右侧，应加大步长向前搜索。此时要注意做变换：舍弃原x1点，以原x2点为新的x1点，原x3点为新的x2点。转⑷，直至出现“高——低——高”排列，则单峰区间可得；

⑹反向小步搜索（要注意做变换）：为了保证x3点计算公式的一致性，做变换：将

1原x2点记为新x1点，原x1点记为新x2点，令h??h，取x3?x2?h，转⑸

4例：用进退法确定函数f(x)?x2?6x?9的单峰区间[a，b]，设初始点x0?0，h?1。 解：①?x0?0②?x1?x0?0③?f(x1)?f(x2)

说明极小点在x2点右侧，应加大步长向前搜索

④令h?2h?2?1?2，取x3?x2?h?1?2?3 则f(x3)?0 ⑤?f(x2)?f(x3)

说明极小点在x3点右侧，应加大步长向前搜索 舍弃原x1?0的点，令x1?1x2?3，则f(x1)?4f(x2)?0

h?1

x2?x1?h?1f(x1)?9f(x2)?4

令h?2h?2?2?4，取x3?x2?h?3?4?7 则f(x3)?16?f(x2)?0 、f(x2)、f(x3)呈“高——低——高”排列

?[x1,x3]为单峰区间，即区间[1，7]即为所求

二、黄金分割法

黄金分割法是基于区间消去思想的一维搜索方法，其搜索过程必须遵循以下的原则：

⑴对称取点的原则：即所插入的两点在区间内位置对称；

⑵插入点继承的原则：即插入的两点中有一个是上次缩减区间时的插入点； ⑶等比收缩的原则：即每一次区间消去后，单峰区间的收缩率?保持不变。 设初始区间为[a，b]，则插入点的计算公式为：

x1?a?0.382(b?a) x2?a?0.618(b?a)

黄金分割法的计算步骤如下： ①给定初始区间[a，b]和收敛精度?； ②给出中间插值点并计算其函数值：

x1?a?0.382(b?a) f(x1) x2?a?0.618(b?a) f(x2)；

③比较f(x1)、f(x2)，确定保留区间得到新的单峰区间[a，b]； ④收敛性判别：计算区间[a，b]长度并与?比较，若b?a??，输出x*?否则转⑤；

⑤在保留区间内继承一点、插入一点，转②。

例：使用黄金分割法求解优化问题：minf(x)?x2?2x，?3?x?5解：①x1?a?0.382(b?a)??3?0.382?(5?3)?0.056②x2?a?0.618(b?a)??3?0.618?(5?3)?1.9441(a?b) 2??0.2。

f(x1)?0.115 f(x2)?7.667

③∵f(x2)?f(x1) ∴舍弃（1.944，5]，保留[-3，1.944] 1.944?(?3)??； ④继承原x1点，即x2?0.056f(x2)?0.115

f(x1)??0.987

插入x1?a?0.382(b?a)??3?0.382?(1.944?3)??1.111∵f(x2)?f(x1) ∴舍弃（0.056，1.944]，保留[-3，0.056] 0.056?(?3)??；

继承原x1点，即x2??1.111f(x2)??0.987

f(x1)??0.306

插入x1?a?0.382(b?a)??3?0.382?(0.056?3)??1.832∵f(x2)?f(x1) ∴保留[-1.832，0.056] 0.056?(?1.832)??； 继承原x2点，即x1??1.111f(x1)??0.987

f(x2)??0.888

插入x2??1.832?0.618?(0.056?1.832)??0.665∵f(x2)?f(x1) ∴保留[-1.832，-0.665]

如此迭代，到第8次，保留区为[-1.111,-0.940] ?0.940?(?1.111)?0.171?? ∴x*? §3.3梯度法 一、基本思想 对于迭代式Xk?11?(?1.111?0.940)??1.02552f(x*)??0.999

?k?X??S，当取搜索方向S???f(Xk)时构成的寻优算法，称

kkk为求解无约束优化问题的梯度法。 二、迭代步骤

⑴给定出发点Xk和收敛精度?；

⑵计算Xk点的梯度?F(Xk)，并构造搜索方向Sk???F(Xk)； ⑶令Xk?1?Xk??kSk，通过一维搜索确定步长?k，即：

minF(Xk??kSk)

求得新点Xk?1

⑷收敛判断：若?F(Xk?1)??成立，输出X*?Xk?1、F(X*)?F(Xk?1)，寻优结束；否则令k?k?1转⑵继续迭代，直到满足收敛精度要求。 三、梯度法的特点

梯度法寻优效率受目标函数性态影响较大。若目标函数等值线为圆，则一轮搜索就可找到极致点；若当目标函数等值线为扁椭圆时，收敛速度则显著下降。

梯度法中相邻两轮搜索方向相互垂直。（是否会证明） §3.4牛顿法

牛顿法分为基本牛顿法和阻尼牛顿法两种。

对于迭代式Xk?1kkkk?k当取??1且搜索方向S??[?2f(Xk)]?1?f(Xk)时?X??S，

构成的寻优算法，称为求解无约束优化问题的基本牛顿法；

?kk?1kkk对于迭代式X?X??S，取搜索方向S??[?2f(Xk)]?1?f(Xk)，?k为从Xk出发、沿牛顿方向做一维搜索获得的最优步长，所构成的寻优算法，称为求解无约束优化问题的阻尼牛顿法。

?k搜索方向S??[?2f(Xk)]?1?f(Xk)称为牛顿方向。

这里需要注意的是会求海塞阵的逆矩阵。 §3.5变尺度法

我们把具有Xk?1?Xk??kAk?f(Xk)迭代模式的寻优算法称为变尺度法。 其搜索方向表达式为：Sk??Ak?f(Xk)，称为拟牛顿方向，其中Ak称为变尺度矩阵。

在迭代开始的时候，A0?I；随着迭代过程的继续，Ak??[?2f(Xk)]?1?f(Xk)。 因此，变尺度法从梯度法出发，随着迭代过程的继续最终趋向于牛顿法。 §3.6共轭梯度法 一、共轭方向的概念

设H为对称正定矩阵，若有两个n维向量S1和S2，满足S1T?H?S2?0，则称向量S1与S2关于矩阵H共轭，共轭向量的方向称为共轭方向。

若有一组非零向量S1，S2，…，Sn满足SiT?H?Sj?0(i?j)，则称这组向量关于矩阵H共轭。

对于n元正定二次函数，依次沿着一组共轭方向进行一维搜索，最多n次即可得到极值点。

二、共轭方向的形成

对于函数f(X)?f(x1,x2,?,xn)?1TXHX?BTX?C 2沿任意方向S0在设计空间上任意做两条平行线，分别与目标函数等值线切于点X1、（能否给出证明） X2，令S1?X2?X1，则S0、S1关于矩阵H共轭。三、共轭梯度法

对于迭代式Xk?1?Xk??kSk，取搜索方向Sk?1???f(Xk?1)??kSk 其中：S0???f(X0)，?k??f(Xk?1)?f(X)k22

共轭梯度法相邻两轮搜索方向是一对共轭方向。