Method of steepest descent 最速下降法
7Method of steepest descent
This technique rst developed by Riemann(1892)1,is extremely useful for han-dling integrals of the form
I(λ)= C eλp(z)q(z)dz
where C is a contour in the complex plane and p(z),q(z)are analytic functions, andλis taken to be real.(Ifλis complex ieλ=|λ|e iαwe can absorb the expo-nential factor into p(z).)We require the behaviour of I(λ)asλ→∞.
The basic idea of the method of steepest descent(or sometimes referred to as the saddle-point method),is that we apply Cauchy's theorem to deform the contour C to contours coinciding with the path of steepest https://www.wendangku.net/doc/eb18231902.html,ually these contours pass through points z=z0where p′(z0)=0.As we will see on the steepest descent contours,?(p(z))is constant and so we are left with integrals of the type which can be handled using Watson's lemma.
Let p(z)=u(x,y)+iv(x,y)be an analytic function of the complex variable z=x+iy in some domain D.Notice that for any path of integration the exponential function
eλp(z)=eλu(x,y)e iλv(x,y)
may have a maximum modulus at some point z=z0on the path.Ideally we would like to choose a path near a point z=z0such that u attains a peak and decreases away from z=z0.But the imaginary part v(x,y)will in general also change and the exponential factor e iλv will oscillate rapidly near z0.
This suggests that a suitable path is one where v(x,y)is nearly constant as we move away from z=z0.Also by the maximum modulus theorem u,v cannot attain maximum or minimum values in a domain if p(z)is analytic,only on the boundary of the region.Thus the point z=z0must coincide with a saddle point where p′(z0)=0.
The method of steepest descent is thus also called the saddle point method. If we consider the surface
u(x,y)=u(x0,y0)
passing through some point z=z0of D then note that?u|z0de nes the direction of steepest ascent from the point z=z0and??u|z0the direction of steepest descent.
Now consider the surface
v(x,y)=v(x0,y0).
We have that?v=(v x,v y)is in a direction normal to the surface.But using the Cauchy-Riemann equations v x=?u y,v y=u x.
1B.Riemann,Gesammelte Mathematische Werke2e Au ,Leipzig,pp.424-430
Thus
?v=(v x,v y)=(?u y,u x).
Hence a direction tangential to the surface is given by
(?v y,v x)=(u x,u y)=?u.
Thus tangents to the surface
v(x,y)=v(x0,y0)
lie in the direction of steepest ascent/descent through z0and the lines of constant u and constant v intersect at right angles in the regions of analyticity of the functions.
Figure2:Typical steepest ascent/descent curves shown by solid/dashed lines near a simple saddle point z=z0
Observe also that for any changeδp
δp=δu+iδv
and so
|δu|≤|δp|
and|δu|is a maximum at z=z0only whenδv=0,ie when v(x,y)=v(x0,y0).
De nition We de ne z=z0to be a saddle point of order N?1if
p′(z0),...p(N?1)(z0)=0,p(N)(z0)=0.
A saddle point or order1is a simple saddle point.
Near z =z 0we have
p (z )=p (z 0)+(z ?z 0)N N !
p (N )
(z 0)+o ((z ?z 0)N ).
Putting z =z 0+ρe iθ,
p (N )(z 0)=ae iα
we have
p (z )?p (z 0)～ρN ae i (Nθ+α)
N !
.
Thus the curves of steepest ascent/descent through z =z 0are given locally by
?(p (z )?p (z 0))=0
=?sin(Nθ+α)=0,
giving Nθ+α=kπ,where k is an integer.In this case
p (z )?p (z 0)=u (x,y )?u (x 0,y 0)～ρN
N !
a cos(Nθ+α).
Thus the curves of steepest descent are given by
θ=?α
N +(2k +1)
πN
k =0,1,2,...,N ?1,since cos(Nθ+α)is then negative and u (x,y )
z =z 0.
The curves of steepest ascent are given by
θ=?αN +2k πN k =0,1,2,...,N ?1,
since cos(Nθ+α)is then positive and u (x,y )>u (x 0,y 0)as we move away from
z =z 0.
Example Consider p (z )=z ?z 3
3.Now p ′(z )=1?z 2and so the critical points where p ′(z )=0are given by z =±1.Also p ′′(z )=?2z and thus p ′′(1)=?2=2e iπ,and p ′′(?1)=2.
Near z =1the directions of steepest descent are given by the directions θ=?π2+(2k +1)π2
,k =0,1ie θ=0,π.Near z =?1the directions of steepest descent are given by the directions θ=π2,3π2
.Consider the point z =1.The steepest descent/ascent curves satisfy
v (x,y )=?(z ?z 33)=y (1?x 2
+y 23
)=v (1,0)=0.
There are two curves of steepest ascent/descent passing through z 0=1.These are y =0and 1?x 2+y 2
3=0.Clearly y =0is the steepest descent curve,see Fig.7.
Next consider the point z=?1.Here the steepest descent/ascent curves
satisfy
v(x,y)=y(1?x2+y2
3
)=v(?1,0)=0.
This time the curve1?x2+y2
3=0is the curve of steepest descent emanating
from x=?1.
Figure3:Plots of the surface and contour levels for u(x,y)=Re(z?z3/3)= u(1,0).The steepest descent path is given by y=0.
Example
Consider p(z)=cosh z?z2
2
.Here
p′(z)=sinh z?z,p′′(z)=cosh z?1,p′′′(z)=sinh z.
Thus z=0is a saddle point of order4and
p′′′′(0)=1,
and the directions of steepest descent areθ=(2k+1)π
4
,k=0,1,2,3.A plot of the surface u(x,y)=?(p(z))?1is shown in Fig.7.
7.1Method of steepest descent-key steps
The key steps in using the method of steepest descent are:
?Identify the saddle points,singular points and endpoints likely to contribute to an estimate for the integral.
?Determine path of steepest descent.It may be the case that there is no continuous path joining the endpoints and one needs two or more steepest descent paths.
?Deform contour making use of Cauchy's theorem.
?Evaluate integral making use of Watson's lemma as appropriate.
The books by Bender&Orszag1,(chapter6),and Bleistein&Handelsmann1 (chapter7)contain many examples which should be studied in detail.
The rst example below is taken from Bender and Orszag.
Example
Consider
I(λ)= 10e iλt log t dt.
Here
p(z)=iz=ix?y.
There are no saddle points.The steepest descent/ascent paths are given by
?(p(z))=x=constant.
Since u(x,y)=?(p(z))=?y,for y>0the curves x=constant are steepest descent paths.
Also note that there is no continuous steepest descent path passing through the two endpoints of the integral x=0and x=1.
This motivates the choice of the contour C1+C2+C3that we deform the original path of integration,see Fig.4.We take a branch cut along the negative real axis for log(z).
Using Cauchy's theorem we can write
10log(t)e iλt dt=? C1+C2+C3e iλz log z dz.
1see references in lecture1
Figure 4:Deformed contour for integral
1
log te iλt dt.
For C 2put z =x +iR and then
C 2
=?
10
log(x +iR )e iλ(x +iR )dx and we see that
|
C 2
|≤e
?Rλ
10
|log(x +iR )|dx
and thus goes to zero as R →∞.For C 1put z =1+iy then
C 1
=i
R 0
log(1+iy )e iλ(1+iy )dy =ie iλ R 0
log(1+iy )e ?yλdy.
For C 3put z =iy then
C 3
=?i
R 0
log(iy )e ?λy dy.
Letting R →∞we nd that I (λ)=i
∞0
e ?λy log(iy )dy ?ie iλ
∞0
log(1+iy )e ?λy dy.
Now
i
∞0
e
?λy
log(iy )dy =i
∞0
e ?λy (log y +
iπ
2
)dy =?π
2λ+i
1λ
∞0
(log(y )?log(λ))e ?y dy,
=?
π2λ?i log λλ+iγλ
where γis the Euler constant and we have used the result that
?γ=
∞
log ye ?y dy.Next applying Watson's lemma to the integral I 1=ie iλ ∞
log(1+iy )?λy dy
gives
I 1～ie
iλ
∞0
∞ n =1
(?1)
n ?1(iy )
n
n
e ?λy dy,
I 1～e
iλ
∞ n =1
(?i )n +1Γ(n +1)
nλn +1
.
Hence putting it all together
I (λ)= 10log(t )e iλt dt ～?i log λλ?2iγ+π2λ+e iλ
∞ n =1(?1)n (i )n +1Γ(n )λn +1.Example
Consider the integral
I (λ)=
12πi
c +i ∞c ?i ∞
e
λ(at ?t 1
2)
t
dt,
where a,c are positive constants and we take a branch cut along the negative real axis.
We require the behaviour of I (λ)as λ→∞.Here
p (t )=at ?t 1
2,
p ′(t )=a ?12t ?1
2,
p ′′(t )=14
t ?3
2.
There is a simple saddle point given by p ′(t )=0ie at t =t 0=1/(4a 2).
Note that p ′′(t 0)=2a 3and so the steepest descent paths have directions θ=π/2,3π/2emanating from the t =t 0.
By Cauchy's theorem we can deform the path of integration to pass through the saddle point as shown in the Fig.5.
Thus to obtain the leading order estimate for the integral,we can approximate the SD path by a straight line in the direction of steepest descent,ie put t =1
4a 2
+iT and note that at ?t 1
2
=?1
4a ?
2a 32
T 2+...,
Figure 5:Original path L is deformed to the steepest descent path SD passing
through the saddle point t =t 0=1/(4a 2).
and
1
t =4a 2+....Thus the integral becomes
I (λ)=12πi
SD
e
λ(at ?t 1
2)
t
dt,～12πi
∞?∞
e ?λ
4a e ?a
3T 2λ
4a 2i dT.
Hence
I (λ)～e ?λ
4a
2a 2
π
∞
?∞
e ?a 3T 2
λdT =2
a πλ
e ?λ
4a .To obtain more terms one needs to work harder.First note that the steepest descent paths satisfy
p (t )=p (t 0)
=?at ?t 1
2=?
14a
,and so the imaginary part of p (t )is zero along these paths.Hence if we put
?W =at ?t 1
2+
14a
where W is real and positive,(because we have a SD path)we nd that
at ?t 1
2+
1
4a
+W =0giving
t =
1±[1?
4a (14a +W )]
12
2a
2
=
1±2a 12W
12
2a
2
.
The±signs here indicate the two steepest directions emanating from t=t0,see Fig.6and by expanding for small W we see that+sign corresponds to theπ/2 direction and the?sign the3π/2direction.We can write
Figure6:The steepest descent paths D+and D?emanating from t=1/4a2.
I(λ)=
1
2πi
D+? D? eλ(?14a?W)t dt dW dW.
Now
dt dW =σ(1+σ2i
√aW)i
2a32
W?12,
whereσ=1for D+andσ=?1for D?.
Also
1 t =4a2(1+2iσ
√aW)?2.
To use Watson's lemma we need the expansion of1
t
dt
dW
as W→0+.Using the
above expression gives
1 t
dt
dW
=
4a2i
2a32
(σW?12+2ia12)(1+2iσa12W12)?2,
～2ia12[σW?12?2ia12?4aσW12+8ia32W+16a2σW32+...]. Here we have used the fact thatσ2=1.Thus
I(λ)～
1
2πi
2a12ie?λ4
∞0e?λW(W?12?2ia12?4aW12+8ia32W+16a2W32+...)dW + ∞0e?λW(W?12+2ia12?4aW12?8ia32W+16a2W32+...)dW ,
Hence
I(λ)～2a12e?λ4
π Γ(12)λ12?4aΓ(32)λ32+16a2Γ(52)λ52+...
,
～2 aπλe?λ4a 1?2aλ+12a2λ2+... ,
asλ→∞.
Example Consider
I(λ)= ∞?∞e iλ(t+t3/3)2t2+1dt.(7.1) Now
p(t)=i(t+t3/3),p′(t)=i(1+t2),p′′(t)=2it.
Hence we have simple saddle points at t=±i and
p(±i)=?2/3,p′′(±i)=?2.
Thus the directions of steepest descent from t=i areθ=0,πand the directions of steepest descent from t=?i areθ=π/2,3π/2.
Next note that if we set t=Re iφthen for large R andλ>0,
e iλ(t+t3/3)～O(e?λR33sin(3φ))
and this decays provided the sin(3φ)term is positive.So if we displace the contour in the upper-half plane the contour should begin and end in the sectors
2π/3<φ<π,and0<φ<π/3.
The steepest descent/ascent paths satisfy
?(p(t))=?(p(±i))=0
giving with t=x+iy,
?[i(x+iy+13(x3+3ix2y?3xy2?iy3))]=x(1+x23?y2).
So the steepest descent paths emanating from t=i are1+x2
3?y2=0and from t=?i are x=0.
Note also that if y2=(x2
3?1)then for large x we have y～±1√3x.A sketch of the path is given in g.7.
The above analysis suggests that we can deform the original contour in(7.1) to the upper-half plane on to the steepest decsent path through t=i,see g.7. Applying Cauchy s theorem we obtain
L1+C1+C2+C3e iλ(t+t3/3)2t2+1dt=2πiRes[t=i/√2],
(a)
(b)
x
y
L 1
i
C 1C 2
C 3
Figure 7:(a)Steepest descent path through t =i (b)Contours for application of Cauchy's theorem.
since the integrand has a simple pole at t =i/√
2.The integrals along C 1,C 3goes to zero for large R and so
L 1
e iλ(t +t 3
/3)
2t 2+1
dt =
?C 2
e iλ(t +t 3
/3)2t 2+1
dt +2πi [
e
iλ(i √
2
?i 6
√2
)
4i √2
].
For the integral along the steepest descent path we can put (for the leading order contribution only)t =i +T to obtain
I (λ)～
∞?∞e λ(?23?T 2)
(?2+1)dT +√22πe ?5λ6√2,～?
πλe ?2λ/3+√22
πe ?5λ6√
2.
最速下降法求解线性代数方程组 要求：对于给定的系数矩阵、右端项和初值，可以求解线性代数方程组 一、最速下降法数学理论 在基本迭代公式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 程序设计实践》课程考核 实践一、编程实现以下科学计算法，并举一例应用之。（参考书籍《精通MATLAB 科学计算》，王正林等著，电子工业出版社，2009年） “最速下降法无约束最优化” 最速下降法： 解： 算法说明：最速下降法是一种沿着N 维目标函数的负梯度方向搜索最小值的方法。 原理：由高等数学知识知道任一点的负梯度方向是函数值在该点下降最快的方向，那么利用负梯度作为极值搜索方向，达到搜寻区间最速下降的目的。而极值点导数性质，知道该点的梯度=0，故而其终止条件也就是梯度逼近于0，也就是当搜寻区间非常逼近极值点时，即：当▽f(a ）→0推出f(a ）→极值）（x f ，f(a ）即为所求。该方法是一种局部极值搜寻方法。 函数的负梯度表示如下： -g(x ）=-▽f(x)=-?????1 )(x x f 2)(x x f ?? … T N x x f ?????)( 搜索步长可调整，通常记为αk （第k 次迭代中的步长）。该算法利用一维的线性搜索方法，如二次逼近法，沿着负梯度方向不断搜索函数的较小值，从而找到最优解。 方法特点（1）初始值可任选，每次迭代计算量小，存储量少，程序简短。即使从一个不好的初始点出发，开始的几步迭代，目标函数值下降很快，然后慢慢逼近局部极小点。（2）任意相邻两点的搜索方向是正交的，它的迭代路径胃绕道逼近极小点。当迭代点接近极小点时，步长变得很小，越走越慢。（3）全局收敛，线性收敛，易产生扭摆现象而造成早停。 算法步骤：最速下降法的基本求解流程如下： 第一步 迭代次数初始化为k=0，求出初始点0x 的函数值f 0=f （0x ）。 第二步 迭代次数加1，即k=k+1，用一维线性搜索方法确定沿负梯度方向-1-k g 的步长1k -α，其中1k -α=ArgMinaf （111k /----k k g g x α）。 第三步 沿着负梯度方向寻找下一个接近最小值的点，其中步长为1k -α，得到下一点的坐标为：1111/-----=k k k k k g g x 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 =-。 步骤3：从()k x 出发，沿方向()k d 进行非精确一位搜索，求得可接受步长()k α。 步骤4：计算下一个迭代点(1)()()()k k k k x x d α+=+及对应的目标函数值(1)()k f x +。 步骤5：若满足(1)()k k x x tol +-<，则终止迭代，分别输出(1)k x +和(1)()k f x +作为该问题的极小点和极小值；否则令:1k k =+，转步骤2. 四、最速下降法的流程图 最速下降法的流程图如下图所示
最速下降法Matlab实现 实验目的： 1.掌握迭代法求解无约束最优化问题的基本思想 2.通过实验掌握最速下降法的Matlab算法的基本步骤 实验内容： 1.迭代法求解无约束最优化问题的基本思想 给定一个初始点x(0), 按照某一迭代规则产生一个迭代序列{x(k)}. 使得若该序列是有限的, 则最后一个点就是原问题的极小点; 否则, 若序列{x(k)} 是无穷点列时, 它有极限点且这个极限点即为原问题的极小点. 设x(k) 为第k 次迭代点, d(k) 为第k 次搜索方向, a(k)为第k 次步长因子, 则第k 次迭代完成后可得到新一轮(第k + 1 次) 的迭代点 x(k+1) = x(k) + a(k) d(k). 2.无约束优化问题迭代算法的一般框架 步0 给定初始化参数及初始迭代点x(0). 置k := 0. 步1 若x(k) 满足某种终止准则, 停止迭代, 以x(k) 作为近似极小点. 步2 通过求解x(k) 处的某个子问题确定下降方向d(k). 步3 通过某种搜索方式确定步长因子a(k), 使得f(x(k) + a(k) d(k)) < f(x(k)). 步4 令x(k+1) := x(k) + a(k) d(k), k := k + 1, 转步1. 3. 最速下降法的基本步骤 步0 选取初始点x(0) ∈R^n, 容许误差0 ≤e ?1. 令k := 1. 步1 计算g(k) = ?f(x(k)). 若‖g(k)‖≤e, 停算, 输出x(k)作为近似最优解. 步2 取方向d(k)= ?g(k). 步3 由线搜索技术确定步长因子a(k),即 min f(a(k))=f(x(k)+a(k)d(k)). 步4 令x(k+1) := x(k) + a(k)d(k)), k := k + 1, 转步1.
数学与计算科学学院 实验报告 实验项目名称使用精确搜索算法确定步长的最速下降法 所属课程名称最优化方法 实验类型算法编程 实验日期 201 班级 学号 姓名 成绩 一、实验概述： 【实验目的】
(1) 掌握精确搜索算法确定步长的最速下降法； (2) 使用计算机语言表达最优化方法。 【实验原理】 最速下降法又称为梯度法，是1847年由著名数学家Cauchy 给出的。他是解析法中最古老的一种，其他解析方法或是它的变形，或是受它的启发而得到的，因此它是最优化方法的基础。 设无约束问题中的目标函数 f : Rn R1一阶连续可微。 最速下降法的基本思想是：从当前点k x 出发，取函数 f (x)在点k x 处下降最快的方向作为我们的搜索方向k p .由 f (x)的 Taylor 展式知 ()()()() k k k k T k k f x f x tp t f x p o tp -+=-?+ 略去t 的高阶无穷小项不计，可见取()k k p f x =-?时，函数值下降得最多。于是，我们可以构造出最速下降法的迭代步骤。 解无约束问题的的最速下降法计算步骤 第 1 步 选取初始点(0)x ，给定终止误差ε ，令k:=0； 第 2 步 计算?f (k x )，，若‖?f (k x )‖≤ ε ，停止迭代.输出k x .否则 进行第三步 第 3 步 取()k k p f x =-?； 第 4 步进行一维搜索，求k t ，使得 1()(())min (()) k k k k k k f x f x t f x f x t f x +=-?=-? 令,k:=k+1，转第2 步。 由以上计算步骤可知，最速下降法迭代终止时，求得的是目标函数驻点的一个近似点。 【实验环境】 计算机 VC++
共轭梯度法 一 共轭梯度法原理 对于线性方程组A b X =，即： 1111221n 12112222n 21122nn n n n n n n a x a x a x b a x a x a x b a x a x a x b +++=??+++=????++ += ? （1） 其中，()=ij n n a ?A 为对称正定矩阵，()1i n b b ?=，如何熟练地运 用最速下降法与共轭梯度法的求解线性方程组。 在求解线性方程组之前，首先用内积将问题转化为函数问题。 1 最速下降法 最速下降法是一种运用梯度与极值的性质，综合数值计算方法寻找局部极值。 基本思想：任一点的负梯度方向是函数值在该点下降最快的方向。将n 维问题转化为一系列沿负梯度方向用一维搜索方法寻优的问题，利用负梯度作为搜索方向，故称最速下降法。 具体步骤： 1、搜索方向：()k k d f x =-?，即最速下降方向。 2、搜索步长：k λ取最优步长，即满足： ()min ()k k k k k f x d f x d λ λλ+=+ 1 给定初始点0n x R ∈，允许误差0ε≥，令1k =。 2 计算搜索方向()k k d f x =-?。 3 若k d ε≤，则k x 为所求的极值点，否则，求解最优步长k λ，使得()min ()k k k k k f x d f x d λ λλ+=+。
4 令1k k k k x x d λ+=+，1k k =+ 最速下降方向是反映了目标函数的局部性质，它只是局部目标函数值下降最快的方向。 2 共轭梯度法 对于1 min ()2T T f x x Ax b x =+ 其中，0n x R ∈，A 是对称正定矩阵。 基本思想：将共轭性与最速下降法相结合利用已知迭代点的梯度方向构造一组共轭方向，并沿此方向搜索，求出函数的极小值。 具体步骤： 1 取初始点(0)x ，取第一次搜索方向为(0)(0)()d f x =-?。 2 设已求得(1) k x +，若(1) ()0k f x +?≠，令(1) ()()k g x f x +=? ，则下一个 搜索方向 (1)()1k k k k d g d β++=-+ （1） 由于(1) k d +与() k d 关于A 共轭，所以给（1）两边同时乘以()T k d A ， 即： ()(1)()()()10T T T k k k k k k k d d d g d d β++A =-A +A = 解得：()1()() k T k k k T k d A g d Ad β+= （2） 3 搜索步长的确定，已知迭代点()k x ，和搜索方向()k d ，确定 步长k λ，即：()()min ()k k f x d λ λ+ 记 ()()()()k k f x d φλλ=+， 令 ()()()()()0k k T k f x d d φλλ'=?+= 既有：()()()[()]0k k T k A x d b d λ++=
最速下降法 %% 最速下降法图示 % 设置步长为0.1，f_change为改变前后的y值变化，仅设置了一个退出条件。syms x;f=x^2; step=0.1;x=2;k=0; %设置步长,初始值,迭代记录数 f_change=x^2; %初始化差值 f_current=x^2; %计算当前函数值 ezplot(@(x,f)f-x.^2) %画出函数图像 axis([-2,2,-0.2,3]) %固定坐标轴 hold on while f_change>0.000000001 %设置条件，两次计算的值之差小于某个数，跳出循环 x=x-step*2*x; %-2*x为梯度反方向，step为步长，！最速下降法！ f_change = f_current - x^2; %计算两次函数值之差 f_current = x^2 ; %重新计算当前的函数值 plot(x,f_current,'ro','markersize',7) %标记当前的位置 drawnow;pause(0.2); k=k+1; end hold off fprintf('在迭代%d次后找到函数最小值为%e，对应的x值为%e\n',k,x^2,x)
wolfe准则 unction [alpha, newxk, fk, newfk] = wolfe(xk, dk) rho = 0.25; sigma = 0.75; alpha = 1; a = 0; b = Inf; while (1) if ~(fun(xk+alpha*dk)<=fun(xk)+rho*alpha*gfun(xk)'*dk) b = alpha; alpha = (alpha+a)/2; continue; end if ~(gfun(xk+alpha*dk)'*dk>= sigma*gfun(xk)'*dk) a = alpha; alpha = min([2*alpha, (b+alpha)/2]); continue; end break; end newxk = xk+alpha*dk; fk = fun(xk); newfk = fun(newxk);
实验的题目和要求 一、所属课程名称： 最优化方法 二、实验日期: 20１０年5月１0日~２010年5月１５日 三、实验目的 掌握最速下降法,牛顿法和共轭梯度法的算法思想，并能上机编程实现相应的算法。 二、实验要求 用ＭA ＴLA Ｂ实现最速下降法，牛顿法和共轭梯度法求解实例。 四、实验原理 最速下降法是以负梯度方向最为下降方向的极小化算法，相邻两次的搜索方向是互相直交的。牛顿法是利用目标函数)(x f 在迭代点k x 处的T ａylor 展开式作为模型函数,并利用这个二次模型函数的极 小点序列去逼近目标函数的极小点。共轭梯度法它的每一个搜索方向是互相共轭的，而这些搜索方向k d 仅仅是负梯度方向k g -与上一次接 待的搜索方向1-k d 的组合。 五.运行及结果如下： 最速下降法: 题目：f=（x-2）^２+(y-４）^2 Ｍ文件： fu ｎcti ｏn [R,n]=stee ｌ（x0,y0，e ｐs) syms ｘ； syms y ; f=(x-2)^2+(ｙ-４）^2; ｖ=[x,y]; ｊ＝ｊac ｏbi ａｎ(f ，v); T=[s ｕbs(j(１),ｘ,x0）,subs （j （2),ｙ，y0)]; temp=s ｑrt((Ｔ(1)）^2＋(T （2))＾2); x １＝x0;y １=y ０; ｎ=0; sym ｓ k ｋ; w ｈi ｌe (temp>eps ） ｄ=－Ｔ； ｆ1=x １+kk*d(1);f2=ｙ1+k ｋ*ｄ（２); fT=[su ｂs(j （1),ｘ,ｆ１),ｓｕb ｓ(j(2),ｙ,ｆ2)]; fu ｎ=sqrt((fT(1））^2+(ｆT(2)）^２）;
第五题： 解：选择类型为： 2/13()x t y t x e x =+ 其中123,,x x x 是待求参数。根据最小二乘原理，参数123,,x x x 是下面优化问题的解。 []2 8 1231 m in (,,)()i i i f x x x y t y == -? 用最速下降法求解这一无约束的最优化问题。 zuiyouhua.m function sh=zuiyouhua(x0) % x0为初始猜测值 syms x y z a al; %====================================== t=[0.2,1,2,3,5,7,11,16]; r1=[5.05,8.88,11.63,12.93,14.15,14.73,15.30,15.60]; minf=0; for i=1:8 r(i)=x*exp(y/t(i))+z-r1(i); %构造最小二乘最优化的目标函数 minf=r(i)^2+minf; end %====================================== f1=diff(minf,x); f2=diff(minf,y); f3=diff(minf,z); %求目标函数的梯度 F=[f1,f2,f3]; %====================================== Fx1= -subs(F,{x,y,z},x0); Fx=Fx1/norm(Fx1); k=0; %====================================== %最速下降法核心迭代程序 while 1 x1=x0+a*Fx; P=subs(minf,{x,y,z},x1); xx1=xianxing(P); %调用线性搜索函数 al=huangjing(P,xx1); %调用黄金分割法函数； x0=x0+al*Fx; Fx1= -subs(F,{x,y,z},x0); Fx=Fx1/norm(Fx1); if norm(Fx1)<5e-4 sh=x0; return; end end %====================================== function xx=xianxing(Pa) %一维搜索法线性搜索函数 aa=findsym(Pa); a1=1; h=0.5; k=0; t1=2; while 1 a2=a1+h; Pa1=subs(Pa,aa,a1); Pa2=subs(Pa,aa,a2); if Pa2< Pa1 h=t1*h; a0=a1; a1=a2; k=k+1; if k>1000 disp('迭代步数太多，可能不收敛！'); end else if k==0 h=-h; a0=a2; else c1=min(a0,a2); d1=max(a0,a2); xx=[c1,d1]; return; end end end %====================================== function al1=huangjing(Pb,xx2)
最速下降法与牛顿法及其区别 摘要：无约束优化方法是优化技术中极为重要和基本内容之一。它不仅可以直接用来求解无约束优化问题，而且很多约束优化问题也常将其转化为无约束优化问题，然后用无约束优化方法来求解。最速下降法和牛顿法是比较常见的求解无约束问题的最优化方法，这两种算法作为基本算法，在最优化方法中占有重要的地位。其中最速下降法又称梯度法，其优点是工作量少，存储变量较少，初始点要求不高；缺点是收敛慢，效率低。牛顿法的优点是收敛速度快；缺点是对初始点要求严格，方向构造困难，计算复杂且占用内存较大。同时，这两种算法的理论和方法渗透到许多方面，特别是在军事、经济、管理、生产过程自动化、工程设计和产品优化设计等方面都有着重要的应用。因此，研究最速下降法和牛顿法的原理及其算法对我们有着及其重要的意义。 关键字：无约束优化最速下降法牛顿法 Abstract: unconstrained optimization method is to optimize the technology is extremely important and basic content of. It not only can be directly used to solve unconstrained optimization problems, and a lot of constrained optimization problems are often transformed into unconstrained optimization problem, and then use the unconstrained optimization methods to solve. The steepest descent method and Newton-Raphson method is relatively common in the unconstrained problem optimization method, these two kinds of algorithm as the basic algorithm, the optimization method plays an important role in. One of the steepest descent method also known as gradient method, its advantages are less workload, storage variable is less, the initial requirements is not high; drawback is the slow convergence, low efficiency. Newtonian method has the advantages of fast convergence speed; drawback is the initial point of strict construction difficulties, directions, complicated calculation and larger memory. At the same time, these two kinds of algorithm theory and methods into many aspects, especially in the military, economic, management, production process automation, engineering design and product optimization design has important applications. Therefore, to study the steepest descent method and Newton-Raphson method principle and algorithm for us with its important significance. Keywords: unconstrained optimization steepest descent method
梯度法（又名,最速下降法） (该法总可以收敛，但是，在接近真解时收敛的速度会放慢。) 梯度法又称为最速下降法，用于求解实系数非线性方程组 12(,,,)0, 1,2,,i n f x x x i n == （7－15） 的一组根。梯度法首先是定义一个目标函数 2 12121 (,,,)(,,,) n n i n i x x x f x x x =Φ= ∑ （7－16） 使目标函数2 1 n i i f =Φ= ∑ 达到最小的12,,,n x x x 是我们寻找的一组解，这是非 线性最小二乘法问题。 如果第(0,1,2,)k k = 步求得一组解1 2 ,,,n k k k x x x ，使得 12(,,,)n k k k x x x ε Φ< （7－17） 则认为1 2 ,,,n k k k x x x 是原方程组满足一定精度的()ε要求的一组解。 梯度法的计算过程是： （1）先给定一组不全为零的初值1 2 000,,,n x x x ，第k 步的一组根为1 2 ,,,n k k k x x x ； （2）计算目标函数1 2 (,,,)n k k k x x x Φ 的值；(单独子程序:fn =TargetFunction) （3）若1 2 (,,,)n k k k x x x εΦ< ，则认为1 2 ,,,n k k k x x x 是满足一定精度()ε的一组 解，否则，作如下修正计算 1 α +=?Φ=-?i k i i k k k i i x x x x x （7－18） 其中
121212********* 1111222 (,,,) (,,,)(,,,)(,,,)(,,,)(,,,)(,,,)*,1,2,,α ==?Φ= ??? ??Φ ? ? ???Φ+-Φ?Φ=??Φ+-Φ?Φ= ?Φ+-Φ?Φ = ?==∑ n k j j n n n n n n k k k k n j j x x k k k k k k k k k k k k k k k k k k n n n k i 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 ）。 （4）重复修正1 k i x +，直到 12111 (,,,)n k k k ε +++ΦΦΦ< ，计算终止。
牛顿法 迭代公式：(1)2()1()[()]()k k k k x x f x f x +-=-?? Matlab 代码： function [x1,k] =newton(x1,eps) hs=inline('(x-1)^4+y^2'); 写入函数 ezcontour(hs,[-10 10 -10 10]); 建立坐标系 hold on; 显示图像 syms x y 定义变量 f=(x-1)^4+y^2; 定义函数 grad1=jacobian(f,[x,y]); 求f 的一阶梯度 grad2=jacobian(grad1,[x,y]); 求f 的二阶梯度 k=0; 迭代初始值 while 1 循环 grad1z=subs(subs(grad1,x,x1(1)),y,x1(2)); 给f 一阶梯度赋初值 grad2z=subs(subs(grad2,x,x1(1)),y,x1(2)); 给f 二阶梯度赋初值 x2=x1-inv(grad2z)*(grad1z)'; 核心迭代公式 if norm(x1-x2) end end end 优点：在极小点附近收敛快 缺点：但是要计算目标函数的hesse 矩阵 最速下降法 1. ：选取初始点xo ，给定误差 2. 计算一阶梯度。若一阶梯度小于误差，停止迭代，输出 3. 取()()()k k p f x =? 4. 10 t ()(), 1.min k k k k k k k k k k t f x t p f x tp x x t p k k +≥+=+=+=+进行一维搜索，求，使得令转第二步 例题： 求min (x-2)^4+(x-2*y)^2.初始值（0,3）误差为0.1 (1)编写一个目标函数，存为f.m function z = f( x,y ) z=(x-2.0)^4+(x-2.0*y)^2; end (2)分别关于x 和y 求出一阶梯度，分别存为fx.m 和fy.m function z = fx( x,y ) z=2.0*x-4.0*y+4.0*(x-2.0)^3; end 和 function z = fy( x,y ) 最速下降算法 syms x1 x2; X=[x1,x2]; f=X(1)^2+X(2)^2-4*X(1)-6*X(2)+20; fd1=[diff(f,x1) diff(f,x2)]; x=[2 3]; g=0; e=1E-5; a=1; p=subs(fd1,[x1 x2],[x(1) x(2)]); tep=0; while g>e tep=tep+1; dk=-p; t=((2*x(1)-4)*dk(1)+(2*x(2)-6)*dk(2))/(dk(1)*dk(2)-2*dk(1)^2-2*dk(2)^2); xu=x+t*dk; x=xu; g=0; for i=1:length(fan) g=g+fan(i)^2; end g=sqrt(g); end fv=subs(f,[x1 x2],[x(1) x(2)]); fprintf('\n最优点时的自变量：函数的最值：\n [x(1),x(2)]=[ %d %d ] fv=%d\n',x(1),x(2),fv); 2.无约束优化问题最速下降法的c程序,以如下问题为例: min f(x)=2*1^2+4*2^2 初值,x=(1,1). 程序如下: #include 随着人工智能、模糊控制、模式识别、人工网络等新技术的应用和发 展。可以让它们与广义预测控制相结合，建立高精度、多模态的预测模型。 使广义预测控制在异常情况下可以稳定运行，推进广义预测控制的进一步 发展。 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)的最优解了。综上所述，让步长“R =1即“*恒 取常数是不合适的。经过研究学者们发现了一个方法可以改善这个情况，那就是利用 已有的线搜索方法来确定步长因子，也就是步长因子是可变的。其迭代格式为 x1. }, = x:一a}.OZ f (x}.)一，Of (x,. ) C 2-6 ) 2.2.2牛顿法 牛顿法也是无约束最优化问题中的一种经典算法，它是利用目标函数.f (x)的二 次泰勒展开式，并将二次泰勒展开式进行极小化。其迭代格式为 x}+i=xA+d}(2-5) 其中步长因子。、=l} d、为02f (x} )d + Of (xA ) = 0的解。当目标函数f(x)是正定二次函数的时候，牛顿法可以一步达到最优解;当目标函数f (x)是非二次函数的时候， 牛顿法经过有限次迭代之后就不能确保求得目标函数f (x)的最优解。我们知道目标 函数f (x)在极小点附近是很接近于二次函数的，所以，假如初始点非常靠近无约束 . 数学与计算科学学院 实验报告 实验项目名称使用精确搜索算法确定步长的最速下降法所属课程名称最优化方法 实验类型算法编程 实验日期 201 班级 学号 姓名 成绩 【实验目的】 (1) 掌握精确搜索算法确定步长的最速下降法； (2) 使用计算机语言表达最优化方法。 【实验原理】 最速下降法又称为梯度法，是1847年由著名数学家Cauchy 给出的。他是解析法中最古老的一种，其他解析方法或是它的变形，或是受它的启发而得到的，因此它是最优化方法的基础。 设无约束问题中的目标函数 f : Rn R1一阶连续可微。 最速下降法的基本思想是：从当前点k x 出发，取函数 f (x)在点k x 处下降最快的方向作为我们的搜索方向k p .由 f (x)的 Taylor 展式知 ()()()() k k k k T k k f x f x tp t f x p o tp -+=-?+ 略去t 的高阶无穷小项不计，可见取()k k p f x =-?时，函数值下降得最多。于是，我们可以构造出最速下降法的迭代步骤。 解无约束问题的的最速下降法计算步骤 第 1 步 选取初始点(0)x ，给定终止误差ε ，令k:=0； 第 2 步 计算 f (k x )，，若‖ f (k x )‖ε ，停止迭代.输出k x . 否则进行第三步 第 3 步 取()k k p f x =-?； 第 4 步进行一维搜索，求k t ，使得 1()(())min (()) k k k k k k f x f x t f x f x t f x +=-?=-? 令,k:=k+1，转第2 步。 由以上计算步骤可知，最速下降法迭代终止时，求得的是目标函数驻点的一个近似点。 【实验环境】 计算机 VC++ 二、实验内容： 【实验方案】 1. 列举例题 2. 手工计算 3. 将计算步骤等实现程序化 4. 实验结果分析 梯度下降法、牛顿迭代法、共轭梯度法 （参见：神经网络->PGM-ANN-2009-C09性能优化） 优化的目的是求出目标函数的最大值点或者最小值点，这里讨论的是迭代的方法 梯度下降法 首先，给定一个初始猜测值 ，然后按照等式 k k k k ΡαΧ+=X +1 （1） 或 k k k k k P =X -X =?X +α)(1 （2） 逐步修改猜测。这里向量 k P 代表一个搜索方向，一个大于零的纯量 k α 为学习 速度，它确定了学习步长。 当用 k k k k ΡαΧ+=X +1 进行最优点迭代时，函数应该在每次迭代时都减小，即 ) ()(1k k F F X 1.最速下降法 #include "stdio.h" #include "math.h" double fun1(double x1,double x2) /*定义函数fun1为目标函数*/ {double y; y=x1*x1-2*x1*x2+4*x2*x2+x1-3*x2; return y; } void main() { double t, x1=1, x2=1,e=0.01, g[2], y, m; int k=1; /*定义起始点为x1=0，x2=1，并定义精度为e=0.01*/ g[0]=2*x1-2*x2+1; /*目标函数对x1求偏导*/ g[1]=(-2)*x1+8*x2-3; /*目标函数对x2求偏导*/ m=(sqrt(g[0]*g[0]+g[1]*g[1])); /*对g[0]*g[0]+g[1]*g[1]求开方，将值赋给m*/ while(m>e&&k<=200) /*判断，当m>e时进行以下循环*/ { t=((2*g[1]-2*g[0])*x1+(2*g[0]-8*g[1])*x2-g[0]+3*g[1])/(4*g[0]*g[1]-2*g[0]*g[0]-8*g[1]*g[1] ); /*根据梯度法（最速下降法），利用梯度和海赛矩阵*/ x1=x1-g[0]*t; /*求步长t。根据步长和梯度方向求出新的x1，x2*/ x2=x2-g[1]*t; printf("迭代次数%d\n",k); printf("搜索方向-%f,-%f,负梯度的模%f,步长%f\n",g[0],g[1],m,t); printf("x的值%f,%f\n",x1,x2); g[0]=2*x1-2*x2+1; g[1]=(-2)*x1+8*x2-3; m=(sqrt(g[0]*g[0]+g[1]*g[1])); /*计算新的m*/ printf("新的负梯度的模%f\n",m); k++; } y=fun1(x1,x2); /*当m不满足m>e的时候退出循环，并计算fun1,*/ printf("分别输出x1,x2 %f,%f\n",x1,x2); /*将值赋给y,并输出。*/ printf("极小值y%f",y); } 1. 算法原理 最速下降法的搜索法向是目标函数的负梯度方向，最速下降法从目标函数的负梯度方向一直前进，直到到达目标函数的最低点。 已知目标函数在()k X 点的梯度为： ()() () ()()() () ()12 ... T k k k k n f X f X f X f X x x x ?? ???? ??=?????? ? 当求目标函数的最小点时，由于函数沿负梯度方向下降最快，故在()k X 点的探索方向应取该点的负梯度方向，即 ()() ()()() k k k f X S f X ?=- ? 显然，()k S 为单位向量。这样第1k +次迭代计算所得的新点为 () () ()()(1)()()()()() k k k k k k k k f X X X S X f X αα+?=+=- ? 负梯度仅给出了最优化方向，而没有给出步长的大小，所以可能有各种各样的最速下降的过程，它们依赖于 () () () k k f X α?的大小。 步长()k α有两种取法： 一种方法是任意给定一个初始步长，使满足条件： ()()()()()()k k k k f X S f X α+< 另外一种方法是沿负梯度方向做一维探索，以求解一维最优化问题的最优步长α，即对目标函数极小，以得到最优步长： ()()()()()0 min ()()k k k k k f X S f X S ααα>+=+ 以此最优步长作为由() k X 点出发沿该点的负梯度方向探索的步长() k α 。 这种方法的迭代计算的收敛性，可用以下三式中的任一式或二式作为准则来进行判断： ()()()()()1()(1) 2()() (1) 3k k k k k k f X f X f X f X X X εεε--??≤? ?-?≤?? ?-≤?? 2. 算法步骤 用最速下降法求无约束多维极值问题min (),n f x x R ∈的算法步骤如下： （1） 取初始点 (0)x ，精度0ε>，令0k = （2） 计算搜索方向() ()()k k v f x =-?，其中()()k f x ?表示函数()f x 在点()k x 处的梯 度； （3） 若()k v ε≤，则停止计算；否则，从()k x 出发，沿()k v 进行一维搜索，即求k λ， 使得() ()()()0 ()min ()k k k k k f x v f x v λλλ≥+=+。此处的一维搜索可以用黄金分割 法等算法，当然也可以用MATLAB 的min f bnd 函数； （4） 令(1) ()(),1k k k k x x v k k λ+=+=+，转步骤（2）。 3. 算法的MATLAB 实现 在MATLAB 中编程实现的最速下降法函数为：min FD 功能：用最速下降法求解多维函数的极值。 调用格式：[,min ]min (,0,var,)x f FD f x eps = 其中，f ：为目标函数； 0x ：初始点； var ：自变量向量； eps ：精度； x ：目标函数取最小值时的自变量值； min f ：目标函数的最小值。 最速下降法的MATLAB 程序代码如下：
- 最优化Armijo算法确定步长的最速下降法
- 最优化Armijo算法确定步长的最速下降法汇总
- 最优化之最速下降法
- 使用精确搜索算法确定步长的最速下降法
- 最优化方法第二章_线搜索算法_最速下降法
- 最速下降法原理及例题实例
- 最优化方法-最速下降法
- 最优化方3.3法最速下降法(梯度法)
- (完整版)最优化毕业课程设计—最速下降法
- 最优化之最速下降法.
- 最速下降法.
- 最优化：最速下降法和Newton法
- 无约束优化方法(最速下降法_牛顿法)
- 最优化之最速下降法PPT课件
- 最优化之最速下降法.
- 使用精确搜索算法确定步长的最速下降法
- 最优化Armijo算法确定步长的最速下降法分解
- 最优化算法实验3-最速下降法
- 最优化牛顿法最速下降法共轭梯度法matlab代码
- 最速下降法-最优化方法