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
共轭梯度法相邻两轮搜索方向是一对共轭方向。