最速下降法原理及例题实例
- 格式：pdf
- 大小：134.91 KB
- 文档页数：10
下载文档原格式
合集下载
最速下降法原理
最速下降法原理嘿，朋友们！今天咱来聊聊最速下降法原理。
这玩意儿啊，就好比你在一个大山里找下山的最快路。
想象一下，你站在山顶，周围都是迷雾，你不知道哪条路是最快能到山底的。
那咋办呢？最速下降法就来帮忙啦！它就像是你手里的指南针，给你指引一个大致的方向。
你就沿着这个方向先走一小步，然后看看，哎呀，是不是离山底更近了点呢？如果是，那就好，接着再沿着这个方向走一小步。
可要是发现好像不太对，那就稍微调整一下方向。
这就好像你走路，有时候会走偏一点，那你就得赶紧调整回来，不然不就越走越远啦？最速下降法就是这么神奇，让你不断地靠近目标。
你说这像不像我们平时做事啊？我们一开始也不知道怎么做才是最好的，那就先试着来嘛！走一步看一步，发现不对就赶紧调整。
比如说你想学会一门乐器，一开始可能弹得乱七八糟的，但是你每次都发现问题，然后改正，慢慢地不就越来越好了嘛！这和最速下降法是一个道理呀！而且哦，这个过程中可不能着急。
就像下山一样，你要是急急忙忙地乱跑，说不定就摔跟头啦！得稳稳地，一步一步来。
最速下降法也不是一下子就能让你找到最好的路，它只是给你一个指引。
有时候可能会走一些弯路，但没关系呀，这都是过程嘛！你想想，要是一下子就找到了最好的路，那多没意思呀，一点挑战都没有。
就是因为有这些曲折，我们才会更加珍惜最后到达目的地的那一刻呀！我们的生活不也是这样嘛？总是会遇到各种各样的问题，但只要我们有最速下降法这样的精神，不断地去尝试，去调整，就一定能找到属于我们自己的路，走向成功的彼岸。
所以啊，别害怕困难，别害怕走弯路，就大胆地去尝试吧！让最速下降法带着我们在生活的大山里找到下山的最快路径！相信自己，一定可以的！。
非线性方程组-最速下降法(梯度法)
梯度法（又名,最速下降法）(该法总可以收敛，但是，在接近真解时收敛的速度会放慢。
) 梯度法又称为最速下降法，用于求解实系数非线性方程组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.迭代原理
P(k)
f ( X (k) )
梯度的性质：函数f (X)在X(k)处P(的k) 负梯度X (方k) 向 f ( X (k) )
是X(k)处函数值下降最快的方向。
证明：
P(k)
一元函数泰勒公式：
P(k)
X p p (k)
(k)
(k)
f ( x(k) h) f ( x(k)) f ( x(k) )h (h)
线性规划3-4
最速下降法迭代原理：
min
XRn
f ( X )
x14
x22
2
f ( X ) (4 x13 , 2 x2 )T
p0
0
X1
X0
X 0 , p0 f ( X 0 ), min f ( X 0 p0 ) f ( X 0 0 p0 ), X 1 X 0 0 p0 0
X 0 (1,1)T , p0 f ( X 0 ) (4, 2)T
min f ( X )
XRn
当X (k ) X 时, f ( X (k) ) f ( X ) 0 (一阶必要条件)
f ( X (k) ) f ( X ) 0
f ( X (k) )
p(k)
线性规划3-4
3.迭代步骤
f ( X (k1) )
10 取初始点X (0) , 容许误差(精度) 0, 令k : 0k
p0 f ( X 0 ), p1 f ( X 1 ), pk f ( X k ),
min f ( X 0 p0 )
0
min f ( X 1 p1)
0
min f ( X k pk )
0
f ( X 0 0 p0 ), X 1 X 0 0 p0 f ( X 1 1 p1 ), X 2 X 1 1 p1 f ( X k k pk ), X k1 X k k pk
最速下降法例题
r é3ù g0 = ê ú ë -3û
r é1ù é 6 -3ù é 3 ù é1ù 1 é0 3ù é 3 ù x1 = ê ú - ê =ê ú+ ê ú ê ú ú ê ú 0 3 0 3 0 3 6 3 ë û ë û ë û ë û 9ë ûë û é3ù r r r é1 ù 1 é- 9ù é 0 ù g = ê ú + ê ú = ê ú . ( x1 ) = ê ú ¹ 0, 不是极小点 3û ë 0 9 1 9 ë û ë û ë û
r é3/ 4 ù r g2 = ê ¹0 ú ë 0 û
例3 用最速下降法求解
min f ( x1 , x 2 ) = x + x2 - 3 x1 x2
3 1 3
判别所得的点是否为极小点
r é1 ù x0 = ê ú ë0û
迭代二次
2 6 x1 -3 ù é é ù 3 x 3 x r 1 2 G ( x , x ) = f ( x ) = 1 2 ê -3 6 x ú ê 1 解： 2ú ë 2û ë -3x1 + 3x2 û
例题 用最速下降法求解
x12 x2 2 . min{ + } (a>0,b>0,a ¹ b) a b r éa ù 选取 x0 = ê ú . ëb û é 2 x1 ù é2 ù êa 0ú ê a ú 解： Q = ê ú ， f ( x ) = ê 2 x ú ， ê 2ú ê0 2ú ê ú b ë û ê ú bû ë
r é -5 / 2ù 1 é -1ù é -3ù r é0ù x2 = ê + ê ú = ê ú . g2 = ê ú ú ë 1 û 2ë 2 û ë 2 û ë 0û
无约束优化方法(最速下降法_牛顿法)
第四章 无约束优化方法——最速下降法，牛顿型方法概述在求解目标函数的极小值的过程中，若对设计变量的取值范围不加限制，则称这种最优化问题为无约束优化问题。
尽管对于机械的优化设计问题，多数是有约束的，无约束最优化方法仍然是最优化设计的基本组成部分。
因为约束最优化问题可以通过对约束条件的处理，转化为无约束最优化问题来求解。
为什么要研究无约束优化问题?（1）有些实际问题，其数学模型本身就是一个无约束优化问题。
（2）通过熟悉它的解法可以为研究约束优化问题打下良好的基础。
（3）约束优化问题的求解可以通过一系列无约束优化方法来达到。
所以无约束优化问题的解法是优化设计方法的基本组成部分，也是优化方法的基础。
根据构成搜索方向所使用的信息性质的不同，无约束优化方法可以分为两类。
一：间接法——要使用导数的无约束优化方法，如梯度法、（阻尼）牛顿法、变尺度法、共轭梯度法等。
二：直接法——只利用目标函数值的无约束优化问题，如坐标轮换法、鲍威尔法单纯形法等。
无约束优化问题的一般形式可描述为：求n 维设计变量 []12Tn n X x x x R =∈使目标函数 ()min f X ⇒目前已研究出很多种无约束优化方法，它们的主要不同点在于构造搜索方向上的差别。
无约束优化问题的求解： 1、解析法可以利用无约束优化问题的极值条件求得。
即将求目标函数的极值问题变成求方程0)(min *=X f的解。
也就是求Ｘ＊使其满足解上述方程组，求得驻点后，再根据极值点所需满足的充分条件来判定是否为极小值点。
但上式是一个含有ｎ个未知量，ｎ个方程的方程组，在实际问题中一般是非线性的，很难用解析法求解，要用数值计算的方法。
由第二章的讲述我们知道，优化问题的一般解法是数值迭代的方法。
因此，与其用数值方法求解非线性方程组，还不如用数值迭代的方法直接求解无约束极值问题。
2、数值方法数值迭代法的基本思想是从一个初始点)0(X出发，按照一个可行的搜索方向)0(d搜索，确定最佳的步长0α使函数值沿)0(d 方向下降最大，得到)1(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
计算步骤
设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 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. 最速下降法性质与评价
最速下降法
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 )
收敛性问题的基本概念 最速下降法的迭代原理 最速下降法的迭代步骤 最速下降法的举例 最速下降法的收敛结论
Байду номын сангаас
无约束问题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 )
最速下降问题
最速下降演示实验清华大学物理系 路峻岭如图，三个相同的球沿三个不同的轨道——斜线、圆弧、旋轮线轨道滚动，结果是沿旋轮线轨道滚动最快，用时最短。
1.球沿轨道作纯滚动与纯滑动的比较以斜线轨道为例进行讨论。
如下图，设斜线轨道的倾角为θ，匀质实心球质量为M ，半径R ，滚动半径r ，绕过质心轴的转动惯量225MR 。
球体受到3个力作用：重力、弹力和静摩擦力。
若静摩擦力足够大，球体可以保持纯滚动。
以,,,c c a v βω为变量，则有()()2sin 25000c c c Mg f Ma fr MR a r v R θββω−=⎧⎪⎪=⎪⎨⎪=⎪==⎪⎩ (1) 解得：22222sin ,,,25sin sin 2255c c c g v a t t R r r rg r g a R R r r rθβωβθθ===+==++ （2） 如果球在光滑的轨道上只滑动不滚动，则sin c a g θ=，即球的纯滚动与纯滑动的质心加速度仅相差一个与仪器结构有关的因子。
对上面三个轨道，结构因子相同。
这样球在三个轨道下落快慢的问题，可以等效地用球光滑滑动（质点）替代实际的球纯滚动（刚体）进行讨论，所得结论不变。
2.最速下降问题最速下降是个古老的问题，又称捷线问题。
有关泛函或变分法的书多采用此例引入相关概念。
其问题是：在空间高低两点之间寻找一条连接两点的光滑轨道，使质点沿轨道从高点下滑到低点用时最短。
如右图，过高低两点作一铅直平面，在此平面内建立直角坐标系。
以高点为原点，水平方向为x 轴，竖直向下为y 轴，设低点E的坐标为000(,)(0)x y y >。
现在的问题就是寻找过O 点和E 点的众多平面曲线()y y x =中使得质点下滑用时最少者。
设轨道()y y x =连续光滑，易得到质点由静止开始沿轨道由O 点到E 点所用时间为：()00x t y x =⎡⎤⎣⎦∫ （3）()t y x ⎡⎤⎣⎦表示t 是函数()y x 的函数，ds dy dx dx y =+=′+222)()(1为质点下落()y x 后的速度大小。
最优化方3.3法最速下降法(梯度法)
例 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) –解
最速下降法
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 *
第一节、最速下降法
第二章 (2)最速下降法-Newton法-共轭梯度法
取初始向量 x0 1,1T .
解：函数的梯度为
f
(
x)
2
x1 2x2 2 x1 +4x2
4
,
第1次迭代：
f
x0
4
2
,
d 0 = f
x0
4 2
,
x0
+
d
0
=
1+4 1 2
的最大和最小特征值
对于正定二次函数 f (x) 1 xTGx bT x
步长
2
最速下降法的下一个迭代点，
xk 1
xk
gkT gk gkT Ggk
gk
二、最速下降法
其中：
二、最速下降法
得最速下降法的步长
k
gkT gk gkT Ggk
从而下一个迭代点为
xk 1
xk
gkT gk gkT Ggk
+0d
0
=
1 1
+1/4
4 2
=
2 1/2
，
f
x1
1
2
,
第2次迭代：
d1= f
x1
1 2
,
x1
+
d
1
=
2+ 1/2+2
，
()=f x1+d1 =f 2+,1/2+2
1
- 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
−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 给出的。他是解析法中最古老的一 种，其他解析方法或是它的变形，或是受它的启发而得到的，因此它是最优化方法的基础。
设无约束问题中的目标函数 f : Rn → R1 一阶连续可微。 最速下降法的基本思想是：从当前点 xk 出发，取函数 f (x) 在点 xk 处下降最快的方向作为我 们的搜索方向 pk .由 f (x) 的 Taylor 展式知
=
−λ λ
故 f (x) = f ( X (1) + λd (1) ) = (−λ) − λ + 2(−λ)2 + 2(−λ)λ + λ2 = λ 2 − 2λ = ϕ1(λ)
令ϕ1' (λ) = 2λ − 2 = 0 可得 λ1 = 1
X
(2)
=
X
(1)
+ λ1d (1)
=
0 0
+
−1 1
∇f ( X k )
50.12 1.47 0.93 0.33 0.36 0.14 0.17 0.09
tk
X k +1
0.06 (2.70,1.51)T 0.24 (2.52,1.20)T 0.11 (2.43,1.25)T 0.31 (2.37,1.16)T 0.12 (2.33,1.18)T 0.36 (2.30,1.14)T 0.13 (2.28,1.15)T
f (xk ) − f ( xk + tpk ) = −t∇f (xk )T pk + o‖( tpk‖) 略去 t 的高阶无穷小项不计，可见取 pk = −∇f (xk ) 时，函数值下降得最多。于是，我们可以构造
出最速下降法的迭代步骤。
解无约束问题的的最速下降法计算步骤
第 1 步 选取初始点 x0 ，给定终止误差ε > 0 ，令 k := 0 ； 第 2 步 计算 ∇f (xk ) ，若‖∇f ( xk )‖≤ ε ，停止迭代.输出 xk .否则进行第三步； 第 3 步 取 pk = −∇f (xk ) ；
最速下降法原理以及其算法的实现
最速下降法又称为梯度法，是 1847 年由著名数学家 Cauchy 给出的，它是解析法中最古老 的一种，其他解析方法或是它的变形，或是受它的启发而得到的，因此它是最优化方法的基础。 作为一种基本的算法，他在最优化方法中占有重要地位。其优点是工作量少，存储变量较少， 初始点要求不高；缺点是收敛慢，效率不高，有时达不到最优解。非线性规划研究的对象是非 线性函数的数值最优化问题。它的理论和方法渗透到许多方面，特别是在军事、经济、管理、
例3 用最速下降法求解无约束问题
min
f
(x)
=
3 2
x12
+
1 2
x22
−
x1x2
−
2x1
取 X (1) = (0, 0)T ，ε = 10−2 。
解：计算目标函数的梯度和 Hesse 阵
∇f
(
X
)
=
3x1 − x2 − x2 − x1
2
=
g1 g2
，
∇2
f
(
X
)
=
3 −1
[ ] [ ] 设 d (k) = d1, d2 T ， ∇f ( X (k) ) = g1, g2 T 得到精确一维搜索步长
=
−1 1
求出 X (2) 点之后，与
上类似地，进行第二次迭代：
∇f
(
X
(2)
)
=
−1 −1
令 d (2)
=
−∇f
(X
(2) )
=
1 1
令步长变量为 λ ，最优步长为 λ2 ，则有
X
(2)
+ λd (2)
=
−1 1
+
λ
1 1
=
λ λ
−1 +1
故
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 5
X
(3)
=
X
(2)
+
λ2d (2)
=
−1 1
+
1 5
1 1
=
−0.8 1.2
∇f
(
X
(3)
)
=
0.2 −0.2
此时所达到的精度 ∇f ( X (3) )
≈ 0.2828
本题最优解
X∗
=
−1 1.5
，
f
(X∗)
=
−1, 25
例 2 用最速下降法求解无约束非线性规划问题：
生产过程自动化、工程设计和产品优化设计等方面都有着重要的应用。而最速下降法正是 n 元 函数的无约束非线性规划问题 min f (x) 的一种重要解析法，研究最速下降法原理及其算法实
现对我们有着极其重要的意义。
一、最速下降法基本原理
(一)无约束问题的最优性条件
无约束问题的最优解所要满足的必要条件和充分条件是我们设计算法的依据，为此我们有以下 几个定理。
点可以是极小点；也可以是极大点；甚至也可能既不是极小点也不是极大点，此时称它为函数 f 的 鞍点。以上定理告诉我们， x∗ 是无约束问题的的局部最优解的必要条件是： x∗ 是其目标函数 f 的
驻点。 现给出无约束问题局部最优解的充分条件。
定理 3 设 f : Rn → R1 在点 x∗ ∈ Rn 处的 Hesse 矩阵 ∇2 f (x∗ ) 存在。若 ∇f (x∗ ) = 0 ，并且 ∇2 f (x∗ ) 正定
f (Xk)
52.00 0.34 0.09 0.04 0.02 0.01 0.009 0.007
表 1-1
∇f ( X k )
(−44, 24)T (0.73,1.28)T (0.80, −0.48)T (0.18, 0.28)T (0.30, −0.20)T (0.08, 0.12)T (0.15, −0.08)T (0.05, 0.08)T
x(2) O xg(4) x(3)
图 1-3 因此，在实用中常将最速下降法和其他方法联合应用，在前期使用最速下降法，而在接近极小 点时，可改用收敛较快的其他方法。
则
∇f (X 0 ) = (−44, 24)T
∇f (X 0) = 50.12 > ε
求单变量极小化问题：
p0 = −∇f (X 0 ) = (44, −24)T
min f (x0 + tp0 ) = min f (44t, 3 − 24t)
t≥0
t≥0
= min(44t − 2)4 + (92t − 6)2 t≥0
此时的 f (xk − t∇f (xk )) 已成为步长 t 的一元函数，故可用任何一种一维寻优法求出 tk ，即
f (xk +1) =
f (xk
−
tk
∇f
(
xk
))
=
min t
f (xk
− t∇f (xk ))
方法二：微分法
因为
tf (xk − t∇f (xk )) = ϕ(t)
所以，一些简单情况下，可令
则 x∗ 是无约束问题的严格局部最优解。
一般而言，无约束问题的目标函数的驻点不一定是无约束问题的最优解。但对于其目标函数是 凸函数的无约束凸规划，下面定理证明了，它的目标函数的驻点就是它的整体最优解。
定理 4 设 f : Rn → R1 ， x∗ ∈ Rn ， f 是 Rn 上的可微凸函数。若有
则 x∗ 是无约束问题的整体最优解。
0, 0 T + 1 3
2, 0 T
=