当前位置：文档之家 › 第三章 梯度法和共轭梯度法

第三章 梯度法和共轭梯度法

  • 格式：ppt
  • 大小：1.10 MB
  • 文档页数：25

下载文档原格式

  / 25

合集下载

共轭梯度法和梯度下降法

共轭梯度法和梯度下降法

共轭梯度法和梯度下降法共轭梯度法和梯度下降法是两种常用的优化算法，它们在解决最优化问题时具有重要的作用。

本文将分别介绍共轭梯度法和梯度下降法的原理、优势和应用领域，并对它们进行比较和总结。

一、共轭梯度法共轭梯度法是一种迭代算法，用于求解线性最小二乘问题或者解线性方程组。

它的核心思想是通过迭代求解一系列的共轭方向，从而不断逼近最优解。

共轭梯度法的优势在于它能够充分利用问题的特殊结构，避免不必要的计算。

相比于梯度下降法，共轭梯度法通常收敛更快，并且对于大规模问题的求解效果更好。

共轭梯度法主要应用于求解线性方程组、最小二乘问题以及特定的优化问题，如信号处理、图像处理和机器学习等领域。

二、梯度下降法梯度下降法是一种基于梯度的迭代优化算法，用于求解无约束最优化问题。

它的核心思想是沿着负梯度方向不断迭代，直至达到最优解或者满足停止条件。

梯度下降法的优势在于它的简单性和易于实现性。

它不需要求解二阶导数，只需要计算一阶导数，因此对于大规模问题的求解也比较高效。

梯度下降法广泛应用于机器学习中的参数优化问题，如线性回归、逻辑回归和神经网络等。

此外，它还可以用于函数拟合、特征选择和降维等领域。

三、共轭梯度法与梯度下降法的比较共轭梯度法和梯度下降法都是常见的优化算法，它们的选择取决于具体的问题和需求。

1. 收敛速度：共轭梯度法通常比梯度下降法收敛更快。

共轭梯度法在每次迭代时利用了前面所有迭代步骤的信息，可以更快地逼近最优解。

2. 内存消耗：梯度下降法只需要存储当前的梯度信息，而共轭梯度法需要存储一系列的共轭方向。

因此，对于大规模问题，梯度下降法在内存消耗方面更具优势。

3. 线性方程组求解：共轭梯度法是一种求解线性方程组的有效方法，而梯度下降法通常不适用于求解线性方程组。

4. 二次型优化问题：共轭梯度法对于二次型优化问题的求解效果更好。

梯度下降法在处理非二次型问题时可能会出现收敛速度慢、局部最优等问题。

共轭梯度法和梯度下降法是两种常用的优化算法。

第三章 优化设计(4节

第三章 优化设计(4节

第四节多维无约束优化方法4.1最速下降法（梯度法）x，使f(x)minf(x+α对于多元函数，求极小点k+1k+1)=minf(x k kS k)，需要确定两个内容：步长αk，方向S k，不同的搜索方向导致了不同的优化方法。

主要有：梯度法、共轭导致了不同的优化方法主要有：梯度法共轭梯度法、牛顿法、变尺度法、坐标轮换法、Powell法。

z思想函数值变化最快的方向是其梯度方向，而且负梯度方向是函数值下降最快的方向。

故沿负梯度方向搜索。

方向是函数值下降最快的方向故沿负梯度方向搜索z迭代格式z步骤1）给定初始点，迭代精度，维数。

2）置0→k。

3）确定搜索方向：计算迭代点x k的剃度，以及剃度的模，进而确定搜索方向s k。

4）求最优步长αk：从x k点出发，沿负剃度方向进行维搜索求最优步长α，f(xαS)min f(xαS)。

一维搜索求最优步长k k+k k＝min f(x k+k5）检验是否满足终止条件，若满足，终止迭代，输k→x*k)→f(x*)，否则，进入下一步出最优解x x，f(x f(x)，否则，进入下步。

6）计算新的迭代点x k＋1＝x k+αk S k。

z搜索路线z特点1）迭代过程简单，存储量小，对初始点的选择要求低；2）在远离函数极小点的地方，函数值下降较快。

但是，由于所谓的最速下降方向函数在某点的负剃度方是，由于所谓的最速下降方向－函数在某点的负剃度方向，仅是对该点而言，一旦离开了这点，其方向就不再是最速方向了。

因而在这个优化过程中，沿某点的负剃是最速方向了因而在这个优化过程中沿某点的负剃度方向寻优，并不总是具有最速下降方向的性质。

因此，从局部看，在一点附近函数的下降是最快的，但从整体从局部看在点附近函数的下降是最快的但从整体看，函数的下降并不算快，而且越是接近极值点，收敛越慢。

越慢3）应用该方法可使目标函数在头几步下降很快，因此可以与其他无约束优化方法配合使用。

例子z目标函数f(x)=60-10x1-4x 2+x 12+x 22-x 1x 2，设初始点[00]精度001用梯度法求极小点和极小x 0=[0 0]T ，精度ε=0.01，用梯度法求极小点和极小值。

共轭梯度法

共轭梯度法
Hesteness和Stiefel于1952年为解线性方程组而提出
•基本思想:把共轭性与最速下降法相结合,利用已 知点处的梯度构造一组共轭方向,并沿着这组方 向进行搜索,求出目标函数的极小点
4.4共轭梯度法
先讨论对于二次凸函数的共轭梯度法,考虑问题
min f (x) 1 xT Ax bT x c
3, giT d (i) giT gi (蕴涵d (i) 0)
证明: 显然m1,下用归纳法(对i)证之.
当i 1时,由于d (1) g1,从而3)成立,对i 2时, 关系1)和2)成立,从而3)也成立.
4.4共轭梯度法
设对某个i<m,这些关系均成立,我们证明对于i+1
也成立.先证2),
因此
2 / 3 1 5/ 9
d (2)



1/ 1
3

1 9

2 0



5/9 1

从x(2)出发,沿方向d (2)进行搜索,求步长2,使满足 :
f
( x (1)

2d (1) )

min
0
f
(x(2)

d (2))


2 0

4.4共轭梯度法
显然, d (1)不是目标函数在x(1)处的最速下降方向.
下面,我们用FR法构造两个搜索方向.
从x(1)出发,沿方向d (1)进行搜索,求步长1,使满足 :
f
( x (1)
1d (1) )

min
0
f
( x (1)

d (1) )
得1 2 3
A正定,故x是f(x)的极小值点.

梯度法

梯度法

A1=A0+△A0 推广到一般的k+1次构造矩阵
Ak+1=Ak+△Ak
矩阵序列的 基本迭代式
△Ak称为校正矩阵
拟牛顿条件
设F（x）为一般形式n阶的目标函数，并具有连续的一、二 阶偏导。在点 处的二次泰勒近似展开
该近似二次函数的梯度是
沿g(k)方向一维搜索，
求最优步长(k)。
x(k+1)= x(k)- (k) g(k)
出口
例 8-4 用最速下降法求解下列问题
min f (x) 2x12 x22 ，
给 定 初 始 点 x(1) (1, 1)T , 1 ．
10
解 目 标 函 数 f (x) 的 梯 度 及 x(1) 处 的 最 速 下 降 方 向 为
f(xk+1)
>
阻尼牛顿法
对原始牛顿法的改进
为解决原始牛顿法的不足，加入搜索步长(k)
因此，迭代公式变为：
x (k+1) = x (k) - (k) Hk-1gk 这就是阻尼牛顿法的迭代公式，最优步长(k)也称
为阻尼因子，是沿牛顿方向一维搜索得到的最优步 长。
牛顿法算法步骤
⑴任选初始点 ，给定精度ε，置k←0 ⑵计算 点的梯度矢量及其模
(x)=
x (k)
gk+
Hkx=0
得 x (k+1) = x (k) - Hk-1gk
即牛顿法迭代公式，方向- Hk-1gk称为牛顿方向
三、原始牛顿法的特点
若用原始牛顿法求某二次目标函数的最优解，则 构造的逼近函数与原目标函数是完全相同的二次式， 其等值线完全重合，故从任一点出发，一定可以一次 达到目标函数的极小点。
二、 确k定的方确法定自学，不作要求。记住

共轭梯度法(精品文档)

共轭梯度法(精品文档)

1

g2T (g2 d1T (g2
g1) g1)

g2T g2 g1T g1
4） 一般地，在第 k 次迭代中，令
k 1
dk gk idi i0
适当选取 i ，使 dkTGdi 0 （ i 0,
, k 1），可得到
i

gkT Gdi diT Gdi

gkT (gi1 gi ) diT (gi1 gi )
§4.2 共轭梯度法
提纲
1、共轭梯度法---F-R共轭梯度法 2、共轭梯度法性质定理及例题 3、再开始FR共轭梯度法 4、Beale三项共轭梯度法 5、预条件共轭梯度法（了解）
共轭梯度法
在上一节中讨论了共轭方向法，其中n个共轭方向是预先设定好的。但是如何 让获取这些共轭方向并为提及。本节讨论一种重要的共轭方向法——共轭梯 度法。这种方法是将共轭性和最速下降方向相结合，利用已知迭代点处的梯 度方向构造一组共轭方向，并沿此方向进行搜索，求出函数的极小点。因在 迭代过程中通过对负梯度方向进行适当校正获得共轭方向，故而称之为共轭 梯度法。
算法步骤—FR共轭梯度法
1、选取初始数据，选取初始点 x0 ，给定允许误差 0 ；
2、检查是否满足终止准则，计算 f (x0 ) ，若 || f (x0 ) || ,迭代终
止，x0为近似最优解，否则转向3；
3、 构造初始搜索方向，计算 d0 f (x0 ), k 0；
而
k 1

gkT (gk gk1)
dT k 1
(
gk

gk 1 )

gkT gk gkT1 gk 1
共轭梯度法的迭代公式为：

4.4共轭方向法4.5 共轭梯度法

4.4共轭方向法4.5 共轭梯度法

序框图如下图所示。
开始
给定 X 0、d0、
k0
X (k 1) X k ak d k ak : min f ( X k ak d k )
k k+1
YES Xk X（k+1）
结束
NO
f (X k1) ＜
提供新的共轭方向
共轭方向 + 精确一维搜索 = 二次终结 设 Z1 ，Z2 ，……Zm 关于正定矩阵A共轭。则从任意初 始点出发 二次型目标函数
2 0
2 9
,
2 T 3
X
2
X1
1d1
2
3
0
2
1
9 2
3
2 3
2 9
1
2 3
1
将 X 2 代入原方程，将 n 维问题化成一维问题。
令 将
(1) 1 代入
0 X2
，解得 1
式得
3 2
。
X
2
2 3
2 9
1
2 3
1
1 1
计算 X 2 点的梯度
g2
f
(
X
2
)
4 0
(0 )
(0 ) 120 4
令 (0 ) 0 ，解得
0
1 3
将
0
1 3
代入
X1
式得
X
1
20
0
2
3
0
将 X 1 代入求梯度公式
g1
f
(
X
1)
3x1 2
x2
x1
x2
x1
2 3
x2 0
0
2
3
0
g1 g0

最优化方法第三章(2).

设 Q 是 n n 对称正定矩阵。若 n 维向量 空间中的非零向量 p0 , p1 , , pm1 满足 piT Qp j 0, i, j 0,1, , m 1(i j) （3.43） 则称 p0 , p1 , , pm1是 Q 共轭向量或称向量 p0 , p1 , , pm1 是 Q共轭的（简称共轭），称 p0 , p1 , , pm1 的方向是 Q 共轭 方向。 当 Q 1（单位矩阵）时，（3.43）为 定义3.3
*
f x * Qx * b 0
f x1 t1Qp1 0 T 上式两边同时左乘 p0 ，并注意到 p0T f x1 0和 t1 0,
便得到
将（3.38）代入此式，并由（3.39）可得
p Qp1 0
T 0
（3.40）
* p p1 所必须满足的条件。 这就是为使 1 直指极小点 x ， 满足（3.40）的两个向量 p0 和 p1 称为 Q 共轭向量， 或称 p0和 p1 的方向是 Q 共轭方向。 利用（3.40）可以给出 p1 的表达式。设 p1 f x1 a0 p0 , （3.41）
n x R 其中 0 是任意选定的初始点，则
T p ⅰ） j f xm 0, 0 j m ；
（3.44）
ⅱ） xm是二次函数（3.36）在线性流形L x0 ; p0 , p1, , pm1 上的极小点。
T 证 ⅰ）根据（1.46），直接有 pm 1f xm 0 。以下 证明：对于 j 0,1, , m 2 ，（3.44）也成立。 由条件（3），有
p f ( x （其中 , , , 是任意实 数）都与 i i m ) 正交。 0 1 m1
i 0 m 1

共轭梯度法详细解读

共轭梯度法详细解读
嘿，朋友们！今天咱就来好好唠唠共轭梯度法。

你想想啊，咱平常解决问题就像走迷宫似的，有时候会在里面转来转去找不到出路，而共轭梯度法呀，就像是在迷宫里给咱指了一条明路！比如说你想找一条最快从山这头到那头的路，共轭梯度法就能帮上大忙啦！
它可不是随随便便就出现的哦，那可是数学家们绞尽脑汁研究出来的宝贝呢！就好比一个超级英雄，专门来打救我们这些在复杂问题里苦苦挣扎的人。

在实际应用里，它可厉害着呢！比如说在工程计算中，要设计一个最完美的结构，共轭梯度法就能迅速算出最优解。

哇塞，这不就相当于有个超厉害的军师在帮咱出谋划策嘛！
你再想想，我们日常生活中很多事情都可以类比成用共轭梯度法来解决问题呀。

比如说你要规划一次旅行，怎么安排路线最合理，不就是在找那个最优的旅行路径嘛，这时候共轭梯度法的思路就能派上用场啦！它就像一个隐藏在幕后的高手，默默地为我们排忧解难。

而且哦，一旦你掌握了它，那种感觉就像是你突然掌握了一种绝世武功，能在各种难题面前游刃有余。

这可太酷了吧！
哎呀呀，共轭梯度法真的是太神奇、太有用啦！大家可一定要好好去了
解它、运用它呀，你绝对会被它的魅力折服的！相信我，没错的！。

共轭梯度法总结

共轭梯度法总结
共轭梯度法总结
一、什么是共轭梯度法
共轭梯度法（Conjugate Gradient Method），是一种用于求解线性方程组的迭代优化算法，它是一种搜索梯度的迭代算法。

共轭梯度法的基本思想是沿梯度的反方向搜索，并在每一步令搜索的方向接近更新的局部梯度。

它是一种非常有效的求解有约束的非线性优化问题的方法，是求解线性方程组的有效算法。

共轭梯度法可以看作是一种极小化函数的迭代方法，它最主要的思想是不断更新梯度的方向，从而寻找函数值最小的点。

二、共轭梯度法的原理
共轭梯度法是一种迭代优化算法，它以凸二次型函数为例，可以用来求解最小值问题。

它的基本思想是：
（1）首先求得函数的梯度，即每一步优化的搜索方向，使梯度变为最小；
（2）以梯度的反方向搜索，令搜索的方向接近更新的局部梯度，而不是与旧的梯度成正比的步长；
（3）逐步更新搜索的方向为新的梯度；
（4）重复这个过程，直到所有的自变量满足限制条件。

三、共轭梯度法的优缺点
共轭梯度法最大的优点是它具有收敛速度快，可以在有限的迭代步数内收敛到最优解；另外，它还具有计算量小，不需要计算精确的
Hessian矩阵的优点。

共轭梯度法的缺点是它不能用来求解非凸优化问题，因为它只能求解凸优化问题；另外，它也不能用于强不可约的优化问题。

共轭梯度法


3. 算法的 MATLAB 实现
在 MATLAB 中编程实现的共轭梯度法函数为： min GETD 功能：用共轭梯度法求解多维函数的极值。
调用格式： [ x, min f ] min GETD( f , x0, var, eps) 其中， f ：目标函数；
x0 ：初始点； ：自变量向量； var x ：目标函数取最小值时的自变量值；
（6） 若 k 1 n ，令 x(0) x( n ) ，转步骤（3） ，否则转步骤（7） ；
（7） 令 p
( k 1)
f ( x
( k 1)
) k p
(k )
， k
f ( x ( k 1) ) f ( x )
(k )
2 2
， 置 k k 1， 转步骤 （4） 。
t 0
(k ) ( k ) （4） 用 一 维 搜 索 法 求 t k ， 使 得 f ( x kt p ) m i n f
( ) 5； x( k 1 ) x k( ) kt p k，转步骤

k( ) x
) 令， tk p( ，
（5） 若 f ( x
( k 1)
) ，停止，极小值点为 x ( k 1) ，否则转步骤（6） ；
1 f ( X ) d1 + x1 -x1* 2 1 =d1 + x1 -x1* 2


2





*
2
1 d1 a x1 -x1* 2

2b x1 -x1*

x -x c x -x


2
2b x1 -x1*
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

求迭代一次后的迭代点 x 2 。
解： f ( x ) ( 2 x1 , 6 x 2 )T ,
d 1 f ( x 1 ) ( 4 , 6 )T . x 1 d 1 ( 2 4 , 1 6 )T . 令 ( ) f ( x 1 d 1 ) ( 2 4 ) 2 3 ( 1 6 ) 2 ，

则有 f ( x k k d k )T d k 0 。
令 ( ) f ( x k d k )， 所以 证明：
( ) f ( x k d k )T d k .
f ( x k k d k ) min f ( x k d k )
椭球面。
x2 x3

x*
x1
注
最速下降方向反映了目 标函数的一种局部性质 。 它只是
局部目标函数值下降最快的方向。
最速下降法是线性收敛的算法。
三. 共轭梯度法
1. 共轭方向和共轭方向法
Rn中的两个非零向量d 1 和 d 2， 定义 设 A 是 n n 的对称正定矩阵，对于
若有 d
1T
Ad 2 0 ，则称 d 1和d 2关于A共轭。
最速下降法（梯度法）：
1. 搜索方向： d k f ( x k ) , 也称为最速下降方向；

2. 搜索步长 : k 取最优步长, 即满足 f ( x k k d k ) min f ( x k d k ) 。
最速下降法算法步骤：
1. 给定初始点 x 1 R n , 允许误差 0 , 令k 1 。 2. 计算搜索方向 d k f ( x k ) ;
k （i）如果点列 { x } 收敛于最优解 x* ，则称算法A收敛。
0 1 k （ii）如果 f ( x ) f ( x ) f ( x ) ，则称算法A为
下降迭代算法。
x1
.
x0
.
.
x2
2.下降迭代算法步骤 （1）给出初始点 x 0 ，令 k 0 ；
k
（2）按照某种规则确定下降搜索方向 d ；
1T
d2 0
d1 d 2
共轭是正交的推广。
d 1 , d 2 ,, d k 是 k 个 A 共轭的非零 定理 1. 设 A是 n阶对称正定矩阵，
向量，则这个向量组线性无关。
证明
设存在实数 1 , 2 ,, k ，使得
i 1
id 0,
T
k
i
上式两边同时左乘 d j A ，则有
求解
min ( )

令 ( ) 8 ( 2 4 ) 36( 1 6 ) 0 1
36 8 T x x 1d ( , ) 31 31
2 1 1
13 62
收敛性
步长 k 满足 性质. 设 f ( x) 有一阶连续偏导数，若
f ( x k k d k ) min f ( x k d k )
（3）按照某种规则确定搜索步长 k ，使得
f ( x k k d k ) f ( x k ) ；
k : k 1 ； （4）令 x k 1 x k k d k ，
k （5）判断 x 是否满足停止条件。是则停止，否则转第2步。
搜索步长确定方法：
f ( x k k d k ) min f ( x k d k )

( k ) f ( x k k d k )T d k 0 .
注： 因为梯度法的搜索方向 d k 1 f ( x k k d k )， 所以
(d k 1 )T d k 0 d k 1 d k 。
锯齿现象
在极小点附近，目标函数可以用二次函数近似，其等值面近似
3. 若 || d k || , 则停止计算， x k 为所求极值点； 否则，求最优步长 k
使得 f ( x k k d k ) min f ( x k d k )。

4. 令 x k 1 x k k d k , 令 k : k 1 , 转2。
2 2 例. 用最速下降法求解 : min f ( x ) x1 3 x2 , 设初始点为 x 1 ( 2 , 1 )T ,
i 1 k

k
id
jT
jT
Ad i 0 ,
因为 d 1 , d 2 , , d 是 k 个 A 共轭的向量，所以上式可化简为 0 , 而 A是正定矩阵，所以 d
所以
Ad j 0，
j 0 , j 1 , 2 , , k 。
因此 d 1 , d 2 , , d k 线性无关。
设 d 1 , d 2 ,, d k 是 Rn 中一组非零向量，如果 它们两两关于A
共轭，即 d i Ad j 0 , i j , i , j 1 , 2 ,, k 。
T
则称这组方向是关于 A共轭的，也称它们是一 组A共轭方向。
注：如果A是单位矩阵，则
d
1T
I d 0d
2
一. 无约束最优化问题
无约束最优化问题 min
f ( x) x Rn
s.t .
其中f ( x ) 有一阶连续偏导数。
解析方法：利用函数的解析性质构造迭代公式，使之收敛到最优解。
下降迭代算法的概念回顾
1.一般迭代算法
集合S上的迭代算法A：
（1）初始点 x 0 ； （2）按照某种规则A产生下一个迭代点 x k 1 A( x k ) 。

称 k 为最优步长，且有 f ( x k k d k )T d k 0 。
二. 最速下降法（梯度法） 迭代公式：
x k 1 x k k d k
如何选择下降最快的方向？
f ( x k ) 函数值增加最快的方向
xk
函数值下降的方向
f ( x k ) 函数值下降最快的方向
几何意义
1 f ( x ) ( x x )T A( x x ) 2 其中 A 是 n n 对称正定矩阵，x 是一个定点。 1 ( x x )T A( x x ) c 则函数 f ( x ) 的等值面 2