最速下降法

f x1 , x2 c, c>0,
2
改写为：
x12 2c 1

2 x2

2c 2
2
1
二、最速下降法
x2
这是以
2c
1
和
2c
2
为半轴的椭圆
2c
2c
2
2
从下面的分析可见 两个特征值的相对
x1
大小决定最速下降法的收敛性。
（1）当 1 2 时，等值线变为圆
2 2
4 f x , 2
2 x1 2 x2 4 f ( x) , 2 x1 +4x2
4 d = f x , 2
0 0
=40 2 20 3 令 0= ' ( ) 80 20, 得 0 =1/4,
一
一维搜索
二 三 四
下 降 算 法
五
最速下降法 Newton法 共轭梯度法
多尺度法 （拟Newton法）
二、最速下降法 假设 f 连续可微，取 线搜索方向
k
d f ( x )
k
步长k 由精确一维搜索得到。 从而得到第 k+1次迭代点，即
f ( x k k d k ) min f ( x k d k )


(推论)在收敛定理的假设下，若f (x)为凸函数，则最速下降 法或在有限迭代步后达到最小点；或得到点列 x k ，它的任 何聚点都是 f (x)的全局最小点。
二、最速下降法

最速下降法特征：相邻两次迭代的方向互相垂直。
令
( ) f ( x d ), 利用精确一维搜索，可得

最速下降法姓名：沈东东 班级：研1404 学号：1415033005一、最速下降法的原理目标函数:(1)n f R R n →>在决策变量的当前点()k n x R ∈处的一阶Taylor 展开式为()()()()()()()k k k T f x f x g x δδοδ+=++式中，()()k n g x R ∈为f 在点()k x 处的梯度向量。

当扰动量n R δ∈充分小时，有()()()()()()k k k T f x f x g x δδ+≈+设新的迭代点为(1)()k k x x δ+=+，于是得到(1)()()()()()k k k T f x f x g x δ+-≈为了使(1)k x +处的目标函数值比()k x 处有所下降，需要满足()()0k T g x δ<此外，梯度向量()()k g x 和扰动量δ的内积可以表示为()()()()cos k T k g x g x δδθ=式中，θ为两向量之间的夹角。

若要使目标函数值的下降量尽可能大，可知δ的方向应该为梯度方向的负方向，即cos 1θ=-。

函数f 在点()k x 处的负梯度方向称为该点的最速下降方向。

在每次迭代时都取最速下降方向作为搜索方向的方法就称为最速下降法。

二、最速下降法的特点1.若()k x 不是极小点，则f 在点()k x 处的最速下降方向总是下降方向。

2.如果每次迭代时都用精确搜索方法得到最佳步长作为搜索步长，则寻优过程中相邻的最速下降方向是正交的。

3最速下降法产生的迭代点序列在一定条件下是线性收敛的，其收敛性质与极小点*x 处的Hesse 矩阵有关。

三、最速下降法的计算步骤最速下降法的计算步骤如下：步骤1：已知待求问题的目标函数()f x ，选择初始点(0)x ，并设定精度要求tol ，令:0k =。

步骤2：计算()f x 在点()k x 处的梯度向量()()k g x ，得到最速下降方向()()()k k d g x =-。

梯度法（又名,最速下降法）(该法总可以收敛，但是，在接近真解时收敛的速度会放慢。

) 梯度法又称为最速下降法，用于求解实系数非线性方程组12(,,,)0,1,2,,i n f x x x i n== （7－15）的一组根。

梯度法首先是定义一个目标函数212121(,,,)(,,,)nn i n i x x x f x x x =Φ=∑（7－16）使目标函数21nii f =Φ=∑达到最小的12,,,n x x x 是我们寻找的一组解，这是非线性最小二乘法问题。

如果第(0,1,2,)k k = 步求得一组解12,,,nk k k x x x ，使得12(,,,)n k k kx x x εΦ< （7－17）则认为12,,,nk k k x x x 是原方程组满足一定精度的()ε要求的一组解。

梯度法的计算过程是：（1）先给定一组不全为零的初值12000,,,nx x x ，第k 步的一组根为12,,,nk k kx x x ；（2）计算目标函数12(,,,)nk k k x x x Φ 的值；(单独子程序:fn =TargetFunction)（3）若12(,,,)nk k k x x x εΦ< ，则认为12,,,nk k k x x x 是满足一定精度()ε的一组解，否则，作如下修正计算1α+=∂Φ=-∂iki ik k ki ix x x x x （7－18）其中121212*********1111222(,,,)(,,,)(,,,)(,,,)(,,,)(,,,)(,,,)*,1,2,,α==⎫Φ=⎪⎛⎫⎪∂Φ ⎪ ⎪∂⎝⎭Φ+-Φ∂Φ=∂⎬Φ+-Φ∂Φ=∂Φ+-Φ∂Φ=∂==∑ n kj jn n n n n n k k kkn j j x x k k k k k kk k k k k k k k k k k kn n nki i x x x x x h x x x x x x h x x h x x x x x h x x x h x x x x h h H x i n ⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎭（7－19）H 为控制收敛的常数，通常选为（10－5～10－6），收敛精度ε选为（10－6～10－8）。

随着人工智能、模糊控制、模式识别、人工网络等新技术的应用和发展。

可以让它们与广义预测控制相结合，建立高精度、多模态的预测模型。

使广义预测控制在异常情况下可以稳定运行，推进广义预测控制的进一步发展。

2.2.1最速下降法最速下降法是无约束最优化中是比较有效的方法，它是以d}=一可(x})作为下降方向的算法。

其迭代格式为xx+i=xx一。

*Of (xk)上式中，一般通过精确线搜索准则求得步长因子。

*，当然也不排除可以利用非精确线搜索准则来求得步长因子。

*。

不管最速下降法采取何种线搜索准则，它均具有全局收敛性，但是这也不能直接就认为最速下降算法就是一个良好的优化算法。

在实际试验中，有很多优化问题利用最速下降法并不是下降的特快，反而下将的十分缓慢。

这是因为出现了锯齿现象:就是在计算过程中，最速下降法开始几步还是挺快的，但是当目标函数f (x)的等高线接近于一个球的时候，就出现了类似锯齿现象，前进十分缓慢，降低了算法的效能。

2.2.12.2.2牛顿法牛顿法也是无约束最优化问题中的一种经典算法，它是利用目标函数.f (x)的二次泰勒展开式，并将二次泰勒展开式进行极小化。

其迭代格式为x}+}=xA十d}(2-5)其中步长因子。

、=l} d、为02f (x} )d + Of (xA ) = 0的解。

当目标函数f(x)是正定二次函数的时候，牛顿法可以一步达到最优解;当目标函数f (x)是非二次函数的时候，牛顿法经过有限次迭代之后就不能确保求得目标函数f (x)的最优解。

我们知道目标函数f (x)在极小点附近是很接近于二次函数的，所以，假如初始点非常靠近无约束最优化问题((1-1)的最优解x的时候，并且}Z.f (x.)正定的时候，那么牛顿法就会有很快的收敛速度，而由此算法产生的点列也具有了超线性收敛速度，同时还在一定条件下具有二次收敛性;假如初始点与无约束最优化问题(1-1)的最优解x’相距比较远的时候，这时的}Z.}(x})就不一定是正定的了，也就存在了一个问题，那就是此时的牛顿方向就不一定是下降方向，有可能是上升方向，此时由此算法产生的点列可能也就不收敛于无约束最优化问题((1-1)的最优解了。

一、最速下降法基本原理(一)无约束问题的最优性条件无约束问题的最优解所要满足的必要条件和充分条件是我们设计算法的依据，为此我们有以下几个定理。

定理1 设f :1n R R →在点nx R ∈处可微。

若存在n p R ∈，使()0T f x p ∇<则向量p 是f 在点x 处的下降方向。

定理2 设1:nf R R →在点n x R *∈处可微。

若x *是无约束问题的局部最优解，则()0f x *∇=由数学分析中我们已经知道，使()0f x ∇=的点x 为函数f 的驻点或平稳点。

函数f 的一个驻点可以是极小点；也可以是极大点；甚至也可能既不是极小点也不是极大点，此时称它为函数f 的鞍点。

以上定理告诉我们，x *是无约束问题的的局部最优解的必要条件是：x *是其目标函数f 的驻点。

现给出无约束问题局部最优解的充分条件。

定理3 设1:nf R R →在点nx R *∈处的Hesse 矩阵2()f x *∇存在。

若()0f x *∇=，并且2()f x *∇正定则x *是无约束问题的严格局部最优解。

一般而言，无约束问题的目标函数的驻点不一定是无约束问题的最优解。

但对于其目标函数是凸函数的无约束凸规划，下面定理证明了，它的目标函数的驻点就是它的整体最优解。

定理4 设1:nf R R →，n x R *∈，f 是nR 上的可微凸函数。

若有()0f x *∇=则x *是无约束问题的整体最优解。

(二)最速下降法的基本思想和迭代步骤最速下降法又称为梯度法，是1847年由著名数学家Cauchy 给出的。

他是解析法中最古老的一种，其他解析方法或是它的变形，或是受它的启发而得到的，因此它是最优化方法的基础。

设无约束问题中的目标函数1:nf R R →一阶连续可微。

最速下降法的基本思想是：从当前点k x 出发，取函数()f x 在点kx 处下降最快的方向作为我们的搜索方向kp .由()f x 的Taylor 展式知()()()(k k k k T k k f x f x tp t f x p o tp -+=-∇+‖‖)略去t 的高阶无穷小项不计，可见取kp =()kf x -∇时，函数值下降得最多。

s.t. 0
计算步骤
设f (X )是可微函数，精度要求为
X f ( ) K 1
，
X 0 为初始点。
(1)计算梯度
f
(
X
)
k
，初始k=0；
(2)
Pk

f
(
X
)
k
(3)求解 k
min f ( X k Pk)
s.t. 0
设 k 是一维搜索的最优解；
(4)求下一个点
评价
由例题中可以发现两次迭代的搜索方向满足：
P P P P T 0, T 0,...,
01
12
即相邻两个搜索方向 PK 与 PK1 正交，这是最速下降
法的搜索方向的基本形质。因此，最速下降法的迭代
路线呈锯齿形，尤其是在极小点附近，锯齿现象尤为
严重，从而影响了迭代速度。
评价
锯齿现象
最优化技术
第三章 7节 最速下降法
主要内容
1原 理
2 计算步骤
3 例题分析 4评 价
原理
定义：用来求解无约束多元函数 min f（x）
极小化问题的一种迭代算法。
拓展：
最速下降法又称梯度法，是 1847 年由著名数学家
Cauchy 给出的，它是解析法中最古老的一种，其他解析 方法或是它的变形，或是受它的启发而得到的，因此它是 最优化方法的基础。
X
)
0

(1,1)T
3-最优步长
2
X P ( ) f 5
0
0 2
1
0
应用一维搜索技术，解得函数最小值点 0 =0.2
举例分析
4-下一搜索点
X1

最速下降法的基本思路最速下降法是一种求解无约束优化问题的迭代算法，其基本思路是从当前点出发，沿着当前点到最优解的方向进行移动，并以一定的步长进行迭代更新，直到达到最优解或者满足一定的停止准则。

本文将从以下几个方面详细介绍最速下降法的基本思路。

一、最速下降法的数学模型在介绍最速下降法的基本思路之前，我们先来看看最速下降法所要求解的数学模型。

对于一个无约束优化问题：min f(x)，x∈R^n其中f(x)为目标函数，x为自变量向量。

我们希望求出目标函数的全局最小值或局部最小值。

二、梯度和梯度方向在介绍最速下降法的基本思路之前，我们需要先了解两个概念：梯度和梯度方向。

1、梯度对于一个可微函数f(x)，在点x处，它的梯度定义为：grad f(x)=[∂f/∂x1, ∂f/∂x2, …, ∂f/∂xn]T其中T表示矩阵转置。

梯度是一个向量，它指向函数在该点上升最快的方向，其模长表示该方向上函数增加的速率。

2、梯度方向对于一个可微函数f(x)，在点x处，它的梯度方向定义为：-df/dx=-(∂f/∂x1, ∂f/∂x2, …, ∂f/∂xn)T梯度方向是一个向量，它指向函数在该点下降最快的方向，其模长表示该方向上函数减少的速率。

三、最速下降法的基本思路有了梯度和梯度方向的概念之后，我们就可以来介绍最速下降法的基本思路了。

最速下降法是一种基于负梯度方向进行迭代更新的优化算法。

具体来说，它的基本思路可以分为以下几个步骤：1、初始化首先需要选择一个初始点x0作为起始点。

2、计算负梯度在当前点xk处计算目标函数f(x)的负梯度-df/dx，并将其作为移动方向。

3、确定步长确定一个合适的步长αk，使得目标函数沿着移动方向能够有足够大的下降。

4、迭代更新根据当前点和移动方向以及步长进行迭代更新：xk+1 = xk + αk*(-df/dx)5、停止准则判断是否满足停止准则，如果满足，则停止迭代；否则返回步骤2。

四、最速下降法的收敛性最速下降法是一种保证收敛的优化算法，但是其收敛速度较慢。

（4）f
(
X
)
3

(0.04,0.04)T
,
f ( X 3) 2 0.0032 0.01
X 3 已达到预定精度要求，迭代终止。
故f（x）的无约束近似极小点为
X X 3 (0.96,1.44)T
注：原问题的精确极小点为
X (1,1.5)T
3. 最速下降法性质与评价
x1 x1

2 2
x2 x2
1 1
（1） X 0 (1,1)T
,
f
(
X
)
0

(1,1)T
,
P0

f
(
X
)
0

(1,1)T
X P (t ) f( 0 t
)
0

5t 2

2t
1
,t>0
ቤተ መጻሕፍቲ ባይዱ
应用一维搜索技术，可解得 (t) 的极小点为t0=0.2
所以 X 1 X 0 t0 P0 (1,1)T 0.2(1,1)T (0.8,1.2)T
X X P
Y f (X ) N 输出X
停止
例3.18 用最速下降法求解无约束优化问题：
x x x x x x min f (X ) 2 2 2
2
1
12
2
1
2
初始点 X 0 (1,1)T
,迭代终止准则为
f
(X k)
2
0.01
。
解：
f
(
X
)

4 2
1. 最速下降法原理 2. 最速下降法算法 3. 最速下降法性质与评价

定理 3.1.1 设假设 2.4.1的条件成立 , 那么采用精确搜索 , 或 Armijo搜索或 Wolfe- P owell搜索的最速下降法产生 的迭 代序列{xk }满足 lim || f ( xk ) || 0
k
由前面的例子看到, 最速下降法的收敛速度至多是线性的, 具体 见下面的两个定理.
第一节
最速下降法
最古老的优化方法，十九世纪中叶由Cauchy提出
1、 思想 ：每次沿负梯度方向进行搜索
●
x*
xk 1
等值线(面)
●
xk
●
f ( xk )
负梯度方向也称为最速下降方向：
事实上，对任意p R n 且 || p || , 由Cauchy - Schwarz 不等式得 f ( xk ) T P - || f ( xk ) || || P || - || f ( xk ) || - f ( xk ) - f ( xk ) 当取p 时等号成立，即 p 是下列问题 || f ( xk ) || || f ( xk ) || 的解 min f ( xk ) T P
从上面的例子看到, 对于简单的二元二次函数极小化问题， 最速下降法在有限次迭代并没有求出其精确最优解, 但能 以较慢的速度无限接近最优解.
事实上，上面的例子刻画了最速下降法的所有收 敛特征
3、 最速下降法的收敛性 全局收敛性
由于最速下降法的搜索方向与负梯度方向一致, 即 k 0, 且 || f ( xk ) || || d k || 所以, 由定理2.4.1 - 2.4.3, 我们很容易得到最速下降算法的全 局收敛性.
2
max 其中 , 且max 和min分别是 f ( x * )的最大和最小特征值 . min

n

收敛性问题的基本概念 最速下降法的迭代原理 最速下降法的迭代步骤 最速下降法的举例 最速下降法的收敛结论
Байду номын сангаас
无约束问题4-4
1.收敛性问题的基本概念 定义4-9
(k )
min f ( X ) n
X R
若序列 { X }，对于 0 ，存在正整数 N ( ),
(k ) (k ) k N 时，有 X X ，即 X X 0, 当 k
2.迭代原理 min f ( X ) X R
n
1 0 0 min f ( X 0 p 0 ) f ( X 0 0 p 0 ), X X 0 p X , p f ( X ), 0 1 1 1 1 1 min f ( X 1 p1 ) f ( X 1 p ), X 2 X 1 1 p1 X , p f ( X ), 0 k 1 k k k k k min f ( X k p k ) f ( X k k p k ), X X k p X , p f ( X ), 0
X (k ) X
X ( k 1) X
X ( k 2) X
X ( k 3) X
X ( k 4) X
0.1
0.09
0.05
0.02
0.01
无约束问题4-4
1.收敛性问题的基本概念 定义4-10
若 X ( k ) X k 0,
( ) ( f ( X ) p )0 充分小时 0 结论： f ( X ( k ) )T p( k ) 0 时，p(k)是 f (X)在X(k) 处的下降方向。 当
(k ) T (k )

高等数值分析_变分原理最速下降法
变分原理最速下降法（Variable Principle Fastest Descent Method，VPFDM）是一种用来解决非线性最优化问题的一种方法，它的本
质是梯度下降法的一个变形，它的发展可以定量地描述系统状态变化的趋势，并且被广泛的应用于计算机模拟和控制系统的设计中。

VPFDM是一种非线性最优化方法，它的基本思想是通过梯度下降法来
找到将目标函数极小化或最大化的解。

它可以提高每次迭代过程中速度，
使算法更快地收敛，从而节省计算机时间。

VPFDM的工作原理是：首先在原点处定义一个初始的趋势方向梯度，
然后采用不断更新其估计值的方法，来改善趋势，使其逐渐收敛到最小值。

VPFDM主要有三个步骤：
-首先，根据初始梯度，计算出目标函数最优化的方向；
-其次，添加一个特征值，把目标函数改写成一个新的函数，它的结
构和目标函数一样，但会有一点不同的，特征值会改变我们这次更新梯度
的方向；
-最后，根据改写的新函数，计算出新的梯度估计值，并更新目标函
数的方向，从而达到最小值。

由于VPFDM比梯度下降法更快，因此它的应用范围很多，其中包括机
器学习，优化算法，智能控制，图像处理，信号处理等等。

最速下降法和共轭梯度法的区别
最速下降法和共轭梯度法都是求解无约束优化问题的迭代方法，它们的区别如下：
1. 方向选择：最速下降法每次迭代选择梯度的方向作为搜索方向，而共轭梯度法每次迭代选择一个共轭方向，不同的迭代步骤之间方向是相互垂直的。

2. 收敛速度：共轭梯度法通常比最速下降法更快地收敛到最优解。

共轭梯度法利用了问题的特殊结构，通过选择共轭方向进行迭代，可以跳过一些搜索方向，从而加快收敛速度。

3. 存储需求：最速下降法仅需要存储当前点的梯度信息，而共轭梯度法需要额外存储用于计算共轭方向的历史梯度信息，因此共轭梯度法的内存需求更高。

4. 线性搜索：最速下降法一般使用线性搜索确定每次迭代的步长，而共轭梯度法可以利用解析公式或其他更高效的非线性搜索方法来选择合适的步长。

总体来说，共轭梯度法在收敛速度和存储需求方面有优势，特别适用于求解大规模优化问题。

但最速下降法相对简单，并且对一些非二次凸函数仍然有效，因此在某些情况下也是一种有效的选择。

例 3.4.4 用 Newton 法求解问题 min f (x) 4x12＋x22－x12x2
取初始点为 xA (1,1)T , xB (3, 4)T , xC (2, 0)T 。
min f (x) 4x12＋x22－x12x2
g
(
x)
8x1－2x1 x2 2 x2－x12
G(
x)
0.1273 0.0003 0.0000
1.3388 0.0511 0.0001
xk (0,0) 严格局部极小点
g
(
x)
8x1－2x1 x2 2x2－x12
G(0,0) 8 0 0 2
G(
x)
8－2x2 －2 x1
－2x1 2
解: (2)用 Newton 法得到得迭代点如表所示：
开域内有极小点 x*，设G* G(x*)正定，则当 x0与 x*充分
接近时，对一切k ，Newton 法有定义，且当xk 为无穷 点列时，xk 二阶收敛于 x*，即hk 0且
f
( xk
)存在，所以有
fk fk1 0。 （3.8）
用反证法。假设 gk 0不成立，则0 0及无穷多个 k ，使 gk 0。对这样的k ，有
gkT pk pk 0，
于是，由 Taylor 公式
f (xk pk ) f (xk ) g(k )T pk
f
(
xk
)
g
T k
pk
g(k ) gk T
最速下降法
k=k+1
x(1), ε >0, k=1
Yes
|| ▽f(x(k) ) ||< ε?
No
d(k)= －▽f(x(k) )
stop. x(k) –解

随着人工智能、模糊控制、模式识别、人工网络等新技术的应用和发展。

可以让它们与广义预测控制相结合,建立高精度、多模态的预测模型。

使广义预测控制在异常情况下可以稳定运行,推进广义预测控制的进一步发展。

2.2.1最速下降法最速下降法是无约束最优化中是比较有效的方法,它是以d}=一可(x})作为下降方向的算法。

其迭代格式为xx+i=xx一。

*Of (xk)上式中,一般通过精确线搜索准则求得步长因子。

*,当然也不排除可以利用非精确线搜索准则来求得步长因子。

*。

不管最速下降法采取何种线搜索准则,它均具有全局收敛性,但是这也不能直接就认为最速下降算法就是一个良好的优化算法。

在实际试验中,有很多优化问题利用最速下降法并不是下降的特快,反而下将的十分缓慢。

这是因为出现了锯齿现象:就是在计算过程中,最速下降法开始几步还是挺快的,但是当目标函数f (x)的等高线接近于一个球的时候,就出现了类似锯齿现象,前进十分缓慢,降低了算法的效能。

2.2.12.2.2牛顿法牛顿法也是无约束最优化问题中的一种经典算法,它是利用目标函数.f (x)的二次泰勒展开式,并将二次泰勒展开式进行极小化。

其迭代格式为x}+}=xA十d}(2-5)其中步长因子。

、=l} d、为02f (x} )d + Of (xA ) = 0的解。

当目标函数f(x)是正定二次函数的时候,牛顿法可以一步达到最优解;当目标函数f (x)是非二次函数的时候,牛顿法经过有限次迭代之后就不能确保求得目标函数f (x)的最优解。

我们知道目标函数f (x)在极小点附近是很接近于二次函数的,所以,假如初始点非常靠近无约束最优化问题((1-1)的最优解x的时候,并且}Z.f (x.)正定的时候,那么牛顿法就会有很快的收敛速度,而由此算法产生的点列也具有了超线性收敛速度,同时还在一定条件下具有二次收敛性;假如初始点与无约束最优化问题(1-1)的最优解x’相距比较远的时候,这时的}Z.}(x})就不一定是正定的了,也就存在了一个问题,那就是此时的牛顿方向就不一定是下降方向,有可能是上升方向,此时由此算法产生的点列可能也就不收敛于无约束最优化问题((1-1)的最优解了。

最速下降方向只是局部下降最快的方向，在全局来看，下降速度是比 较慢的。尤其当目标函数等值面是很扁的椭圆、椭球或类似图形时， 收敛更慢。
例4.1 用最速下降法求函数 f (x1, x2)＝x12+4x22 的极小点，（迭代两次）， 并验证相邻两个搜索方向是正交的。初始点取为x(0)=[1,1]T 。
x1
因而由上述定理知： x1
0 0 || x1 || 0
x1
即只需迭代一步就到了极小点，这表明最速下降法用于等值线为圆的目标 函数时，从任意初始点出发，只需迭代一步就到了极小点。
（2）当 1 2 时, 等值线为椭圆。此时对于一般的初始点将产生锯齿现象。
（3）当 1 2
d kT g k d k g k
当且仅当dk=-gk时， (dk)Tgk 最小，从而-gk是最速下降方向。
最速下降法的迭代格式为：
x( k 1) x( k ) tk f ( x( k ) )
（二）算法
开始
给定x(0) , M , 1 , 2 , 令 k=0 计算f( x(k ) ) ||f( x(k ) )|| < 1 否 k>M 是 是
而采用固定步长λ的方法，称为固定步长最速下降法。只要λ充分小，总有：
f x k f xk 1 f xk f x k
f xk
但λ到底取多大，没有统一的标准， λ取小了，收敛太慢，而λ取大了， 又会漏掉极小点。——不精确线搜索解决这个问题
x1 x0 0f x0 1.919877 0.3071785 10
f ( x1 ) 3.686164.
2

T
然后再从 x1开始新的迭代，经过10次迭代，得最优解 x* (0, 0)T 计算中可 以发现，开始几次迭代，步长比较大，函数值下将降较快但当接进最优点 时，步长很小，目标函数值下降很慢。如果不取初点为 x0 (2, 2)T 而取 x0 (100,0)T 虽然后一初点较前一初点离最优点 x* (0, 0)T 远，但迭代中 不会出现上面的锯齿现象。这时：

1.给定初始点x0,置k:=0. 2.计算xk点的梯度，若梯度小于等于事先给 定的非常小的正数 ,则终止，否则，下 一步。
3.令z k f ( x k ).
4.求使f ( x k z k )最小的 , 记为k ,即最佳步长. 令x k 1 x k k z k , 转2.


d T 2 f ( x* )d r 即： 1 2 T 2 d f ( x * )d o(2 ) 1 2 o ( ) 2 r 0 2 2 2
即当小到一定程度时， f ( x d )-f ( x ) 0
* *
也即：x*是严格局部极小点。
算法迭代步骤(求出的是极小值点)
因为x 是局部极小值点，所以当 充分小时， f ( x d )－f ( x ) 0 令 0, 取极限可知，
1 T 2 d f ( x )d 0 2
即2 f ( x )半正定
充分条件如下（即局部最优解的刻画，当满足什么 条件，所得的解就是局部最优解）
定理3：若f 是连续可微的凸函数，则x 是 min f ( x) 问题 的最优解的充分必要条件是： n x E f ( x ) 0 进一步，若f ( x)是严格凸函数，则 x 是 唯一的最优解。
(k ) (k )
lim x ( k ) x *
k
局部收敛，全局收敛
收敛速度：设序列x k 收敛到x*,若
k

lim
x k 1 - x * x x*
k
存在，
(0,1), 线性收敛； 0，超线性收敛；
若存在p, 使得 lim
k
x k 1 - x * xk x *
第一节、最速下降法

最速下降法的基本思路最速下降法是一种用于最小化函数的优化算法。

它是一种迭代方法，通过在每一步选择使目标函数值减少得最快的方向，逐渐逼近函数的最小值。

最速下降法被广泛应用于数学、物理、工程和计算机科学领域。

最速下降法的基本思路是通过计算目标函数在当前点的梯度来确定下一个搜索方向。

梯度是函数在某一点的变化率，它指向函数值增加最快的方向。

在最速下降法中，我们希望函数值减小，因此选择梯度的反方向作为搜索方向。

这样，每一步都朝着函数值减小最快的方向前进，直到达到最小值或满足停止准则。

最速下降法的步骤如下：1. 初始化：选择起始点x0，并设定停止准则，如目标函数值的变化小于某个阈值或达到最大迭代次数。

2. 计算梯度：计算目标函数的梯度∇f(x)在当前点xk处的值。

3. 更新搜索方向：选择梯度的反方向作为搜索方向dk。

4. 确定步长：确定步长αk，使得目标函数在xk+αk·dk处取得最小值。

5. 更新位置：更新当前点的位置xk+1=xk+αk·dk。

6. 判断停止条件：检查是否满足停止准则，如果满足则结束迭代，否则返回步骤2。

最速下降法的效率受到函数形状的影响。

如果目标函数是凸函数且具有连续的二阶导数，最速下降法能够快速收敛到最小值。

然而，对于非凸函数或具有高度非线性特性的函数，最速下降法可能陷入局部最小值，导致收敛速度较慢或无法找到最小值。

最速下降法还存在一些问题。

步长的选择对算法的收敛速度和性能至关重要，过小的步长可能导致收敛速度缓慢，而过大的步长可能导致算法发散。

在实际应用中，选择合适的步长值是一个关键问题。

总结起来，最速下降法是一种基于梯度信息的优化算法，通过选择使目标函数值减少最快的方向进行搜索，并通过迭代逼近最小值。

它是一种简单直观的方法，但在处理复杂的函数或非凸问题时可能遇到困难。

在实际应用中，需要根据具体问题合理选择步长和停止准则，以达到较好的优化效果。

最速下降法，也被称为梯度下降法，是一种常用的优化算法，适用于求解目标函数的最小值。