最速下降法:最速下降法又稱為梯度法，是1847年由著名數學家Cauchy -百科知識中文網

最速下降法又稱為梯度法，是1847 年由著名數學家Cauchy 給出的，它是解析法中最古老的一種，其他解析方法或是它的變形，或是受它的啟發而得到的，因此它是最最佳化方法的基礎。作為一種基本的算法，他在最最佳化方法中占有重要地位。其優點是工作量少，存儲變數較少，初始點要求不高；缺點是收斂慢，效率不高，有時達不到最優解。非線性規劃研究的對象是非線性函式的數值最最佳化問題。它的理論和方法滲透到許多方面，特別是在軍事、經濟、管理、生產過程自動化、工程設計和產品最佳化設計等方面都有著重要的套用。而最速下降法正是n元函式的無約束非線性規劃問題min f (x)的一種重要解析法，研究最速下降法原理及其算法實現對我們有著極其重要的意義。
一、最速下降法基本原理
(一)無約束問題的最優性條件
無約束問題的最優解所要滿足的必要條件和充分條件是我們設計算法的依據，為此我們有以下
幾個定理。
定理1 設 f : Rn ® R1在點x ÎRn處可微。若存在pÎRn，使
Ñf (x)T p < 0
則向量p是f 在點x 處的下降方向。
定理2 設 f : Rn ® R1在點x* Î Rn處可微。若x*是無約束問題的局部最優解，則
Ñf (x* ) = 0
由數學分析中我們已經知道，使Ñf (x) = 0的點x為函式f 的駐點或平穩點。函式f 的一個駐
點可以是極小點；也可以是極大點；甚至也可能既不是極小點也不是極大點，此時稱它為函式f 的
鞍點。以上定理告訴我們，x*是無約束問題的的局部最優解的必要條件是：x*是其目標函式f 的
駐點。
現給出無約束問題局部最優解的充分條件。
定理3 設 f : Rn ® R1在點x* Î Rn處的Hesse矩陣Ñ2 f (x* )存在。若
Ñf (x* ) = 0，並且Ñ2 f (x* )正定
則x*是無約束問題的嚴格局部最優解。
一般而言，無約束問題的目標函式的駐點不一定是無約束問題的最優解。但對於其目標函式是
凸函式的無約束凸規劃，下面定理證明了，它的目標函式的駐點就是它的整體最優解。
定理4 設 f : Rn ® R1，x* ÎRn， f 是Rn上的可微凸函式。若有
Ñf (x* ) = 0
則x*是無約束問題的整體最優解。
(二)最速下降法的基本思想和疊代步驟
最速下降法又稱為梯度法，是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 ，使得
0
( k k ) min ( k k )
k t
f x tp f x tp
3
+ = +
令 k 1 k k
k 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 t
f x + = f x - t Ñf x = f x -tÑf x
方法二：微分法
因為
tf (xk - tÑf (xk )) = j(t)
所以，一些簡單情況下，可令
j' (t) = 0
以解出近似最優步長k t 的值。
(三)最速下降法套用舉例
例 1 2 2
1 2 1 1 2 2 min f (x) = x - x + 2x + 2x x + x 給定初始點X (1) = (0,0)T
解：目標函式f (x)的梯度1 1 2
1 2
2
( )
( ) 1 4 2
( )
( ) 1 2 2
( )
f x
x x x
f x
f x x x
x
é¶ ù
ê ¶ ú é + + ù Ñ = ê ú = ê ú ê¶ ú ë- + + û
ê ¶ ú ë û
(1) 1
( )
1
f X
é ù
Ñ = ê ú ë- û
令搜尋方向(1) (1) 1
( )
1
d f X
é- ù
= -Ñ =ê ú
ë û
再從X (1)出發，沿d(1)方向作一維尋優，令
步長變數為l ，最優步長為1 l ，則有(1) (1) 0 1
0 1
X d
l
l l
l
é ù é- ù é- ù
+ = ê ú + ê ú = ê ú
ë û ë û ë û
故 (1) (1) 2 2 2
1 f (x) = f (X + ld ) = (-l) - l + 2(-l) + 2(-l)l + l = l - 2l = j (l)
令 '
1 ( j l) = 2l - 2 = 0可得1 l =1 (2) (1) (1)
1
0 1 1
0 1 1
X X l d
é ù é- ù é- ù
= + = ê ú + ê ú = ê ú
ë û ë û ë û
求出 X (2)點之後，與
上類似地，進行第二次疊代： (2) 1
( )
1
f X
é- ù
Ñ = ê ú ë- û
令 (2) (2) 1
( )
1
d f X
é ù
= -Ñ =ê ú
ë û
令步長變數為l ，最優步長為2 l ，則有
(2) (2) 1 1 1
1 1 1
X d
l
l l
l
é- ù é ù é - ù
+ = ê ú + ê ú = ê ú ë û ë û ë + û
故
(2) (2) 2 2 2
2 f (x) = f (X + ld ) = (l -1) - (l +1) + 2(l -1) + 2(l -1)(l +1) + (l +1) = 5l - 2l -1 = j (l)
令'
2 j (l) =10l - 2 = 0可得2
1
5
l = (3) (2) (2)
2
1 1 1 0.8
1 5 1 1.2
X X l d
é- ù é ù é- ù
= + = ê ú + ê ú = ê ú
ë û ë û ë û
(3) 0.2
( )
0.2
f X
é ù
Ñ = ê ú ë- û
此時所達到的精度Ñf (X (3) ) » 0.2828
本題最優解
1
1.5
X * é- ù
=ê ú
ë û
， f (X * ) = -1, 25
例2 用最速下降法求解無約束非線性規劃問題：
4 2
1 1 2 min f (X ) = (x - 2) + (x - 2x )
其中 1 2 X = (x , x )T，要求選取初始點X 0 = (0,3)T ，終止誤差e = 0.1.
解：因3
1 1 2 1 2 Ñf (X ) = [4(x - 2) + 2(x - 2x ),-4(x - 2x )]T
則 Ñf (X 0 ) = (-44, 24)T
Ñf (X 0 ) = 50.12 > e
p0 = -Ñf (X 0 ) = (44,-24)T
求單變數極小化問題：
0 0
0 0
min ( ) min (44 ,3 24 )
t t
f x tp f t t
3 3
+ = -
4 2
0
min(44 2) (92 6)
t
t t
3=
-
+
-
的最優解t0，由0.618 法可得t0 = 0.06，於是
X1 = x0 + t0 p0 = (2.70,1.51)T
Ñf (X1) = (0.73,1.28)T
Ñf (X1) =1.47 > e
令 p1 = -Ñf (X1)
再求單變數極小化問題
1 1
0
min ( )
t
f X tp
3
+
的最優解.略去計算步驟，由表1-1 給出計算結果.由表1-1 可以知道， Ñf (X 7 ) = 0.09 < e ，所以
X 7 = (2.28,1.15)T 為近似最優解，原問題的近似最優值為0.007 .
表1-1
疊代次
數k
X k f (X k ) Ñf (X k ) Ñf (X k ) tk X k +1
0 (0.00,3.00)T 52.00 (-44, 24)T 50.12 0.06 (2.70,1.51)T
1 (2.70,1.51)T 0.34 (0.73,1.28)T 1.47 0.24 (2.52,1.20)T
2 (2.52,1.20)T 0.09 (0.80,-0.48)T 0.93 0.11 (2.43,1.25)T
3 (2.43,1.25)T 0.04 (0.18,0.28)T 0.33 0.31 (2.37,1.16)T
4 (2.37,1.16)T 0.02 (0.30,-0.20)T 0.36 0.12 (2.33,1.18)T
5 (2.33,1.18)T 0.01 (0.08,0.12)T 0.14 0.36 (2.30,1.14)T
6 (2.30,1.14)T 0.009 (0.15,-0.08)T 0.17 0.13 (2.28,1.15)T
7 (2.28,1.15)T 0.007 (0.05,0.08)T 0.09
例3 用最速下降法求解無約束問題
2 2
1 2 12 1
min ( ) 3 1 2
2 2
f x = x + x - x x - x
取 (
X 1) = (0,0)T ，e =10-2 。
解：計算目標函式的梯度和Hesse陣
1 2 1
2 1 2
3 2
( )
x x g
f X
x x g
é - - ù é ù
Ñ = ê ú = ê ú ë - û ë û
， 2 3 1
( )
1 1
fX G
é - ù
Ñ = ê ú = ë- û
設 ( ) [ ]
1 2 , d k = d d T ， ( ) [ ]
1 2 ( ) , Ñf X k = g g T 得到精確一維搜尋步長
1 1 2 2
2 2
1 2 1 2 3 2 k
gd g d
d d d d
a
+
=
+ -
取 (
X 1) = (0,0)T ，則( (1) ) [ 2,0]T Ñf X = - ，所以(1) ( (1) ) [2,0]T d = -Ñf X = ，
2
1 2
2 1
3 2 3
a= =
′
因此
(2) (1) (1) [ ] [ ]
1
0,0 1 2,0 2 ,0
3 3
T
T T X = X +a d = + = éê ùú ë û
再計算第二輪循環，表1-2 列出了各次疊代的計算結果。總計算了9 個點， Ñf (X (9) ) = 0.025 <
10-2，停止計算，所以(9) [0.988,0.988]T X = 作為問題的最優解。
表 1-2
k X ( k ) f (X ( k ) ) Ñf (X (k ) ) d( k ) k a
1 (0.000,0.000) 0.000 (-2.000,0.000) (2.000,0.000) 0.333
2 (0.667,0.000) -0.667 (0.000,-0.667) (0.000,0.667) 1.000
3 (0.667,0.667) -0.889 (-0.667,0.000) (0.667,0.000) 0.333
4 (0.889,0.667) -0.963 (0.000,-0.222) (0.000,0.222) 1.000
5 (0.889,0.889) -0.988 (-0.222,0.000) (0.222,0.000) 0.333
6 (0.963,0.889) -0.996 (0.000,-0.074) (0.000,0.074) 1.000
7 (0.963,0.963) -0.999 (-0.074,0.000) (0.074,0.000) 0.333
8 (0.988,0.963) -1.000 (0.000,-0.025) (0.000,0.025) 1.000
9 (0.988,0.988) -1.000 (-0.025,0.000)
(四)最速下降法的缺點
由於沿負梯度方向目標函式的最速下降性，很容易使人們誤認為負梯度方向是最理想的搜尋方
向，最速下降法是一種理想的極小化方法。必須指出的是，某點的負梯度方向，通常只是在該店附
近才具有這種最速下降的性質。
在一般情況下，當用最速下降法尋找極小點時，其搜尋路徑呈直角鋸齒狀（圖1-3），在開頭
幾步，目標函式下降較快；但在接近極小點時，收斂速度長久不理想了。特別適當目標函式的等值
線為比較扁平的橢圓時，收斂就更慢了。
圖 1-3
因此，在實用中常將最速下降法和其他方法聯合套用，在前期使用最速下降法，而在接近極小
點時，可改用收斂較快的其他方法。
x(4) O
x(2)
g x(3)
二、最速下降法算法實現
(一)最速下降法程式流程圖
最速下降法的程式流程圖，如圖1-4 所示
圖 1-4
(二)最速下降法程式清單
用 C 語言編寫的最速下降法的程式清單如下。其中R 是梯度模，P是梯度方向的的單位向量，h
是步長，f 是目標函式。
#include “math.h”
開始
給定初始點0
x ÎEn，e > 0
k := 0
計算pk = -Ñf (xk )
pk ￡ e
求 k l 使其滿足
0
min ( k k ) ( k k )
k f x p fx p
l
l l
3
+ = +
令
k 1 k k
k x + = x + l p
輸出： min
x = xk
結束
是
#include “stdio.h”
float x[10],y[10],p[10],f,h;
int n;
vod fun( )
{int i;
for(i=1,i<n;i++) x[i]=y[i]-h*p[i];
f=x[1]*x[1]+x[2]*x[2]-x[1]*x[2]-10*x[1]-4*x[2];
f=f+60;
return;
}
main( )
{float g[10],d[10],q,r,e,h1,h2,h3,h4,t,t0,c1,c2,f1,f2,f3,f4,f5,v;
int i,k,u;
printf(“input n,e\n”)；
scanf(“%d,%f”,&n,&e);
x[1]=0;x[2]=0;
p4: g[1]=2*x[1]-x[2]-10;
g[2]=2*x[2]-x[1]-4;
q=0;
for(i=1;i<n;i++) q=g[i]*g[i]+q;
r=sqrt(q);
for(i=1;i<n;i++) {y[i]=x[i];p[i]=g[i]/r;}
if(r<e)go to p3;
else
{t0=1;v=0.1;h1=0;h=h1
fun( );f1=f;
p2: u=0;t=t0; h2=h1+t;h=h2;
fun( );f2=f;
if(f1>f2) {t=t+t;u=u+1;
else{t=-t;h3=h1;f3=f1;
h1=h2;f1=f2;h2=h3;f2=f3;
p1: h3=h2+t; h=h3;
fun( ) f3=f;
if(f2>f3) {t=t+t;u=u+1;
h1=h2;f1=f2;h2=h3;f2=f3;goto pl;}
else{if(u>0)
{h4=0.5*(h2+h3);h=h4;
fun( );f4=f;
if(f4>f2) {h3=h4;f3=f4;}
else{h1=h2;f1=f2;h2=h4;f2=f4;}
}
c1=（f3-f1）/(h3-h1);
c2=((f2-f1)/(h2-h1)-c1)/(h2-h3);
if(fabs(c2)<e) {h1=h2;f1=f2;t0=v*t0;goto p2;}
else{h4=0.5*(h1+h3-(c1/c2));h=h4;
fun( );f4=f;
if(f2<1) f5=1;
else f5=f2;
if((fabs(f4-f2)/f5)<e)
{for(i=1;i<n;i++) x[i]=y[i]-h4*p[i];
goto p4;
}
else
{if(f4>f2) {h1=h2;f1=f2;}
else {h1=h4;f1=f4;}
t0=v*t0;goto p2;
}
}
}
}
p3:h0;fun( );
printf(“OBJ.FUNC F=%f\n”,f);
for(i=1;i<n;i++)
{printf(“X(%d”,I);
printf(“)=%f\n”,x[i]);
}
}
三、設計總結
接觸最速下降法是在學習運籌學時，它是一種重要的無約束最最佳化方法。是1847 年由著名數
學家Cauchy 給出的，它是解析法中最古老的一種，其他解析方法或是它的變形，或是受它的啟發
而得到的。在進行該題目的畢業設計時，以前學到的知識是遠遠不夠的。我去學校圖書館查閱了大
量的相關書籍，引用了一些比較經典的例題來呈現最速下降法。為了用C 語言實現最速下降法，重
溫了C 語言，上網查閱了相關資料。經過近半年的努力和輔導老師的大力幫助下，我的論文《最速
下降法及其算法實現》完成了。詳細闡釋了最速下降法的基本原理，疊代步驟以及算法的實現，對
最速下降法做了較為深入的研究。
通過這次設計，我重新學習了以前遺忘的知識，加深了記憶和理解。真正做到了理論和實踐相
結合，鍛鍊了自己分析，處理實際問題的能力，也認識到了自己的不足。畢業設計過程中總結到的
經驗和教訓將指導我未來的工作和學習，我會更加努力，取得更大的成績。
參考文獻
[1]趙瑞安，吳方.非線性最最佳化理論和方法.北京:高等教育出版社，1900
[2]袁亞湘，孫文瑜.最最佳化理論與方法.北京：科學出版社，1997
[3]陳開明.非線性規劃.上海：復旦大學出版社，1991
[4]周維，楊鵬飛.運籌學.北京:科學出版社，2008
[5]張瑩，運籌學基礎.北京：清華大學出版社.1994
[6]劉建永，運籌學算法與編程實踐.北京：清華大學出版社.2004
[7]傅鸝，龔劬，劉瓊蓀，何中市.數學實驗.北京：科學出版社.2000

最速下降法

相關詞條

套用最最佳化方法及MATLAB實現

最最佳化

工程最佳化設計與MATLAB實現

神經網路在套用科學和工程中的套用：從基本原理到複雜的模式識別

矩陣計算六講

最最佳化方法與程式設計

精通MATLAB最最佳化計算

現代科學計算

算法最佳化

相關搜尋

熱門詞條