当前位置：文档之家 › 用Newton法、DFP法和BFGS法求函数极值

用Newton法、DFP法和BFGS法求函数极值

  • 格式：pdf
  • 大小：236.06 KB
  • 文档页数：7

下载文档原格式

  / 7

合集下载

数值优化算法

数值优化算法

数值优化算法在现代科学和工程中，数值优化算法被广泛应用于解决各种复杂问题。

数值优化算法是一种寻找函数极值的方法，这些函数可能具有多个自变量和约束条件。

数值优化算法对于在实际问题中找到最佳解决方案至关重要。

本文将介绍几种常见的数值优化算法及其应用。

一、梯度下降法梯度下降法是一种常用的数值优化方法。

它通过寻找损失函数的梯度来更新参数，以在每次迭代中逐步接近极值点。

梯度下降法的优势在于简单易实现，并且在大规模数据集上的表现良好。

这使得它成为许多机器学习算法中参数优化的首选方法。

二、牛顿法牛顿法是一种用于寻找函数极值点的迭代优化算法。

它利用函数的一阶导数和二阶导数信息来逼近极值点。

与梯度下降法相比，牛顿法的收敛速度更快，但它的计算复杂度更高。

牛顿法在求解高维问题或拟合复杂曲线时表现出色。

三、遗传算法遗传算法是一种模拟生物遗传和进化过程的优化算法。

它通过使用选择、交叉和变异等操作，模拟自然界的进化规律，来寻找函数的最优解。

遗传算法适用于复杂问题，能够在搜索空间中找到全局最优解。

在函数不可导或离散问题中，遗传算法能够提供有效的解决方案。

四、模拟退火算法模拟退火算法是一种启发式搜索算法，模拟了金属退火过程中原子随温度变化的行为。

模拟退火算法以一定的概率接受更差的解，并以较低的概率逐渐收敛到全局最优解。

模拟退火算法对局部极小点有一定的免疫能力，并且在大规模离散优化问题中表现出优越性。

五、粒子群算法粒子群算法是一种基于群体行为的优化算法。

它模拟了鸟群觅食的行为，通过迭代寻找问题的最优解。

粒子群算法通过评估适应度函数来引导粒子的移动，从而逐渐靠近最优解。

这种算法适用于多目标优化问题和高维函数优化。

结论数值优化算法在科学和工程领域扮演着至关重要的角色。

梯度下降法、牛顿法、遗传算法、模拟退火算法和粒子群算法是几种常见的数值优化方法。

它们各自具有不同的优势和适用范围，可以根据问题的特点选择合适的优化算法。

通过应用这些优化算法，可以帮助科学家和工程师在实际问题中找到最佳解决方案，推动技术的进步和创新。

求多元函数最小值的算法

求多元函数最小值的算法

求多元函数最小值的算法多元函数最小值的求解是数学中的一个重要问题，有许多实际应用场景，比如在优化问题中，需要找到使目标函数达到最小值的变量取值。

本文将介绍几种经典的求解多元函数最小值的算法。

一、梯度下降法：梯度下降法是一种迭代的优化算法，通过不断地沿着负梯度的方向更新变量的值，最终达到函数的局部最小值。

具体步骤如下：1.随机初始化变量的值。

2.计算目标函数在当前变量取值处的梯度向量。

3.根据梯度向量的方向和步长，更新变量的值。

4.重复步骤2和3，直至梯度接近于零或达到预定的迭代次数。

梯度下降法的优点是易于理解和实现，但缺点是容易陷入局部最小值，对于非凸函数的最小值搜索效果较差。

二、牛顿法：牛顿法是一种基于二阶泰勒展开的优化算法，通过使用函数的一阶和二阶偏导数来近似目标函数，并找到近似目标函数的最小值。

具体步骤如下：1.随机初始化变量的值。

2.计算目标函数在当前变量取值处的一阶和二阶偏导数。

3.根据一阶和二阶偏导数的值，更新变量的值。

4.重复步骤2和3，直至梯度接近于零或达到预定的迭代次数。

牛顿法的优点是收敛速度快，缺点是计算复杂度高，需要计算目标函数的一阶和二阶偏导数。

三、共轭梯度法：共轭梯度法是一种特殊的梯度下降法，通过利用前一轮迭代的梯度信息来加速收敛，并提高搜索最小值的效率。

具体步骤如下：1.随机初始化变量的值。

2.计算目标函数在当前变量取值处的梯度向量。

3.根据梯度向量和共轭方向的线性组合，更新变量的值。

4.重复步骤2和3，直至梯度接近于零或达到预定的迭代次数。

共轭梯度法的优点是收敛速度较快，效果较梯度下降法更好，但需要函数的梯度信息。

四、粒子群优化算法：粒子群优化算法是一种启发式优化算法，通过模拟鸟群寻找食物的过程来搜索目标函数的最小值。

具体步骤如下：1.随机初始化粒子的位置和速度。

2.计算每个粒子的适应度值（目标函数的值）。

3.更新每个粒子的速度和位置。

4.重复步骤2和3，直至达到预定的迭代次数。

向量极值问题

向量极值问题

向量极值问题向量极值问题是数学中的一个重要概念，研究如何找到向量函数的最大值或最小值点。

在应用中，向量极值问题经常出现在经济学、物理学、工程学等领域。

本文将介绍向量极值问题的基本概念、求解方法以及实际应用。

一、向量极值问题的基本概念向量极值问题是指在一定条件下，如何找到使得向量函数取得最大值或最小值的点。

在向量极值问题中，我们通常需要考虑多个自变量对应的向量函数，并通过约束条件确定自变量的取值范围。

常见的向量极值问题可以用以下形式表示：求向量函数f(x)的极值，其中x=(x1,x2,...,xn)为自变量，f(x)为目标函数，约束条件为g(x)=0。

解决向量极值问题的方法主要有两种：拉格朗日乘数法和牛顿法。

下面分别介绍这两种方法的基本原理和步骤。

1. 拉格朗日乘数法拉格朗日乘数法是一种常用的求解约束优化问题的方法，也可用于求解向量极值问题。

其基本思想是在目标函数中引入一个或多个拉格朗日乘子，将约束条件转化为目标函数的一部分。

通过求解构造的拉格朗日函数的梯度为零的点，即可得到极值点。

2. 牛顿法牛顿法是一种迭代求解非线性方程组的方法，也可用于求解向量极值问题。

其基本思想是利用目标函数的梯度和海森矩阵进行迭代，逐步逼近最优解。

通过迭代求解，可以找到目标函数的驻点，再通过判断海森矩阵的正定性确定极值点。

三、向量极值问题的实际应用向量极值问题在实际应用中具有广泛的应用价值。

以下是几个常见的应用场景：1. 经济学中的应用在经济学中，向量极值问题常常用于研究经济模型中的最优决策问题。

例如，在生产函数中，可以通过求解使得产量最大的自变量取值，确定最优生产方案。

2. 物理学中的应用在物理学中，向量极值问题常常用于描述物理系统中的平衡状态。

例如，通过求解势能函数的极值点，可以确定物体在重力场中的平衡位置。

3. 工程学中的应用在工程学中，向量极值问题通常用于优化设计问题。

例如，在工程设计中，可以通过求解满足约束条件的目标函数的极值点，确定最优设计方案。

拟牛顿法

拟牛顿法

•主页•专栏作家•量化基础理论•软件使用经验•量化软件•资源导航•资料下载•量化论坛搜索搜索用户登录用户名:*密码:*登录•创建新帐号•重设密码首页拟牛顿法及相关讨论星期三, 2009-06-17 00:24 —satchel1979使用导数的最优化算法中，拟牛顿法是目前为止最为行之有效的一种算法，具有收敛速度快、算法稳定性强、编写程序容易等优点。

在现今的大型计算程序中有着广泛的应用。

本文试图介绍拟牛顿法的基础理论和若干进展。

牛顿法(Newton Method)牛顿法的基本思想是在极小点附近通过对目标函数做二阶Taylor展开，进而找到的极小点的估计值[1]。

一维情况下，也即令函数为则其导数满足因此(1)将作为极小点的一个进一步的估计值。

重复上述过程，可以产生一系列的极小点估值集合。

一定条件下，这个极小点序列收敛于的极值点。

将上述讨论扩展到维空间，类似的，对于维函数有其中和分别是目标函数的的一阶和二阶导数，表现为维向量和矩阵，而后者又称为目标函数在处的Hesse矩阵。

设可逆，则可得与方程(1)类似的迭代公式：(2)这就是原始牛顿法的迭代公式。

原始牛顿法虽然具有二次终止性（即用于二次凸函数时，经有限次迭代必达极小点），但是要求初始点需要尽量靠近极小点，否则有可能不收敛。

因此人们又提出了阻尼牛顿法[1]。

这种方法在算法形式上等同于所有流行的优化方法，即确定搜索方向，再沿此方向进行一维搜索，找出该方向上的极小点，然后在该点处重新确定搜索方向，重复上述过程，直至函数梯度小于预设判据。

具体步骤列为算法1。

算法1：(1) 给定初始点，设定收敛判据，.(2) 计算和.(3) 若< ，则停止迭代，否则确定搜索方向.(4) 从出发，沿做一维搜索，令.(5) 设，转步骤(2).在一定程度上，阻尼牛顿法具有更强的稳定性。

拟牛顿法(Quasi-Newton Method)如同上一节指出，牛顿法虽然收敛速度快，但是计算过程中需要计算目标函数的二阶偏导数，难度较大。

牛顿法和拟牛顿法

牛顿法和拟牛顿法

⽜顿法和拟⽜顿法⽜顿法和拟⽜顿法⽜顿法（Newton method）和拟⽜顿法（quasi Newton method）是求解⽆约束最优化问题的常⽤⽅法，收敛速度快。

⽜顿法是迭代算法，每⼀步需要求解海赛矩阵的逆矩阵，计算⽐较复杂。

拟⽜顿法通过正定矩阵近似海赛矩阵的逆矩阵或海赛矩阵，简化了这⼀计算过程。

⽜顿法我们假设点x∗为函数f(x)的根，那么有f(x∗)=0。

现在我们把函数f(x)在点x k处⼀阶泰勒展开有：假设点x k+1为该⽅程的根，则有：可以得到这样我们就得到了⼀个递归⽅程，我们可以通过迭代的⽅式不断的让x趋近于x∗从⽽求得⽅程f(x)的解。

最优化问题对于最优化问题，其极值点处⼀阶导数为0。

因此我们可以在⼀阶导数处利⽤⽜顿法通过迭代的⽅式来求得最优解，即相当于求⼀阶导数对应函数的根。

⾸先，我们对函数在x0点处进⾏⼆阶泰勒展开对x求导可得由于在极值点处，于是从⽽可以得出下⼀个x的位置其迭代形式为对于多维函数，⼆阶导数就变成了⼀个海森矩阵，⼆阶泰勒展开公式如下:图中的便是海森矩阵。

迭代公式就变成了。

我们可以看到，当 H k为正定（ H k-1也正定）的时候，可以保证⽜顿法的搜索⽅向是向下搜索的。

拟⽜顿法当特征特别多的时候，求海森矩阵的逆矩阵，运算量是⾮常⼤且慢，考虑⽤⼀个n阶矩阵来替代，这就是拟⽜顿法的基本思路。

通过以上可以得到因此，对于我们所选择的替代矩阵G k，需要满⾜两个条件：1. 拟⽜顿条件，即2. 要保证G k为正定矩阵，这是因为只有正定才能保证搜索⽅向是向下搜索的。

由于每次迭代都需要更新矩阵G k ，下⾯介绍⼀些⽅法。

DFP，这⾥的D K相当于前边提到的G K ，这个迭代公式的关键是每⼀步的校正矩阵ΔD K的构造。

我们采⽤待定法，先将ΔD K待定为下⾯的形式:α和β为待定系数，u和v为待定向量。

uu T和vv T均为对称矩阵，因此可以保证ΔD K也是对称矩阵。

将待定公式代⼊迭代公式，可得:D k+1·y k = s k上述变化是因为是两个数，不妨设为可得将其带⼊s k的表达式，可得不妨直接取代回上⾯α和β的表达式，得:将上两式代回ΔD K的表达式，得这样就可以使⽤迭代公式来进⾏拟⽜顿法的计算了。

第2章优化设计-2

第2章优化设计-2

（2-45）
上式中的搜索方向 S (k)
称为牛顿方向，
可见原始牛顿法的步长因子恒取： (k) 1 ，因此，原始牛顿法是一
种定步长的迭代过程。
牛顿算法对于二次函数是非常有效的，迭代一步就可达到极值点， 而这一步根本不需要进行一维搜索。
对于高次函数，只有当迭代靠近极值点附近，目标函数近似二次函 数时，才会保证很快收敛，否则也可能导致算法失败。
(2-57)
但其中的校正矩阵的计算公式为
A(k )

X
1
(
k
)
T

g (k )
{X
(k)

X
(
k
)
T


X (k)
X
(
k
)
T


g
(k
)
T

A(k )g (k )
X
(k)
T

g (k )

A(k )g (k )

X
(k
)
T

X (k )
g
BFGS法 的优点:
在于计算中它的数值稳定性强， 所以它是目前变尺度法中最受欢迎的一种算法。
2.5 约束优化方法
工程中的大量优化设计问题，都是约束优化问题， 这类问题的一般数学模型为：
min f ( X ), X Rn s.t.gu ( X ) 0u 1, 2, hv (X ) 0v 1, 2, ,
[X (k ) ]T g (k )
[g (k ) ]T A(k )g (k )
（2-54） （2-55）
式中: X (k) X (k1) X (k)
第 k 次迭代中前后迭代点的向量差 ；

非线性代数方程(组)的解法


06
应用举例与算法实现
应用举例
经济学
非线性方程组在经济学中广泛应用于描述市场均衡、消费者行为等问题。例如，求解供需平衡价格时，可以通过构建 非线性方程组来表示供给和需求函数，进而求解市场均衡价格。
工程学
在机械、电子等工程领域，非线性方程组常用于描述系统的动态行为。例如，在控制系统中，通过建立非线性状态方 程来描述系统的状态变化，可以求解系统的稳定性、响应特性等问题。
拟牛顿法是对牛顿法的改进，通过近 似计算雅可比矩阵或其逆矩阵来减少 计算量。常见的拟牛顿法有BFGS方 法、DFP方法等。程序设计时，需要 实现拟牛顿法的迭代过程，包括选择 合适的拟牛顿公式、更新近似矩阵等 步骤。
信赖域方法
信赖域方法是一种全局收敛的非线性 方程组求解算法，其基本思想是在每 次迭代中构造一个信赖域，然后在该 区域内寻找使目标函数充分下降的试 探步。程序设计时，需要实现信赖域 方法的迭代过程，包括构造信赖域、 求解子问题、更新信赖域半径等步骤 。
04
解析解法分离变量法源自01 适用于可将方程中的变量分离为两个或多个独立 函数的情况。
02 通过将方程两边同时积分，得到各变量的通解。 03 需要注意积分常数的确定，以及解的合理性验证。
行波法
01
适用于可化为行波形式的非线性方程。
02
通过引入行波变换，将原方程化为关于行波参数的常微分方 程。
03
步骤
1. 选定适当的坐标轴，将方程的变量表 示为坐标轴上的点。
等倾线法
定义：等倾线法是一种通过绘 制等倾线（即斜率相等的线） ，从而找出方程解的方法。
步骤
1. 将方程转化为斜率形式， 即 y' = f(x, y)。
3. 通过观察等倾线的交点、 切线等性质，可以判断方程 的解的存在性、唯一性等。

matlab牛顿法求极小值

在MATLAB中，我们可以使用牛顿法来求解函数的极小值。

以下是一个简单的示例，展示了如何使用牛顿法来求解一个函数的极小值。

首先，我们需要定义目标函数以及其一阶和二阶导数。

假设我们的目标函数是f(x) = x^2 - 4x + 4，其一阶导数是f'(x) = 2x - 4，二阶导数是f''(x) = 2。

然后，我们可以编写一个MATLAB脚本来实现牛顿法：matlab复制代码function[minx, iter] = newton(f, df, d2f, x0, tol, max_iter)% f: 目标函数% df: 目标函数的一阶导数% d2f: 目标函数的二阶导数% x0: 初始点% tol: 允许误差% max_iter: 最大迭代次数iter = 0;x = x0;while abs(df(x)) > tol && iter < max_iterx = x - df(x) / d2f(x);iter = iter + 1;endminx = x;end接下来，我们可以调用这个函数来求解目标函数的极小值：matlab复制代码f = @(x) x.^2 - 4.*x + 4; % 目标函数df = @(x) 2.*x - 4; % 目标函数的一阶导数d2f = @(x) 2; % 目标函数的二阶导数x0 = 0; % 初始点tol = 1e-6; % 允许误差max_iter = 100; % 最大迭代次数[minx, iter] = newton(f, df, d2f, x0, tol, max_iter);fprintf('极小值点: %f\n', minx);fprintf('迭代次数: %d\n', iter);这段代码将使用牛顿法从初始点x0开始搜索目标函数的极小值，并打印出找到的极小值点和迭代次数。

例题是唐老师教材_1025_拟牛顿法(DFP算法)


)
Step4: 令 k
k 1,
返回Step2.
注: 第一步迭代与最速下降法相同.
三. 对称秩2算法（DFP校正公式）
设校正矩阵的形式为:
H k H k 1 k uk uk
T
Page 10
k vk vk
T
( II )
其中 k 0, uk = uk 1 , uk 2 , , ukn 0
x
k 1
x k d .
k k
Page 13
Step3: 计算
k 1 x
k 1
x
k 1
k
k 1 f ( x
) f ( x )
k T
H k 1 H k d
k 1
k 1 k 1 k 1 k 1
T k 1
)
H k k 1 k 1 H k
2
0 4 , 10 1
0 8
2 x1 f x , 8 x2
0
2 f x 0
2 2 0 0 f ( x ) , d f ( x ) 8 8
f
T
H1 H 0
1 1
T
T
1 1

H 0 1 1 H 0
T
1 H 0 1 Page 16
T
又
0.26154 1 x x 1.04 x
1
f x
0
0.52308 8.36923
1 0 0
Page 15
f
x 1.47692,
1
0.36923 ,

非线性规划-无约束问题


一般地，解非线性规划问题要比解线性规划问题困难的多，因为它不像解线性规划问题有单纯形法这一通用的方法，非线性规划目前还没有适合于各种问题的一般算法，各个方法都有自己特定的应用范围。
1.1 非线性规划问题及其数学模型
例：某金属制品厂要加工一批容积为1米3的长方形容器，按规格要求，上下底的材料为25元/m2，侧面的材料为40元/m2，试确定长、宽、高的尺寸，使这个容器的成本最低。
线性规划：
可能在其可行域中的任意一点达到。
非线性规划：
02
01
非线性规划的解的特点
目标函数是线性函数，可行域为凸集，求出的最优解就是整个可行域上的全局最优解。
线性规划：
01
有时求出的解是一部分可行域上的极值点，但并不一定是整个可行域上的全局最优解。
非线性划：
02
1.2 极值问题
局部极值定义
定理1：极值存在的必要条件
称该点列{X(k)}收敛于X*. 由于算法产生的点列使目标函数值逐步减小，称这一算法为下降算法。
或
超线性收敛：当 1<<2, q>0，或＝1, q＝0时，称为超线性收敛速度
二阶收敛：当 =2 ，k充分大时有
收敛速度
一般地认为，具有超线性收敛或二阶收敛速度的算法是比较快速的算法。
对于不同的问题，要根据具体情况来选择算法，因为我们事先并不知道最优解，迭代到什么时候停止呢？常用的准则是：
01
02
01
迭代中我们从一点出发沿下降可行方向找一个新的、性质有所改善的点。
02
下降方向：
可行方向：设 ∈S，d∈Rn,d≠0,若存在 ，使 ，称d 为 点 的可行方向。
2
如果继续缩小区间[a,b1](或[a1,b])，就需要在区间[a,b1](或[a1,b])内取一点b2，并计算出f(b2)的值，并与f(a1)比较。
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

ᓔ ྟ 䆒㕂㊒ᑺˈ㒭ᅮ߱ྟⱘ䗁ҷ⚍
yes
ℹ䭓||S||<㊒ᑺ˛
no
䅵ㅫ೼㄀k⃵䗁ҷ⚍໘ⱘ⍋Ểⶽ䰉H ੠ẃᑺ৥䞣 ㄀k+1ℹ 䗮䖛㾷㒓ᗻᮍ⿟ˈᕫࠄ㄀kℹⱘᮍ৥ Sk 㒧ᴳ䗁 ҷˈᕫࠄ ᵕؐ⚍X
಴ЎSk=X k+1 -Xk; ᠔ҹˈᕫࠄᮄⱘ䗁ҷ⚍Xk+1=X k +S k.
图 1: Newton方法的算法简图 b)计算(xk , yk , zk )点处的海森矩阵和梯度向量时，调用函数[Hessen, grads] = HessenM atrica ndg rids(x, y, z )求 解。 → − → c)由于− x− k+1 和xk 满足方程： → − − → − → − → −1 ∗ − →) x− ∇ f (x k+1 = xk − Hf (xk ) k 所以为了避免求海森矩阵的逆矩阵，令 − → → − → sk = − x− k+1 − xk 就转化为解线性方程组： − − − − − → → → Hf (xk ) ∗ − sk = −∇f (− x k)
− → 考 察 梯 度 向 量 ∇ (f (x, y, z ))容 易 看 出 ， 在(x, y, z ) ∈ [−1, 1] ∗ [−1, 1] ∗ [−1, 1]范 围 内 ， 只 − → 有(0, 0, 0)点能使得 ∇ (f (0, 0, 0)) = 0，其余点梯度均不为0，所以，(0, 0, 0)点是唯一的一个 极值点，且，求得海森矩阵 2.0200 0 0 Hf = (12) 0 0.6000 0 0 0 4.0000 因为|Hf | = 4.8480 > 0,所以(0, 0, 0)点是函数的一个极小值点。相应的极小值为f (0, 0, 0) = 0. 下文分别用Newton法、DFP方法和BFGS方法三种方法求取函数极值点，并比较其特点。
2 2 2
1
函数分析
2 2 2 2 2 2
优化函数为f (x, y, z ) = e0.01x +0.2y +z − e−x −0.1y −z + (sin(x2 + 1.1y 2 + z 2 ))2 , (x, y, z ) ∈ [−1, 1] ∗ [−1, 1] ∗ [−1, 1]。容易观察出函数为偶函数，所以，函数具有空间的对称性。分别 对函数求一次和二次导数，得到：
2 2 2 2 2 2 ∂2f = 0.008xye0.01x +0.2y +z − 0.4xye−x −0.1y −z + 8.8xycos(2(x2 + 1.1y 2 + z 2 )) (5) ∂x∂y
2 2 2 2 2 2 ∂2f = 0.04xze0.01x +0.2y +z − 4xze−x −0.1y −z + 8xzcos(2(x2 + 1.1y 2 + z 2 )) ∂x∂z
d)用一维优化方法求取第k步的步长lk ，使得： →+l ∗− → − → − → f (− x k k sk ) = minf (xk + l ∗ sk ) 由于问题较为简单，所以此处采用精确求解法(黄金分割法，详见函数l = stepl engtha ccurate(xk , yk , zk , sk ))求 解lk 。
(6)
1
2 2 2 2 2 2 ∂2f = 0.1(1.6y 2 + 4)e0.01x +0.2y +z + 0.1(2 − 0.4y 2 )e−x −0.1y −z ∂y 2
+2.2sin(2(x2 + 1.1y 2 + z 2 )) + 9.68y 2 cos(2(x2 + 1.1y 2 + z 2 ))
4
ᓔ ྟ 䆒㕂㊒ᑺˈ䆒㕂߱ྟӬ࣪⚍ˈҸH0=I˗
||gk||<㊒ᑺ? No 䅵ㅫᔧࠡӬ࣪⚍ⱘẃᑺ৥䞣gkˈᑊ⫼䖥 ԐⱘHⶽ䰉ᕫࠄ㄀kℹⱘᮍ৥˖ Sk= - Hk * gk ⫼ϔ㓈Ӭ࣪∖㾷㄀kℹℹ䭓ؐl˖Փᕫ f=min{f(Xk+l*Sk)}
yes
㒧ᴳ䗁 ҷˈᕫࠄ ⒵䎇㊒ᑺ ⱘᵕؐ⚍
㄀k+1ℹ
ᕫࠄXk+1,ᑊ䅵ㅫ㄀k+1ℹⱘH䖥Ԑⶽ䰉
迭代次数 4 3 3 5 5 9919113 4124048 13 10
出，Newton方法对初值的依赖性很大，当初值越靠近真实的极值点时，牛顿方法能越迅速 且准确地收敛到极值点上去。然而，当初值点偏离了极值点时，用牛顿方法几乎得不得正 确的结果，甚至不收敛并且迭代次数随之增大。所以，用Newton方法时，初值的选取至关 重要。
2
Newton方 法优化
牛顿方法是将函数在某点处泰勒展开至二阶，近似认为函数在此附近为二次函数，用二次 函数的极值点作为新的迭代点。如此循环，直至步长为0(精度范围内)，结束迭代，得到整 个函数的极值点。其算法思路如图一所示。 算法说明： a)如图一所示，设置精度为10−8 ,由于Newton算法对初值较为敏感，如果初值偏离极值太 远，那么可能得不得正确的极值点。所以由上文得到的判断，将初值设为(0, 0, 0)点附近 的(0.1, 0.1, 0.1) 2
− → ∂f ∂f ∂f T , ] ; ∇ (f (x, y, z )) = [ , ∂x ∂y ∂z Hf =
∂2f ∂x2 ∂2f ∂x∂y ∂2f ∂y∂z ∂2f ∂x∂z ∂2f ∂y∂z ∂2f ∂z 2
(10)
(11)
用Newton法、DFP方法和BFGS方法求解函数极值
00986096 沈欢 北京大学工学院，北京100871 2011 年 11 月 12 日 摘 要
本文分别用Newton法、DFP方法和BFGS方法求解函数f (x, y, z ) = e0.01x +0.2y +z − −x2 −0.1y 2 −z 2 e + (sin(x2 + 1.1y 2 + z 2 ))2 , (x, y, z ) ∈ [−1, 1] ∗ [−1, 1] ∗ [−1, 1]的极值，并 讨论三种方法的特点。
3
DFP方 法 优 化
DFP方法是综合了牛顿法和最速下降法的方法，既保留了牛顿法快速的收敛性，又克服了 牛顿法对初值的依赖性。其基本思路是寻找海森矩阵的近似矩阵H，之后用近似矩阵H得到 第k步的方向，用一维搜索得到步长值，更新优化点。当满足精度时，迭代结束，得到极值 点。其算法思路如图二所示。 算法说明： a)初始时，精度设置为10−8 ,由于DFP算法对初始优化点的依赖性不高，所以，初值可以取 得稍微宽松。对于初始的海森矩阵的近似矩阵H取为单位矩阵即H = I3∗3 . − → → → → = (x , y , z )点处的梯度调用[Hessen, grads] = HessenM atric nd rids(x, y, z )函 b)令− gk = ∇ f (− xk ),其中在− x k k k k a g 数求解。 → c)第k步的方向由梯度− gk 和近似矩阵Hk 给出，为： − → → sk = −Hk ∗ − gk
→ − → g )迭代结束的条件可以由 − x− k+1 − xk < accuracy 给出。 结果讨论： DFP方法是综合了牛顿法和最速下降法的方法，既能保证快速的收敛性，又对初值的要求 不是太高。表二显示了用DFP算法(直接调用函数[extremep oint, f lag ] = DF Pa ccurate)求 解的结果。 与Newton方法比较，从表一和表二中，可以看出，在相同的初值条件下，Newton法的收 敛速率基本上都快于DFP方法。并且得到的极值点相对于真实极值点的精度也高于DFP方 法，但是，当初始值偏离了真实值较大时，Newton法收敛速度远不如DFP方法，并且甚至 不收敛或得到错误解，且得到的极值点的精度也低于DFP方法。
的问题。采用G-S迭代法求解，调用函数f unctionx = GSi teration(A, b, n)可求解该方程。 → − → − → d)解出方向后，更新优化点的值为− x− k+1 = xk + sk 当满足精度要求时，迭代结束可以得到满足精度要求的优化值，作为极值点。函数详 见f unction[extremep oint, f lag ] = N ewton 结果讨论: 如果取初值点位(0.1, 0.1, 0.1),那么调用Newton方法的结果显示extremep oint = 1.0e − 018 ∗ [−0.3312, −0.2546, 0],f lag = 4.得到的结果非常接近于理论值(0,0,0).并且迭代次数4，非 常的小。体现了牛顿方法当初值点取在极值点附近时的快速收敛性。由于Newton方法 依赖于初值，表一给出了不同初值时用Newton方法得到的结果的实验。 从表中可以看 3
(2)
2 2 2 2 2 2 ∂f = 2z ∗ e0.01x +0.2y +z + 2z ∗ e−x −0.1y −z + 2z ∗ sin(2(x2 + 1.1y 2 + z 2 ))) ∂z
(3)
和：
2 2 2 2 2 2 ∂2f = (0.0004x2 +0.02)e0.01x +0.2y +z +(2−4x2 )e−x −0.1y −z +2sin(2(x2 +1.1y 2 +z 2 ))+8x2 cos(2(x2 +1.1y 2 +z 2 )) 2 ∂x (4)
图 2: DFP方法的算法简图 e)得到lk 后，就可以更新优化点使得 − → − → − → x− k+1 = xk + lk ∗ sk → ,并且可以求得在− x− k+1 处的梯度值。 f )用上述信息可以更新近似的海森矩阵使得： Hk+1 = Hk − → → Hk ∗ − gk ∗ ( − gk )T ∗ Hk + − → → ( gk )T ∗ Hk ∗ − gk ( − →∗( − →)T x x k k − → → xk )T ∗ − gk