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

梯度法和共轭梯度法

  • 格式：ppt
  • 大小：1.44 MB
  • 文档页数：27

下载文档原格式

  / 27

合集下载

matlab梯度算法

matlab梯度算法

matlab梯度算法Matlab梯度算法在数学和计算机科学中，梯度是指一个多元函数在某一点上的变化率或斜率。

梯度算法是一种优化算法，用于找到函数的最小值或最大值。

在Matlab中，有多种方法可以使用梯度算法来优化函数，包括梯度下降和共轭梯度法。

本文将详细介绍Matlab中的梯度算法，并逐步讲解其原理和应用。

I. 梯度下降法梯度下降法是一种基于迭代的优化算法，通过计算函数的梯度来更新参数的值，以逐步接近函数的最小值。

在Matlab中，可以使用"gradientDescent"函数来实现梯度下降法。

1. 实现梯度下降法首先，我们需要定义一个优化目标函数，例如：f(x) = x^2 + 2x + 1。

然后，定义其梯度函数为g(x) = 2x + 2。

接下来，我们可以使用以下代码来计算梯度下降：matlab定义优化目标函数f = (x) x^2 + 2*x + 1;定义梯度函数g = (x) 2*x + 2;初始化参数x0 = 0;设置学习率和迭代次数alpha = 0.01;iterations = 100;梯度下降法for i = 1:iterationsx0 = x0 - alpha * g(x0);end打印最优解disp(['Optimal solution: ', num2str(x0)]);在这个例子中，我们使用了学习率(alpha)为0.01，迭代次数(iterations)为100。

通过不断更新参数x0的值，最终得到了最优解。

2. 梯度下降法的原理梯度下降法的核心思想是利用函数在当前点的梯度信息来更新参数的值，以便能够向着函数的最小值前进。

具体来说，算法的步骤如下：a. 初始化参数的值：选择一个初始参数的值作为起始点。

b. 计算梯度：计算函数在当前点的梯度，即求解函数关于参数的偏导数。

c. 更新参数：根据当前点的梯度和学习率，通过减去梯度的乘积来更新参数的值。

优化设计梯度法和共轭梯度法

优化设计梯度法和共轭梯度法

优化设计梯度法和共轭梯度法梯度法和共轭梯度法是常用的数值优化算法，用于求解非线性优化问题。

它们在工程领域中的应用广泛，能够有效解决很多实际问题。

本文将对优化设计梯度法和共轭梯度法进行介绍，并比较它们的优劣。

1. 优化设计梯度法优化设计梯度法是一种通过调整设计变量来最小化给定目标函数的方法。

它基于梯度下降的思想，每一步都会更新设计变量的取值，使得目标函数在设计变量的邻域内最小化。

优化设计梯度法的具体步骤如下：1）初始化设计变量；2）计算目标函数在当前设计变量取值下的梯度；3）根据梯度方向和步长因子更新设计变量；4）重复步骤2和步骤3，直到满足收敛条件。

优化设计梯度法的优点是简单易用，容易实现。

但是它也存在一些问题，比如容易陷入局部最小值，收敛速度慢等。

2. 共轭梯度法共轭梯度法是一种通过迭代算法求解线性方程组的方法，也可以用于非线性优化问题。

它的特点是每一步迭代都要寻找一个新的搜索方向，使得每一次迭代都能够有效利用之前的搜索历史。

共轭梯度法的具体步骤如下：1）初始化设计变量和搜索方向；2）计算目标函数在当前设计变量取值下的梯度；3）根据搜索方向和步长因子更新设计变量；4）计算新的搜索方向，使其与上一次的搜索方向共轭；5）重复步骤2到步骤4，直到满足收敛条件。

共轭梯度法的优点是能够在较少的迭代次数内收敛到最优解，且具有较好的数值稳定性。

然而，共轭梯度法在非精确线搜索时有一定局限性，并且对于非二次凸函数可能陷入非全局最小值。

3. 优化设计梯度法与共轭梯度法的比较在实际应用中，选择合适的优化算法对于问题的解决和效率的提高至关重要。

下面对优化设计梯度法和共轭梯度法进行比较。

（1）收敛速度：在一般情况下，共轭梯度法比优化设计梯度法收敛速度更快。

这是由于共轭梯度法在搜索方向上的选择更加优化。

（2）算法复杂度：优化设计梯度法通常较为简单，易于实现，而共轭梯度法则相对复杂一些，需要额外计算共轭方向。

（3）全局最优解：共轭梯度法在处理非二次凸函数时可能陷入局部最小值，而优化设计梯度法的表现相对较差。

共轭梯度法

共轭梯度法
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)的极小值点.

最优化问题的算法迭代格式

最优化问题的算法迭代格式

最优化问题的算法迭代格式最优化问题的算法迭代格式最优化问题是指在一定的条件下，寻找使某个目标函数取得极值（最大值或最小值）的变量取值。

解决最优化问题的方法有很多种，其中较为常见的是迭代法。

本文将介绍几种常用的最优化问题迭代算法及其格式。

一、梯度下降法梯度下降法是一种基于负梯度方向进行搜索的迭代算法，它通过不断地沿着目标函数的负梯度方向进行搜索，逐步接近极值点。

该方法具有收敛速度快、易于实现等优点，在许多应用领域中被广泛使用。

1. 算法描述对于目标函数 $f(x)$，初始点 $x_0$ 和学习率 $\alpha$，梯度下降算法可以描述为以下步骤：- 计算当前点 $x_k$ 的梯度 $\nabla f(x_k)$；- 更新当前点 $x_k$ 为 $x_{k+1}=x_k-\alpha\nabla f(x_k)$；- 如果满足停止条件，则输出结果；否则返回第 1 步。

2. 算法特点- 沿着负梯度方向进行搜索，能够快速收敛；- 学习率的选择对算法效果有重要影响；- 可能会陷入局部极小值。

二、共轭梯度法共轭梯度法是一种基于线性方程组求解的迭代算法，它通过不断地搜索与当前搜索方向共轭的新搜索方向，并在该方向上进行一维搜索，逐步接近极值点。

该方法具有收敛速度快、内存占用少等优点，在大规模问题中被广泛使用。

1. 算法描述对于目标函数 $f(x)$，初始点 $x_0$ 和初始搜索方向 $d_0$，共轭梯度算法可以描述为以下步骤：- 计算当前点 $x_k$ 的梯度 $\nabla f(x_k)$；- 如果满足停止条件，则输出结果；否则进行下一步；- 计算当前搜索方向 $d_k$；- 在当前搜索方向上进行一维搜索，得到最优步长 $\alpha_k$；- 更新当前点为 $x_{k+1}=x_k+\alpha_k d_k$；- 计算新的搜索方向 $d_{k+1}$；- 返回第 2 步。

2. 算法特点- 搜索方向与前面所有搜索方向都正交，能够快速收敛；- 需要存储和计算大量中间变量，内存占用较大；- 可以用于非线性问题的求解。

梯度法

梯度法

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定的方确法定自学，不作要求。记住

【实用】共轭梯度法反演PPT资料

【实用】共轭梯度法反演PPT资料

我们假设在点X0 处开始沿负梯度方向
蒙特卡洛方法 搜索,到达点X1 ,即
设有一组n 维彼此关于n×n 的正定对称矩阵A共轭的向量
，能够使我们分别沿着这n个共轭向量所指的方向各搜索一
非 统计方法 次,就可以达到极值点 。
为了使搜索能够快速到达极值点选取α使
模拟退火法
为了使搜索能够快速到达极值点选取α使
0 ( Ax k b )T d k 1 ( A ( xk 1 k d k ) b )T d k 1
从而，
k
rkT p k
p
T k
ApBiblioteka k(11)将上式带入 (10) 式可得：
x *
xn
x0
n 1 i0
riT p i
p
T i
Ap
i
di
(12)
*
16
三、共轭梯度法的优缺点
优 分别使用最共 速轭 下梯 降度 法法 和组 解 2 3线 6 2x性 28方 程 点 目标函 :(数 x1,x2为 )-2x13x124x1x28x26x22
性
小值，分0别 .60是 10和 ： 508.76035
P2局部极 小值
P1全局极 小值
*
20
三、共轭梯度法的优缺点
局限性
初始猜测 反演结果 目标函数值 (2,-1) (3.0，0.0) 0.6011 (-2,-1) (-3.0,0.0) 0.7606 (-1.5,0) (-0.0958,0) 0.9932 (4,-1) (3.0，0.0) 0.6011
*
17
三、共轭梯度法的优缺点
计算效率比较
最速下降法
共轭梯度法
*
18
三、共轭梯度法的优缺点

共轭梯度法

例 3.1 用共轭梯度法求解无约束非线性规划问题
2 2 min f ( x ) = x1 + 2x2 x
⎛1⎞ 给定初始点 x (0) = ⎜ ⎜1⎟ ⎟。 ⎝ ⎠
13
⎛ 2 x1 ⎞ ⎛ 2 0⎞ 2 首先， ∇f ( x ) = ⎜ ⎜ 0 4⎟ ⎟ ，以下利用(4.14)确定 β k 。 ⎜ 4x ⎟ ⎟ ，H= ∇ f ( x ) = ⎜ ⎝ ⎠ ⎝ 2⎠ k=0：
0
k +1
) 与搜索方向 s 0 ," , s k 均正交。同时，利用引理 4.1 马上
设 H ∈ R n×n 是对称正定阵，s ," , s
0
n −1
0
n −1
是非零 G—共轭方向组，x ∈ R 。 若对问题(UQP)，
0
n
从 x 出发，依次沿 s ," , s
0
进行最优一维搜索，最终得到 x ，则 x 是(UQP)的最优解。
为保证 H-共轭性，在 x 处必须取 s 为搜索方向，而不能取 α s (α > 0) 为搜索方向。
k k
k
利用定理 4.3，马上得到上述算法的有限终止性。 定理 4.4 设 H ∈ R n×n 是对称正定阵。若用凸二次规划的共轭梯度法求解 (UQP) 时产生迭代点
x1 ," , x K ，则 x K 是(UQP)的最优解，并且 K ≤ n 。
首先由(4.7)知， g = ∇f ( x ) ( j = 0, " , k -1)是 s ," , s 的线性组合，因此根据定理 4.2，
j j 0 j
( g k )T g j =0， j = 0, " , k -1
由于

(整理)16梯度法和共轭梯度法基本原理和特点.

16梯度法和共轭梯度法基本原理和特点？梯度法又称最速下降法，基本原理是在迭代点附近采用使目标函数值下降最快的负梯度方向作为搜索方向，求目标函数的极小值，特点；迭代计算简单，只需求一阶偏导数，所占的存储单元少，对初始点的要求不高，在接近极小点位置时收敛速度很慢，共轭的特点为在梯度法靠近极值点收敛速度放慢时，它可以构造共轭方向使其收敛速度加快，迭代计算比较简单，效果好，在每一步迭代过程中都要构造共轭的、方向，比较繁琐。

17迭代终止准则有哪三种？1）当设计变量在相邻两点之间的移动距离充分小时，可用相邻两点的矢量差的模作为终止的判据，2）当相邻两点目标函数值之差达到充分小时，可用两次迭代的目标函数之差作为终止判据。

3）当迭代点逼近极值点时，目标函数在该点的梯度已达到充分小时，可用梯度的模作为终止判据。

18.无约束设计法，1）powell法，它是在下降迭代过运算中只需计算和比较目标函数值的大小，不需计算偏导数的方法，是较好的一种直接搜索算法。

2）梯度法，又称最速下降法，它是采用使目标函数值下降最快的负梯度方向作为搜索方向来求目标函数的极小值。

3）共轭梯度法，又称FR法，是利用目标函数的梯度确定共轭方向，使得计算简便而效果好，只需利用相邻两点的梯度就可以构造一个共轭方向，这种方式产生共轭方向并进行迭代的算法称为共轭梯度法。

4）变尺度法，又称DFP法，为了得到既有快速收敛的性质，又能避免计算二阶导数矩阵及逆矩阵，减少计算工作量。

迭代公式X=X+aS,19有约束设计法？1）复合形法，在可行域中选取k个设计点作为初始复合形的顶点，然后比较复合形个各项目标函数值的大小，其中目标函数值最大的点为坏点，以坏点之外其余各点的中心为映射中心，寻坏点的映射点，以映射点替换坏点，并与原复合型除坏点之外其余各点构成就k 顶点的新的复合型，这样反复迭代直到达到精度找到最优点，2）简约梯度法，用来解决线性约束非线性规划问题。

3）罚函数法，是把一个有约束的问题转化为一系列无约束的问题求解，逐渐逼近最优值。

最优控制的计算方法

(2) 的第K步估计值 和给定的 合在一起，从 积分正则方程，求出 ，抽出n个要求的分量的终值 ，若 ，停止计算，否则进行下一步。
可得
3、将 代入协态方程，且由边界条件 从t=1倒向积分可得 这里选步长因子 。如此继续下去，直至指标函数随迭代变化很小为止。 由 ，得
图b 最优状态的求解
图a 用梯度法寻找最优控制 右图表示了控制和状态的初始值和第一次迭代值，可以看到第一次迭代 就几乎收敛到最优值， 与最优值还有差异，而且一般说来愈接近最优值收敛愈慢。
K=1时时，控制量为
所以，这个例子只要两步迭代即可得到最优解。一般说来，共轭梯度法比梯度法收敛快，但接近最优解后收敛性仍是较慢的。一个补救办法是重新启动，即找出几个共轭梯度方向 后，令 ，再重新迭代，寻找共轭梯度方向。
可以证明 ，即为最优控制。这只要证明
2、共轭梯度法
*
用共轭梯度法寻找最优控制时是沿着所谓共轭梯度向量的方向进行的。为了说明共轭梯度的意义，我们先从求函数极值问题的共轭梯度法开始，再推广到求泛函极值问题。
(1) 求函数极值的共轭梯度法
其中，
C为常数， Q为正定阵。
要求寻找X使F(X)取极值。
设F(X)是定义在Rn空间中的二次指标函数
直接法的特点是，在每一步迭代中，U(t)不一定要满足H 取极小的必要条件，而是逐步改善它，在迭代终了使它满足这个必要条件，而且，积分状态方程是从t0到tf ，积分协态方程是从tf到t0，这样就避免了去寻找缺少的协态初值(t0)的困难。常用的直接法有梯度法，二阶梯度法，共轭梯度法。
间接法的特点是，在每一步迭代中都要满足H取极小的必要条件，而且要同时积分状态方程和协态方程，两种方程的积分都从从t0到tf或从tf到t0 。常用的间接法有边界迭代法和拟线性化法。

第9讲梯度法和共轭梯度法


{ x( ) }
k
A−a 收敛于 x , 则目标函数值的序列 f ( x( k ) ) 以不大于 A+ a
{
}
2
的收敛比线性的收敛于 f ( x ) . 若令 r = A / a ,则
A − a r −1 = < 1. A + a r +1
i =1 k
生成的子空间。 x 是由 d (1) , d ( 2 ) ,⋯ , d ( k ) 生成的子空间。特别地 ， k = n时， ( n +1)是 当 f ( x )在 R n 上的唯一极小点。 上的唯一极小点。
推论
在上述定理条件下， 在上述定理条件下，必 有
∇f ( x ( k +1) )T d ( i ) = 0 , i = 1 , 2 ,⋯ , k 。
( 2) 设已求得点 x ( k +1) ， ∇f ( x ( k +1) ) ≠ 0 ， g k +1 = ∇f ( x ( k +1) ) ， 若 令 则下一个搜索方向 d ( k +1)按如下方式确定 : 令 d ( k + 1) = − g k + 1 + β k d ( k ) (1)
如何确定 β k？
证明
设存在实数 α 1 , α 2 ,⋯ , α k ，使得
i =1
∑ αid = 0,
i
k
上式两边同时左乘d jT A ，则有
i =1 k
∑ αid
k
jT
Ad i = 0 ,
共轭的向量， 因为 d 1 , d 2 ,⋯ , d 是 k 个 A 共轭的向量，所以上式 可化简为
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

如何选择下降最快的方向？
f ( x k ) 函数值增加最快的方向
xk
函数值下降的方向
f ( x k ) 函数值下降最快的方向
梯度法（最速下降法）：
1. 搜索方向： k f ( x k ) , 也称为最速下降方向； d

2. 搜索步长 : k 取最优步长, 即满足 f ( x k k d k ) min f ( x k d k ) 。

则有 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 )

(k ) f ( x k k d k )T d k 0 .
则下一个搜索方向 d ( k 1)按如下方式确定:
令 d ( k 1) g k 1 k d ( k ) (1)
如何确定 k？
要求 d ( k 1) 和 d ( k ) 关于 A共轭。
则在（ ）式两边同时左乘 d 1
0d
( k )T
( k )T
A ，得
A d (k )
Ad
注： 因为梯度法的搜索方向 k 1 f ( x k k d k )， d 所以
(d k 1 )T d k 0 d k 1 d k 。
锯齿现象
在极小点附近，目标函 数可以用二次函数近似 ，其等值面近似
椭球面。
x2 x3

x*
x1
注
最速下降方向反映了目 标函数的一种局部性质 它只是 。
(1) d
( i )T
Ad ( j ) 0 , j 1 , 2 ,, i 1;
( 2) g i T g j 0 , j 1 , 2 , , i 1 ;
( 3) giT d ( i ) giT g i 。
注 （1）由定理3 可知搜索方向d (1) , d ( 2) ,, d ( m) 是 A 共轭的。
d (1) 是 R n中的一个方向，
x ( 0) 沿着d (1) 以最优步长 搜索得到点 x (1) 。
o
x
x (0)
d ( 1)
d
( 2)
x (1) x1
则 d ( 1 )是点 x ( 1 )所在等值面的切向量。
该等值面在点 x ( 1 ) 处的法向量为f ( x 1 )
f ( x (1) ) A( x (1) x ) . 则 d (1) 与 f ( x (1) ) 正交， 即 d
局部目标函数值下降最 快的方向。 最速下降法是线性收敛 的算法。
三、共轭方向法
1. 何谓共轭方向？
几何解释
1 f ( x ) ( x x )T A( x x ) 设有二次函数 2
其中 A 是 n n 对称正定矩阵，
x 是一个定点。
则函数 f ( x ) 的等值面
1 ( x x )T A( x x ) c 2
x
是以 x 为中心的椭球面。
由于 f ( x ) A( x x ) 0 , 而
1 f ( x ) ( x x )T A( x x ) 2
2 f ( x ) A,
x
因为A 正定， 所以 2 f ( x ) A 0 ,
因此 x 是 f ( x ) 的极小点。
设 x ( 0) 是在某个等值面上的一点，
(2) 算法中第一个搜索方向 必须取负梯度方向，否 则构造的搜索 方向不能保证共轭性。
T (i ) T 2 (3) 由定理3的（3）可知， g i d g i g i || g i || 0 ,
所以 d ( i )是迭代点 x ( i ) 处的下降方向。
(4) 由定理3 ， 算法中 i的计算公式可以简化。 FR

令 ( ) 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 )
n 次迭代必可得到最优解 。
如何选取一组共轭方向？
四. 共轭梯度法 ：
二次函数情形 非二次函数情形
1、 二次函数情形
Fletcher R eeves 共轭梯度法:
1 T x Ax bT x c 2 其中 x R n , A是对称正定矩阵， R n， 是常数。 b c min f ( x)
(1)T
( 2)
d ( 1)
x
f ( x
(1)
) 0。
d
1
( 2)
x (1) x1
o f ( x )源自令 d所以 x x ,
(1)
d (1)T Ad ( 2) 0 。
即等值面上一点处的切 向量与由这一点 指向极 小点的向量关于 A 共轭。
2. 共轭方向
定义 设 A 是 n n 的对称正定矩阵，对于 Rn中的两个非零向量 d 1 和 d 2，
min

f ( x ( k ) d ( k ) ) 。
( ) f ( x ( k ) d ( k ) ) ,
( ) f ( x ( k ) d ( k ) )T d ( k ) 0，
[ A ( x ( k ) d ( k ) ) b ]T d ( k ) 0，
x ( k 1 ) x ( k ) k d ( k ) f ( x ( k ) d ( k ) ) min f ( x ( k ) d ( k ) ) k
直到某个 x ( k ) 满足 f ( x ( k ) ) 0。
注 由定理2可知，利用共轭方向法 求解上述极小化问题， 至多经过
( k 1)
d
( k )T
Ag k 1 k d
( k )T
解得 k
d ( k ) A g k 1 d
( k )T
T
Ad
(k )
( 2)
(3) 搜索步长的确定 :
已知迭代点 x ( k )和搜索方向d ( k ) , 利用一维搜索确定最优步长 k ，
即求解
记 令 即有
i 1

k
id i 0,
jT
上式两边同时左乘 d
i 1 k
A ，则有

k
id
jT
jT
Ad i 0 ,
因为 d 1 , d 2 ,, d 是 k 个 A 共轭的向量，所以上式可化简为
jd
j
Ad j 0 .
jT
因为 d 0 , 而 A是正定矩阵，所以d
所以
Ad j 0，
j 0 , j 1 , 2 , , k 。
注：如果A是单位矩阵，则
d
1T
I d 0 d
2
1T
d2 0
d1 d 2
共轭是正交的推广。
d 定理 1. 设 A是 n阶对称正定矩阵， 1 , d 2 ,, d k 是 k 个 A 共轭的非零
向量，则这个向量组线 性无关。
证明
设存在实数 1 , 2 ,, k ，使得
T
g i f ( x ( i ) ) A x ( i ) b .
i g i 1T ( g i 1 g i ) d
( i )T
( g i 1 g i )

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 ，
求解 min ( )

4. 令 x k 1 x k k d k , 令 k : k 1 , 转2。
2 2 例. 用最速下降法求解 : min f ( x ) x1 3 x2 , 设初始点为 x1 ( 2 ,1 )T ,
求迭代一次后的迭代点 x 2 。
解： f ( x ) ( 2 x1 , 6 x2 )T ,
得到点 x ( 2) , x ( 3) ,, x ( k 1) , 则 x ( k 1) 是函数 f ( x )在 x (1) Bk 上的
极小点，其中
Bk { x | x i d ( i ) , i R }
i 1
k
是由 d (1) , d ( 2) ,, d ( k ) 生成的子空间。特别地， k n时， ( n1)是 当 x f ( x )在R n上的唯一极小点。
基本思想： 将共轭性和最速下降方 向相结合，利用已知迭 代点
处的梯度方向构造一组 共轭方向，并沿此方向 进行搜索，求出
函数的极小点。
以下分析算法的具体步骤。
(1) 任取初始点 x (1)，第一个搜索方向取为 d (1) f ( x (1) ) ；
( 2) 设已求得点 x ( k 1) ， f ( x ( k 1) ) 0 ， g k 1 f ( x ( k 1) ) ， 若 令
梯度法算法步骤：
1. 给定初始点 x 1 R n , 允许误差 0 , 令k 1 。 2. 计算搜索方向 d k f ( x k ) ;
3. 若|| d k || , 则停止计算， k 为所求极值点； x 否则，求最优步长 k
使得 f ( x k k d k ) min f ( x k d k )。
因此 d 1 , d 2 ,, d k 线性无关。