如何理解最速下降法(哈工大数值分析)

最速下降法1.最速下降⽅向函数f(x)在点x处沿⽅向d的变化率可⽤⽅向导数来表⽰。

对于可微函数，⽅向导数等于梯度与⽅向的内积，即：Df(x;d) = ▽f(x)Td,因此，求函数f(x)在点x处的下降最快的⽅向，可归结为求解下列⾮线性规划：min ▽f(x)Tds.t. ||d|| ≤ 1当 d = -▽f(x) / ||▽f(x)||时等号成⽴。

因此，在点x处沿上式所定义的⽅向变化率最⼩，即负梯度⽅向为最速下降⽅向。

2.最速下降算法最速下降法的迭代公式是x(k+1) = x(k) + λkd(k) ,其中d(k)是从x(k)出发的搜索⽅向，这⾥取在x(k)处的最速下降⽅向，即d = -▽f(x(k)).λk是从x(k)出发沿⽅向d(k)进⾏⼀维搜索的步长，即λk满⾜f(x(k) + λkd(k)) = min f(x(k)+λd(k)) (λ≥0).计算步骤如下：(1)给定初点x(1) ∈ Rn，允许误差ε> 0，置k = 1。

(2)计算搜索⽅向d = -▽f(x(k))。

(3)若||d(k)|| ≤ ε，则停⽌计算；否则，从x(k)出发，沿d(k)进⾏⼀维搜索，求λk，使f(x(k) + λkd(k)) = min f(x(k)+λd(k)) (λ≥0).(4)令x(k+1) = x(k) + λkd(k) ，置k = k + 1，转步骤(2)。

共轭梯度法1.共轭⽅向⽆约束问题最优化⽅法的核⼼问题是选择搜索⽅向。

以正定⼆次函数为例，来观察两个⽅向关于矩阵Ａ共轭的⼏何意义。

设有⼆次函数：f(x) = 1/2 (x - x*)TA(x - x*) ,其中A是n×n对称正定矩阵，x*是⼀个定点，函数f(x)的等值⾯1/2 (x - x*)TA(x - x*) = c是以x*为中⼼的椭球⾯，由于▽f(x*) = A(x - x*) = 0，A正定，因此x*是f(x)的极⼩点。

设x(1)是在某个等值⾯上的⼀点，该等值⾯在点x(1)处的法向量▽f(x(1)) = A(x(1) - x*)。

最速下降法姓名：沈东东 班级：研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 =-。

最速下降法求解线性代数方程组要求：对于给定的系数矩阵、右端项和初值，可以求解线性代数方程组一、最速下降法数学理论在基本迭代公式k k k k P t X X +=+1中，每次迭代搜索方向k P 取为目标函数)(X f 的负梯度方向，即)(k k X f P -∇=，而每次迭代的步长k t 取为最优步长，由此确定的算法称为最速下降法。

为了求解问题)(min X f ，假定我们已经迭代了k 次，获得了第k 个迭代点k X 。

现在从k X 出发，可选择的下降方法很多，一个非常自然的想法是沿最速下降方向（即负梯度方向)进行搜索应该是有利的，至少在k X 邻近的范围内是这样。

因此，去搜索方向为)(k k X f P -∇=.为了使目标函数在搜索方向上获得最多的下降，沿k P 进行一维搜索，由此得到第1+k 个跌带点，即)(1k k k k X f t X X ∇-=+，其中步长因子k t 按下式确定))((m in ))((k k k k k k X f t X f X f t X f ∇-=∇-，))(,(1k k k X f X ls X -∇=+. （1） 显然，令 ,2,1,0=k 就可以得到一个点列 ,,,210X X X ,其中0X 是初始点，由计算者任意选定。

当)(X f 满足一定的条件时，由式（1）所产生的点列}{k X 必收敛于)(X f 的极小点。

二、最速下降法的基本思想和迭代步骤已知目标函数)(X f 及其梯度)(X g ，终止限21,εε和3ε.（1）选定初始点0X ，计算)(),(0000X g g X f f ==；置0=k .（2）作直线搜索：),(1k k k g X ls X -=+；计算)(),(1111++++==k k k k X g g X f f . 用终止准则检验是否满足：若满足，则打印最优解))(,(11++k k X f X ，结束；否则，置1+=k k ，转（2）（3）最速下降法算法流程图如图所示.三、最速下降法的matlab实现function [x,n]=twostep(A,b,x0,eps,varargin)%两步迭代法求线性方程组Ax=b的解if nargin==3eps= 1.0e-6;M = 200;elseif nargin<3errorreturnelseif nargin ==5M = varargin{1};endD=diag(diag(A)); %求A的对角矩阵L=-tril(A,-1); %求A的下三角阵U=-triu(A,1); %求A的上三角阵B1=(D-L)\U;B2=(D-U)\L;f1=(D-L)\b;f2=(D-U)\b;x12=B1*x0+f1;x =B2*x12+f2;n=1; %迭代次数while norm(x-x0)>=epsx0 =x;x12=B1*x0+f1;x =B2*x12+f2;n=n+1;if(n>=M)disp('Warning: 迭代次数太多，可能不收敛！');return;endendfunction [x,n]= fastdown(A,b,x0,eps) %最速下降法求线性方程组Ax=b的解if(nargin == 3)eps = 1.0e-6;endx=x0;n=0;tol=1;while(tol>eps) %以下过程可参考算法流程r = b-A*x0;d = dot(r,r)/dot(A*r,r);x = x0+d*r;tol = norm(x-x0);x0 = x;n = n + 1;end四、最速下降法的算例实现A=[5 2 0;6 4 1;1 2 5];b=[10 18 -14]';eps=1.0e-6;x =-0.87507.1875-5.5000 k =60。

−1 1
=
G
αk
=
g1d1 + g2d2 3d12 + d22 − 2d1d2
[ ] [ ] 取 X (1) = (0, 0)T ，则 ∇f ( X (1) ) = −2, 0 T ，所以 d (1) = −∇f ( X (1) ) = 2, 0 T ，
因此
α1
=
22 3× 22
=
1 3
[ ] [ ] X (2) = X (1) + α1d (1) =
=
1 + 4x1 + 2x2 −1+ 2x1 + 2x2
∂(x2 )
∇f
(X
(1) )
=
1 −1
令搜索方向 d (1)
=
−∇f
(X
(1) )
=
−1 1
再从
X
(1) 出发，沿
d (1) 方向作一维寻优，令
步长变量为 λ
，最优步长为 λ1 ，则有
X
(1)
+
λd (1)
=
0 0
+
λ
−1 1
min f ( X ) = (x1 − 2)4 + (x1 − 2x2 )2
其中 X = (x1, x2 )T ，要求选取初始点 X 0 = (0, 3)T ，终止误差 ε = 0.1.
解：因
∇f ( X ) = [4(x1 − 2)3 + 2(x1 − 2x2 ), −4(x1 − 2x2 )]T
∇f (x∗ ) = 0源自(二)最速下降法的基本思想和迭代步骤
最速下降法又称为梯度法，是 1847 年由著名数学家 Cauchy 给出的。他是解析法中最古老的一 种，其他解析方法或是它的变形，或是受它的启发而得到的，因此它是最优化方法的基础。

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

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

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

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)的最优解了。

0 为一维搜索最佳步长，应满足极值必要条件
0 0 f x1 min f x f x
min 2 4 25 2 100 min
2 2


0 8 2 4 5000 2 100 0
(k ) (k ) d x 3.若 ,则停止计算;否则,从 出发,沿 d ( k ) 进行
,使
f ( x ( k ) k d ( k ) ) min f ( x ( k ) d ( k ) )
0
4.令 x ( k 1) x ( k ) k d ( k ) ,置 k : k 1,转步2..
从而算出一维搜索最佳步长
626 0 0.02003072 31252 及第一次迭代设计点位置和函数值
1.919877 2 4 0 x 2 2 100 0 0.3071785 10
1
f x1 3.686164
经过10次迭代，得到最优值
4 计算框图
x(1), ε >0, k=1
k=k+1
|| ▽f(x(k) ) ||< ε? No d(k)= －▽f(x(k) )
Yes stop. x(k) –解
min f(x(k)+λ d(k)) s.t. λ >0 得 x(k+1)=x(k)+λkd(k) 解
P37 例 3-1
2 例：求目标函数 f x x12 25x2 的极小点。
f ( x ( k ) k d ( k ) ) min f ( x ( k ) d ( k ) )
0
f ( x( k ) )T f ( x( k ) ) 最优步长法： k f ( x( k ) )T H ( x( k ) )f ( x( k ) )

求单变量极小化问题：
min f ( x 0 + tp 0 ) = min f (44t , 3 − 24t )
t ≥0 t ≥0
= min(44t − 2)4 + (92t − ቤተ መጻሕፍቲ ባይዱ)2
t ≥0
的最优解 t 0 ，由 0.618 法可得 t 0 = 0.06 ，于是
X 1 = x 0 + t 0 p 0 = (2.70,1.51)T ∇f ( X 1 ) = (0.73,1.28)T ∇f ( X 1 ) = 1.47 > ε
T T
解：计算目标函数的梯度和 Hesse 阵
设d
(k )
= [ d1 , d 2 ] ， ∇f ( X ( k ) ) = [ g1 , g 2 ] 得到精确一维搜索步长 αk = g1d1 + g 2 d 2 3d + d 2 2 − 2d1d 2
2 1
取X
(1)
= (0, 0)T ，则 ∇f ( X (1) ) = [ −2, 0] ，所以 d (1) = −∇f ( X (1) ) = [ 2, 0 ] ，
故
f ( x) = f ( X ( 2) + λ d (2) ) = (λ − 1) − (λ + 1) + 2(λ − 1)2 + 2(λ − 1)(λ + 1) + (λ + 1) 2 = 5λ 2 − 2λ − 1 = ϕ 2 (λ )
' 令 ϕ2 (λ ) = 10λ − 2 = 0 可得 λ2 =
一、最速下降法基本原理
(一) 无约束问题的最优性条件
无约束问题的最优解所要满足的必要条件和充分条件是我们设计算法的依据， 为此我们有以下 几个定理。 定理 1 设 f : R → R 在点 x ∈ R 处可微。若存在 p ∈ R ，使

（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. 最速下降法性质与评价

我们将要讨论的无约束优化问题的格式为：min ()f x ()n x R ∈(一)无约束优化问题的最优性条件无约束优化问题的最优解所要满足的必要条件和充分条件是我们设计算法的依据，为此我们有以下几个定理。

定理1 设f :n R R →在点*n x R ∈处一阶可导。

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

定理2 （一阶必要条件） 设:n f R R →在点n x R *∈处一阶可导。

若x *是f 的局部极小点，则()0f x *∇=由数学分析中我们已经知道，使()0f x ∇=的点x 为函数f 的驻点或平稳点。

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

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

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

定理3 （二阶必要条件） 设:n f R R →在点n x R *∈处二阶可导。

若*x 是f 的局部极小点，则必有()0f x *∇=且2()f x *∇半正定。

定理4 （二阶充分条件） 设:n f R R →在点n x R *∈处二阶可导。

若()0f x *∇=，并且2()f x *∇正定则x *是f 的严格局部极小点。

无约束优化问题有很多种算法，比如最速下降法，牛顿法，拟牛顿法，共轭梯度法，我们只针对两种方法进行讨论，分析，比较，还有MATLAB 算法的实现，在接下来的篇幅中，我们将讨论最速下降法和共轭梯度法。

(二)最速下降法最速下降法又称为梯度法，是1847年由著名数学家Cauchy 给出的。

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

最速下降法的原理：目标函数在:n f R R →在决策变量的当前点n k R x ∈处的一阶Taylor 展开式为)()()()(δδδo x g x f x f T k k k ++=+式中，n k x g R )(∈为f 在点k x 的梯度向量。

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

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

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

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)的最优解了。

最速降线的详细原理最速降线（brachistochrone）是一种优化问题，它的目标是找到两个点之间，使得质点沿着该路径下落的时间最短。

这个问题最早由约翰·伯努利在1696年提出，它在物理学、数学、工程学等领域都有着广泛的应用。

最速降线的求解可以通过变分法来实现。

变分法是一种数学工具，用于求解优化问题，它的基本思想是将变量看作函数，然后对这些函数进行微分和积分运算，最终得到一个最优解。

在最速降线的求解中，我们需要找到一条曲线，使得质点沿着该曲线下落的时间最短。

这个问题可以通过最小化路径积分来求解。

假设我们要求解从点A到点B的最速降线，我们可以将这条曲线表示为y(x)，其中x表示曲线上的位置，y表示曲线的高度。

我们也可以将曲线表示为参数形式，即x(t)和y(t)，其中t表示时间。

则质点的速度可以表示为v(t)=sqrt(2gy(t))，其中g表示重力加速度。

因此，质点在曲线上运动的时间可以表示为T = ∫(sqrt(1+y'(x)^2)/sqrt(2gy(x))) dx其中y'(x)表示y(x)的导数。

我们需要最小化这个路径积分，即使得T最小化。

这个问题可以通过欧拉-拉格朗日方程来求解。

欧拉-拉格朗日方程是变分法的核心工具，它是一种微分方程，用于求解最小化问题。

在最速降线的求解中，欧拉-拉格朗日方程可以表示为d/dx(dL/dy') - dL/dy = 0其中L表示拉格朗日量，它可以表示为L = sqrt(1+y'(x)^2)/sqrt(2gy(x))通过求解欧拉-拉格朗日方程，我们可以得到最速降线的解析式。

这个问题的求解比较复杂，需要使用高等数学的知识，比如微积分、微分方程等。

但是，我们可以使用计算机来求解这个问题。

最速降线的应用非常广泛，比如在机械工程中，它可以用于设计滑轮系统和弹簧系统；在航天工程中，它可以用于设计火箭的轨迹和飞行器的降落轨迹；在物理学中，它可以用于求解质点在重力场中的运动等等。

解释最速降线简单原理
最速降线是一种在优化问题中常用的方法，其基本原理是从一个起点开始，沿着某个方向一直走，让每一步都减小到最小值，直到达到全局最小值为止。

最速降线是一种对目标函数的梯度下降方法，其对目标函数进行了一步步的优化，通过找到局部最优解的方向，逐步减少目标函数值，直到找到全局最优解。

最速降线方法的主要目标是确定每一步的方向及步长，以使得目标函数值能够尽量地减少。

在实际应用中，最速降线方法通常结合梯度下降算法使用，其主要步骤如下：
1.选定起始点：首先，需要确定起始点，即从哪里开始进行优化。

这里可以采用随机或者手动指定的方法来确定起始点。

2.计算梯度：为了确定下一步的方向和步长，需要计算当前位置的梯度。

梯度是指目标函数在当前位置处的方向导数，其方向指向函数在该点上升最快的方向。

3.确定步长：在确定下一步的方向后，需要确定每一步的长度。

一般而言，步长可以通过预测当前位置到达全局最小值所需要的步数来确定。

4.更新位置：将步长和方向相乘，以更新当前位置。

也就是说，当前位置移动到下一个位置。

5.重复操作：一旦到达下一个位置，就需要重新计算梯度和确定步长，以便于尽可能地接近最优解。

不断重复这个过程，直到达到全局最优解时为止。

最速降线方法在优化问题中得到了广泛应用，比如在机器学习、神经网络和数据挖掘等领域。

其优点是简单易懂，容易实现，并且在很多情况下可以找到全局最优解，但缺点就是可能遇到局部最优解，无法达到全局最优解的情况。

因此，在实际应用中，需要根据具体情况对最速降线方法进行调整和改进。

4、记 mk 是满足下列不等式的最小非负整数m.
f ( xk ? ? mdk ) ? f (xk ) ? ?? m gkT dk
5、令 ? k ? ? mk , xk ?1 ? xk ? ? k dk , k :? k ? 1 ，转1.
三、程序
1、最速下降法程序 ? grad.m
? function [x,val,k]=grad(fun,gfun,x0)
? for i=2:n
? h=subs(h,xx(i));
? end
? He=h;
四、实验数据
? 第一题函数： ? fun.m ? function f=fun(x) ? D=30; ? x1=0; ? for i=1:D ? x1=x(i).^2+x1; ? end ? f=x1;
第四题函数： function f=fun(x) f=0; for i=1:n-1
? 2、阻尼牛顿法
? 初始点需要足够“靠近”极小点，否则，有可能导致算法不 收敛。由于实际问题的精确极小点一般是不知道的，因此， 初始点的选取给算法的实际操作带来了很大的困难，为了克 服这一困难，可引入线搜索技术以得到大范围收敛的算法， 即所谓的阻尼牛顿法.给出一个基于Armijo搜索的阻尼牛顿法。
?
if(feval(fun,x0+rho^m*d)<feval(fun,x0)+sigma*rho^m*g'*d)
?
mk=m;break;
?
end
?
m=m+1;
? end
? x0=x0+rho^mk*d;
? k=k+1;
? end
? x=x0;
? val=feval(fun,x0);

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

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

设无约束问题中的目标函数f : Rn ® R1一阶连续可微。

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

于是，我们可以构造出最速下降法的迭代步骤。

解无约束问题的的最速下降法计算步骤第 1 步选取初始点x0，给定终止误差e > 0，令k := 0；第 2 步计算Ñf (xk )，若‖Ñf (xk )‖￡ e ，停止迭代.输出xk .否则进行第三步；第 3 步取 pk = -Ñf (xk )；第 4 步进行一维搜索，求k t ，使得( k k ) min ( k k )k tf x tp f x tp3+ = +令 k 1 k kk x + = x + t p ，k := k +1，转第2 步。

由以上计算步骤可知，最速下降法迭代终止时，求得的是目标函数驻点的一个近似点。

确定最优步长k t 的方法如下：方法一：采用任一种一维寻优法此时的f (xk - tÑf (xk ))已成为步长t的一元函数，故可用任何一种一维寻优法求出k t ，即( k 1) ( k ( k )) min ( k ( k ))k tf x + = f x - t Ñf x = f x -tÑf x方法二：微分法因为tf (xk - tÑf (xk )) = j(t) 所以，一些简单情况下，可令j' (t) = 0以解出近似最优步长k t 的值。

x*=x(k)
结束
否
一维搜索求tk f ( x k t g k ) min f ( x k tg k ) k t 0 精度为 2 x(k+1) = x(k) －tk f(x(k) ) k=k+1
vjghkjh
7
（三）最速下降法的搜索路径呈直角锯齿形 定理4.1 设从点x(k) 出发，沿方向d作精确一维搜索， tk为最优步长因子，即 f(x(k) + tk dk) = min f( x(k) + t dk) t>0 则成立 f(x(k) + tk d) T d =0, 即新点处的梯度与搜索方向垂直。 即
第四章
本章要点：
无约束非线性问题的解法
最速下降法的基本思想及特点
min f ( x ) n
x R
牛顿方向 Newton法基本思想及特点 共轭方向、共轭方向法的基本定理 共轭梯度法基本思想 拟Newton法的基本思想
vjghkjh
1
学习的重要性： 1、直接用于无约束的实际问题； 2、其基本思想和逻辑结构可以推广到约束问题； 3、约束问题可以转化成无约束问题求解。
5
x(k+1)
=
x(k)
－ tk
f(x(k)
下面看一下理论推导： 设函数f(x)在xk附近连续可微，且gk= f(xk) ≠0，由Taylor展式
f ( x ) f ( x k ) ( x x k )T f ( x k ) o( x x k )
可知，若记x-xk=tdk，则满足(dk)Tgk<0的方向dk是下降方向。当t取定后， (dk)Tgk的值越小，即- (dk)Tgk的值越大，函数下降的越快。由CauchySchwartz不等式