当前课程知识点：优化设计 > 第四章 无约束优化方法 > 4.3 牛顿法 > 4.3 牛顿法
接续前一次课的梯度法
我们来讲解牛顿法
那么牛顿法的思想
首先我们通过一个引理
我们来看一看
我们用f(X)一元函数在Xk点出的二阶泰勒展开
我们考虑一下
之前我们讲过了很简单
f(X)约等于f(Xk)加上f'(Xk)
X减去Xk加上2的阶层f''(Xk) X-X的平方
对吧 那么如果我令它等于rk的话
假如f(X)是这么一个函数
这是我函数的要求的X*
那我这里找初始点什么Xk
我用在这一点的附近进行二阶泰勒展开
我用这个抛物线来近似地表示我的f(X)
然后呢我用抛物线的这个极值点呢来做映射
那我可以做抛物线这个极值点
得到X*
然后呢这一点呢我做映射
你想 如果说我f(X)就是一个二次函数
所以说呢直接就找到了
如果不是的话
我用这个点再进行一次迭代
即Xk+1等于Xk减去fgSkf''(Xk)
然后呢反复迭代
逼近最优点
看动画我们再取这一点
再做抛物线
然后呢再取这一点
再做抛物线
如此反复做
最后可能到最后的时候
我们说这个附近就是二次函数
一步就重合
就做到了找到极值点了
那么实际上呢这个就是它的什么迭代公式
推广到n维的话
n维多元函数f(X)在Xk点处的二阶泰勒展开
只取到二次项呢
f(Xk)加上∇f(Xk)的转置X减去XK加上二的阶层
或1/2X减X的转置乘以海森矩阵乘以X减Xk
令它等于新的函数
则满足极值条件是什么呢
对它的∇是等于0
可以做这样的公式
两边左乘一个海森矩阵
X*等于Xk加上海森矩阵的逆阵∇f(Xk)
当f(X)是跟我们刚讲一样
如果f(X)是二元函数的话
我们的X*呢就是我们原函数f(X)的X*
如果不是二次函数
那么则我们用它呢作为新的迭代点
去做Xk+1
如此反复
那么迭代公式就是我们这里边的
Xk+1等于Xk减去海森矩阵的逆阵∇f(Xk)
与迭代公式的通式进行比较
αk恒等于1的话
那我就什么
Sk=1等于负的海森矩阵的转置
然后呢∇f(Xk)我们把它称为是牛顿方向
那么牛顿法的基本思想呢在点Xk的邻域内呢
用一个二次函数去近似迭代f(X)
然后求出它的极小值
作为f(X)的下一次迭代点
重复迭代 最终逼近X*
迭代公式Xk+1等于Xk减去HXk的逆阵
然后呢∇f(Xk)
我们把负的海森矩阵的逆阵乘以∇f(Xk)称为是牛顿方向
我们看一下几何解释
这是Sk做切线做法线
这条线一定是我的
-∇f(X)的梯度方向
那我们看牛顿法呢做了一个椭圆
为什么做椭圆
因为什么
我认为在这个很小的区域内
我这个椭圆跟我原函数是等效的
那我就认为可能这一点就是我的极值点
那么方向就是什么
就这个方向
那么这是我的新的方向
这个方向就是谁
负的海森矩阵的逆阵乘以∇f(X)
做到了Xk+1
将负梯度的方向呢偏转一个角度所得到的
但是它有不足
第一因为步长等于1 效率很低
举个例子
我只能很机械的到这个地方就停了
我不能短一点
不能长一点
实际上这个方向很好
还能怎么
还能继续往前跑
跑到这一个地方
我利用这个方向往前走到这个地方
是不是更接近极值点
我从这个地方再做一个椭圆
可能就到这个点
但是你不行
牛顿告诉你
我只能到这个地方
在这一点处做你和做椭圆来做
所以说呢效率是变低了
第二个问题不仅效率低
甚至可能会造成函数值不降反升的情况
看一看Xk 本来我在这个地方
我这个方向非常好
我这个方向可能我就一步就指向圆心了
就到极值点了
结果什么 你很机械
你必须让我αk等于1
正是因为这样的一个问题
所以说呢人们对牛顿法进行了改进
一个很小的改进使它效果提升了很多
就是我们说的是修正的牛顿法
或称为广义牛顿法
或称为是阻尼牛顿法
基本思想
不统一取αk等于1
而是沿着Xk的处的牛顿方向进行一维搜索
求得极小点为Xk+1的点
那么框图什么
输入X0 ε
然后呢k等于0
计算∇f(Xk)然后呢gk∇f(Xk)
然后判断梯度是否小于ε
是不是收敛 收敛呢就输出
不收敛了
还需要进行迭代
那就是计算海森矩阵的逆阵
然后呢构造牛顿方向
Sk等于负的海森矩阵逆阵∇f(Xk)
然后呢再做一维搜索求αk
然后Xk+1等于Sk加上αkSk
然后回到这步进行循环
这是牛顿法和广义法的一个框图
看一个例子
求minf(X)等于X1平方加四倍X2平方
取X0等于1
然后呢求极值
那么求解呢第一步呢实际上就求梯度
∇f(X)等于2倍的X1 8倍X2
然后把1,1带进去变成了2,8
然后海森矩阵H(X)等于2,8,0,0
然后求海森矩阵的逆阵是0.5 0,0 0.125
求完它两个以后呢代入牛顿法迭代公式
Sk+1加上Xk减去αkH(Xk)的逆阵
然后∇f(Xk)带进去以后
S1就等于它 得完了以后1111等于0
然后呢∇f(X1)等于0
所以说呢X*就等于0 看到了吧
所以说它具有二次收敛速度函数的话
它一步就到极点很快
所以说二次函数用牛顿法一步就可以达到X*
我们说了对于牛顿法来说
它能够具有二次收敛性
它的寻优速度很快
但是呢它存在的问题是它在计算过程中呢
需要求解海森矩阵的逆阵
那我们知道要求一个矩阵的一个高维矩阵逆阵
还是比较困难的
因此说我们提出来的能否找到另外一种方法
使该方法对初始点要求不严格
又保持二次收敛性
即又保证了牛顿法的优点
并且呢不需要求解海森矩阵的逆阵
是否有这样的一种方法
那么我们说了有这样的方法
那就是我们这里边的变尺度法
DFP法我们称为是拟牛顿法
-1.1 优化设计概述
-1.2 优化设计的数学模型
-1.3 最优化问题几何解释
-第一章 讨论
--第一章讨论
-第一章 作业
--第一章 作业
-2.1 函数的梯度
-2.2 多元函数的泰勒展开
-2.3 二次函数
--2.3 二次函数
-2.4 无约束优化问题的极值条件
-2.5 凸函数
--2.5 凸函数
-2.6 约束优化问题的极值条件
-2.7 优化设计方法的基本思想与迭代终止准则
-第二章 讨论
--第二章讨论
-第二章 作业
--第二章 作业
-3.1 搜索区间的确定及区间消去法原理
-3.2 黄金分割法
-第三章 讨论
--第三章讨论
-第三章 作业
--第三章 作业
-4.1 共轭方向法及其改进
-4.2 梯度法
--4.2 梯度法
-4.3 牛顿法
--4.3 牛顿法
-4.4 变尺度法
--4.4 变尺度法
-第四章 讨论
--第四章讨论
-第四章 作业
--第四章 作业
-5.1 复合形法
--5.1 复合形法
-5.2 惩罚函数法
-第五章 作业
--第五章 作业
-6.1 遗传算法
--6.1 遗传算法
-6.2 人工神经网络与神经网络优化算法
-第六章 作业
--第六章 作业
-7.1 实例
--7.1 实例1
--7.2 实例2
-第七章 作业
--第七章 作业
-期末考试
--期末考试
