关于无约束优化各种方法
- 格式:ppt
- 大小:4.29 MB
- 文档页数:123
无约束优化方法1. 最速下降法(Gradient Descent Method)最速下降法是一种基于梯度信息的迭代优化算法。
其基本思想是从任意初始点开始,沿着目标函数的梯度方向进行迭代,直到达到收敛条件。
最速下降法的迭代更新公式如下:x_{k+1}=x_k-t_k*∇f(x_k)其中,x_k是第k次迭代的解向量,t_k是第k次迭代的步长(也称为学习率),∇f(x_k)是目标函数在x_k处的梯度向量。
最速下降法的步骤如下:1)选取初始点x_0。
2)计算目标函数的梯度∇f(x_k)。
3)计算步长t_k。
4)更新解向量x_{k+1}。
5)判断迭代终止条件,如果满足则停止迭代;否则返回第2步。
最速下降法的优点是易于实现和理解,收敛性较好。
然而,最速下降法存在的问题是收敛速度较慢,特别是对于目标函数呈现狭长或弯曲形状的情况下。
这导致了在高维优化问题中,最速下降法的性能较差。
2. 牛顿法(Newton's Method)牛顿法是一种基于二阶导数信息的迭代优化算法。
它使用目标函数的一阶和二阶导数信息构造一个二次近似模型,然后求解该模型的最小值。
牛顿法的迭代更新公式如下:x_{k+1}=x_k-H_k^{-1}*∇f(x_k)其中,H_k是目标函数在x_k处的海森矩阵,∇f(x_k)是目标函数在x_k处的梯度向量。
牛顿法的步骤如下:1)选取初始点x_0。
2)计算目标函数的梯度∇f(x_k)和海森矩阵H_k。
3)计算更新方向H_k^{-1}*∇f(x_k)。
4)更新解向量x_{k+1}。
5)判断迭代终止条件,如果满足则停止迭代;否则返回第2步。
牛顿法的优点是收敛速度快,尤其是在目标函数曲率大的地方。
然而,牛顿法也存在一些问题。
首先,计算海森矩阵需要大量的计算资源,特别是在高维空间中。
其次,当海森矩阵不可逆或近似不可逆时,牛顿法可能会失效。
综上所述,最速下降法和牛顿法是两种常用的无约束优化方法。
最速下降法简单易实现,但收敛速度较慢;牛顿法收敛速度快,但计算量大且可能遇到海森矩阵不可逆的问题。
无约束优化方法
**一、最速下降法**
最速下降法(Gradient Descent)是一种迭代优化方法,它是在梯度下降算法的基础上,通过更新梯度的方式来实现最优化目标的过程。
它的思想是:从一个初始点出发,沿着梯度方向,使得目标函数值在末尾尽可能的小。
它可以用来优化非线性的最优化问题,此外,它还可以用于估计函数的最小值。
最速下降法中的基本概念是梯度和梯度下降。
梯度描述了梯度函数的变化情况,它可以衡量函数值在特定点的变化程度。
如果梯度更大,则说明函数值发生的变化更大。
梯度下降是按照梯度的反方向进行函数的,它的目标是出函数值较小的点,也就是最优解。
最速下降法的两个基本步骤是:
1)当前点求梯度之后,按梯度负方向,沿着函数曲面降低。
2)每次迭代,都是沿着相反于梯度的方向,更新当前点,并继续。
最速下降法的优势在于:它比较简单,实现方便,只需要计算梯度,就可以出最优解;且它不需要考虑约束条件,也不需要研究局部最优点,所以它的速度比较快。
但最速下降法也有一些缺点:它有可能陷入局部最优;它缺乏判断能力,只能当前梯度的方向。
第四章 无约束优化方法第一节 概述1为什么要研究无约束优化问题?(1)有些实际问题,其数学模型本身就是一个无约束优化问题。
(2)通过熟悉它的解法可以为研究约束优化问题打下良好的基础。
(3)约束优化问题的求解可以通过一系列无约束优化方法来达到。
所以无约束优化问题的解法是优化设计方法的基本组成部分,也是优化方法的基础。
2各种无约束优化方法的区别在于确定其搜索方向0d 的方法不同。
根据构成搜索方向所使用的信息性质的不同,无约束优化方法可以分为两类。
一:间接法——要使用导数的无约束优化方法,如梯度法、(阻尼)牛顿法、变尺度法、共轭梯度法等。
二:直接法——只利用目标函数值的无约束优化问题,如坐标轮换法、鲍威尔法单纯形法等。
第二节 最速下降法(梯度法) 1基本思想:函数的负梯度方向是函数值在该点下降最快的方向。
将n 维问题转化为一系列沿负梯度方向用一维搜索方法寻优的问题,利用负梯度作为搜索方向,故称最速下降法或梯度法。
2梯度法的特点:(1)理论明确,程序简单,对初始点要求不严格。
(2)对一般函数而言,梯度法的收敛速度并不快,因为最速下降方向仅仅是指某点的一个局部性质。
(3)梯度法相邻两次搜索方向的正交性,决定了迭代全过程的搜索路线呈锯齿状,在远离极小点时逼近速度较快,而在接近极小点时逼近速度较慢。
(4)梯度法的收敛速度与目标函数的性质密切相关。
对于等值线(面)为同心圆(球)的目标函数,一次搜索即可达到极小点。
3选用原则及条件:一般与其他算法配合,在迭代开始时使用。
第三节 牛顿型方法 1基本思想:在xk 邻域内用一个二次函数)(x ϕ来近似代替原目标函数,并将)(x ϕ的极小点作为对目标函数)(x f 求优的下一个迭代点1+k x 。
经多次迭代,使之逼近目标函数)(x f 的极小点。
2牛顿型方法的特点:(1) 初始点应选在X *附近,有一定难度;(2) 若迭代点的海赛矩阵为奇异,则无法求逆矩阵,不能构造牛顿法方向; (3) 不仅要计算梯度,还要求海赛矩阵及其逆矩阵,计算量和存储量大。
⽆约束最优化的常⽤⽅法11/22/2017 12:40:56 PM优化问题在很多领域有着重要的应⽤。
为了⽇后查阅⽅便,本⽂列举常见的⽆约束优化⽅法的计算公式。
需要说明的是,本⽂的⼤部分内容选⾃图书《算法笔记》。
⼀、梯度下降法梯度下降法(Gradient Descent Method)也叫做最速下降法(Steepest Descent Method),因为负梯度是函数局部下降最快的⽅向。
梯度下降梯度下降法的迭代格式为x k+1=x k−αk∇f(x k)梯度下降法⾮常简单,只需要知道如何计算⽬标函数的梯度就可以写出迭代格式。
因此,尽管在不少情况下梯度下降法的收敛速度都很慢,也依然不影响它在⼯业界的⼴泛应⽤。
梯度下降法应⽤到⼀些具体模型上有时也会被视作⼀类特定的算法,例如神经⽹络中的后向传导算法(Back Propagation Algorithm)。
随机梯度下降在机器学习中经常有f(x)=∑m i=1ℓi(x),其中ℓi(x)是第i个训练样本的损失函数。
这时我们可以使⽤随机梯度下降法(Stochastic Gradient Descent Method)。
其迭代格式为x k+1=x k−αk∇ℓr(x k)其中r∈1,2,⋯,m为随机数。
这种做法可以理解为随机选择⼀个训练样本,进⾏⼀次梯度下降的训练。
在机器学习的问题中,我们通常不需要真的求得最优值,这样不精确的迭代,使得算法不容易过拟合。
由于随机梯度下降法的普及,与此相对的梯度下降法有时被称为批量梯度下降法(Batch Gradient Descent Method),因为它同时考虑所有训练样本。
介于批量梯度下降法和随机梯度下降法之间,还有⼩批量梯度下降法(Min-Batch Gradient Descent Method),也就是每次迭代选择若⼲个训练样本。
步长αk的选取梯度下降法可采⽤BB步长(Barzilai Borwein)。
BB步长有两个计算公式,选择其⼀即可。
无约束优化问题的求解方法无约束优化问题是指在不考虑任何限制条件下,通过调整自变量来寻找函数的最大值或最小值的问题。
在数学和工程领域中,无约束优化问题是一个重要的研究方向,其解决方法也非常丰富和多样。
下面将介绍几种常用的无约束优化问题求解方法。
一、梯度下降法梯度下降法是一种基于一阶导数信息的优化算法。
其基本思想是通过不断迭代地朝着函数的负梯度方向进行搜索,从而找到函数的极小值点。
具体来说,梯度下降法的迭代公式如下:x_(x+1)=x_x−x∇x(x_x),其中x_x代表第x次迭代的自变量的取值,x称为学习率,∇x(x_x)是函数x(x_x)在点x_x处的梯度。
梯度下降法是求解无约束优化问题的常用方法,具有易于实现和收敛性等优点。
但是,梯度下降法有时可能会陷入局部最优解,因此需要进行多次尝试或采用改进的算法。
二、共轭梯度法共轭梯度法是一种基于二阶导数信息的优化算法。
其基本原理是通过逆Hessian矩阵的乘法来更新自变量的取值,从而加速搜索速度。
具体来说,共轭梯度法的迭代公式如下:x_(x+1)=x_x−x_x,x∇x(x_x),x_x,x=x∇x(x_x)+x_x,x−1共轭梯度法具有高效、迭代次数少、不需要存储Hessian矩阵等优点。
然而,共轭梯度法也存在一些问题,如对于某些特定的函数可能会陷入收敛困难、对于非二次函数可能收敛速度较慢等。
三、拟牛顿法拟牛顿法是一种综合利用一阶和二阶导数信息的优化算法。
其基本思想是通过利用函数在当前点处的一阶导数和二阶导数近似值来构造一个局部的二次模型,从而求解优化问题。
拟牛顿法的迭代公式如下:x_(x+1)=x_x−(x_x)^−1∇x(x_x),x_x是拟牛顿法的Hessian矩阵近似值。
拟牛顿法具有利用了二阶导数信息、不需要进行二阶导数计算、有较好的全局收敛性等优点。
但是,拟牛顿法也存在一些问题,如需要存储和更新Hessian矩阵近似值、对于非光滑函数可能无法收敛等。
第6章 无约束问题的优化方法§6.1 最速下降法和牛顿法6.1.1 最速下降法的基本原理、计算步骤和特点基本原理: 考虑无约束问题n R x x f ∈),(min从某一点出发,选择一个目标函数值下降最快的方向,可以尽快达到极小点. 1847年法国数学家Cauchy 提出了最速下降法.后来,Curry 等人作了进一步研究. 最速下降方向是目标函数的负梯度方向:)(x f d -∇=最速下降法的迭代公式:)()()1(k k k k d x x λ+=+)(k d 取为在点)(k x 处的最速下降方向:)()()(k k x f d -∇=k λ为进行一维搜索的步长,满足:)(min )()()(0)()(k k k k k d x f d x f λλλ+=+≥计算步骤: (l)给定初点n R x∈)1(,允许误差0>ε,置1=k .(2)计算搜索方向)()()(k k x f d-∇=.(3)若ε≤)(k d,则停止计算;否则,从)(k x 出发,沿)(k d 进行一维搜索,求k λ,使 )(min )()()(0)()(k k k k k d x f d x f λλλ+=+≥(4)令)()()1(k k k k d x x λ+=+,置1:+=k k ,转步骤(2). 例1 解问题22212)(min x x x f += 初点T x)1 ,1()1(=,10/1=ε. (最优解T x )0 ,0(*=)第1次迭代:目标函数在点x 处的梯度⎥⎦⎤⎢⎣⎡=∇2124)(x x x f令搜索方向 ⎥⎦⎤⎢⎣⎡--=-∇=24)()1()1(x f dε>=+=52416)1(d从)1(x 出发,沿方向)1(d进行一维搜索,求步长1λ,即22)1()1(0)21()41(2)()(min λλλλϕλ-+-=+=≥d x f令0)('=λϕ(一般应采用不精确一维搜索求解),解得18/51=λ在直线上的极小点: ⎥⎦⎤⎢⎣⎡-=+=9/49/1)1(1)1()2(d x x λ 第2次迭代:⎥⎦⎤⎢⎣⎡-=-∇=9/89/4)()2()2(x f d ε>=5/54)2(d 22)2()2(0)21(8116)41(812)()(min λλλλϕλ-+-=+=≥d x f 解得 12/52=λ⎥⎦⎤⎢⎣⎡=+=27/227/2)2(2)2()3(d x x λ 第3次迭代:⎥⎦⎤⎢⎣⎡--=-∇=27/427/8)()3()3(x f d ε>=27/54)3(d2222)3()3(0)21(274)41(278)()(min λλλλϕλ-+-=+=≥d x f 解得 18/53=λ⎥⎦⎤⎢⎣⎡-=+=412432)3(3)3()4(d x x λ 这时有ε<=52438)4(d 满足精度要求,得到近似解⎥⎦⎤⎢⎣⎡-=412432x 最速下降算法的特点:最速下降算法在一定条件下是收敛的.最速下降法产生的序列是线性收敛的,而且收敛性质与极小点处Hesse 矩阵)(2x f ∇的特征值有关.定理1: 设)(x f 存在连续二阶偏导数,x 是局部极小点,Hesse 矩阵)(2x f ∇的最小特征值0>a ,最大特征值为A ,算法产生的序列}{)(k x 收敛于点x ,则目标函数值的序列)}({)(k x f 以不大于2⎪⎭⎫⎝⎛+-a A a A 的收敛比线性地收敛于)(x f .最速下降法存在锯齿现象:从局部看,最速下降方向确是函数值下降最快的方向.从全局看,由于锯齿现象的影响,即使向着极小点移近不太大的距离,也要经历不小的弯路,使收敛速率大为减慢.注1:最速下降法并不是收敛最快的方法,从全局看,它的收敛是比较慢的. 注2:最速下降法一般适用于计算过程的前期迭代或作为间插步骤. 当接近极小点时,使用最速下降法达到迭代终止,这样做并不有利.6.1.2 牛顿法的基本原理、计算步骤和特点1.牛顿法)(x f 在点)(k x 的二阶Taylor 展开为))(()(21 )()()()()()()(2)()()()(k k T k k T k k x x x f x x x x x f x f x x f -∇-+-∇+=≈φ 求)(x φ的平稳点,令0)('=x φ,即0))(()()()(2)(=-∇+∇k k k x x x f x f (1)设)()(2k xf ∇可逆,得到牛顿法的迭代公式)()()(1)(2)()1(k k k k x f x f x x ∇∇-=-+产生序列}{)(k x ,在适当的条件下,这个序列收敛.例2:解问题:2241)1min(x x +- (最优解T x )0,1(=) 目标函数的梯度和Hesse 矩阵分别为⎥⎦⎤⎢⎣⎡-=∇2312)1(4)(x x x f ⎥⎦⎤⎢⎣⎡-=∇200)1(12)(212x x f 取初点T x )1 ,0()1(=. 第l 次迭代:⎥⎦⎤⎢⎣⎡-=∇24)()1(x f ⎥⎦⎤⎢⎣⎡=∇20012)()1(2x f ⎥⎦⎤⎢⎣⎡=⎥⎦⎤⎢⎣⎡-⎥⎦⎤⎢⎣⎡-⎥⎦⎤⎢⎣⎡=∇∇-=--03/1242001210)()(1)1(1)1(2)1()2(x f x f x x第2次迭代:⎥⎦⎤⎢⎣⎡-=∇027/32)()2(x f ⎥⎦⎤⎢⎣⎡=∇2009/48)()1(2x f ⎥⎦⎤⎢⎣⎡=∇∇-=-09/5)()()2(1)2(2)2()3(x f x f x x继续迭代,得到⎥⎦⎤⎢⎣⎡=027/19)4(x,⎥⎦⎤⎢⎣⎡=081/65)5(x ,…注3:当牛顿法收敛时,有下列关系:2)()1(x x c x x k k -≤-+c 是某个常数.因此,牛顿法至少2级收敛,收敛速率是很快的.注4:对二次凸函数,用牛顿法求解经1次迭代即达极小点.设有二次凸函数:c x b Ax x x f T T++=21)(用极值条件求解:令0)(=+=∇b Ax x f 得到最优解b A x 1--=用牛顿法求解:任取初始点)1(x ,根据牛顿法的迭代公式有b A b Ax A x x f A x x 1)1(1)1()1(1)1()2()()(----=+-=∇-=以后还会遇到一些算法,把它们用于二次凸函数时,类似于牛顿法,经有限次迭代必达到极小点.这种性质称为二次终止性.注5: 当初始点远离极小点时,牛顿法可能不收敛. 牛顿方向)()()(1)(2k k x f xf d ∇-∇=-不一定是下降方向,经迭代,目标函数值可能上升. 即使目标函数值下降,得到的点)1(+k x 也不一定是沿牛顿方向的最好点或极小点.对牛顿法进行修正,提出了阻尼牛顿法.2. 阻尼牛顿法阻尼牛顿法增加沿牛顿方向的一维搜索,迭代公式:)()()1(k k k k d x x λ+=+)()()(1)(2)(k k k x f x f d ∇-∇=-为牛顿方向.k λ由一维搜索得到:)(min )()()()()(k k k k k d x f d x f λλλ+=+由于阻尼牛顿法含有一维搜索,因此每次迭代目标函数值一般有所下降(绝不会上升).可以证明,阻尼牛顿法在适当的条件下具有全局收敛性,且为2 级收敛.阻尼牛顿法的计算步骤:(l)给定初点)1(x ,允许误差0>ε,置1=k .(2)计算)()(k x f ∇,1)(2)(-∇k x f .(3)若ε<∇)()(k x f ,则停止计算;否则,令)()()(1)(2)(k k k x f x f d ∇-∇=-(4)从)(k x出发,沿)(k d进行一维搜索,求k λ,使)(min )()()(0)()(k k k k k d x f d x f λλλ+=+≥(5)令)()()1(k k k k d x x λ+=+,置1:+=k k ,转步骤(2). 3.牛顿法的进一步修正原始牛顿法和阻尼牛顿法有共同缺点:(1)可能出现Hesse 矩阵奇异的情形,因此不能确定后继点;(2)即使)(2x f ∇非奇异,也未必正定,因而牛顿方向不一定是下降方向,就可能导致算法失效.例3: 用阻尼牛顿法求解:222141)1()(min x x x x x f +++=取初始点T x )0,0()1(=. 在点)1(x 处,有⎥⎦⎤⎢⎣⎡=∇20)()1(x f ,⎥⎦⎤⎢⎣⎡=∇2110)()1(2x f牛顿方向⎥⎦⎤⎢⎣⎡-=⎥⎦⎤⎢⎣⎡⎥⎦⎤⎢⎣⎡-=∇-∇=--02202110)()(1)1(1)1(2)1(x f x f d从)1(x 出发,沿)1(d 作一维搜索.令 116)()(4)1()1(+=+=λλλφd xf , 则 01=λ.用阻尼牛顿法不能产生新点,而点T x )0,0()1(=并不是问题的极小点.原因在于Hesse矩阵)()1(2x f ∇非正定.为使牛顿法从任一点开始均能产生收敛于解集合的序列}{)(k x ,要做进一步修正,克服Hesse 矩阵非正定.考虑(1)式,记搜索方向)()(k k x x d-=,得到)()()()()(2k k k x f d x f -∇=∇ (2)阻尼牛顿法所用搜索方向是上述方程的解:)()()(1)(2)(k k k x f x f d ∇-∇=-解决Hesse 矩阵)()(2k x f ∇非正定问题的基本思想: 修正)()(2k x f ∇,构造一个对称正定矩阵k G . 在(2)中,用k G 取代矩阵)()(2k x f ∇,得到方程)()()(k k k x f d G -∇= (3)解此方程,得到在点)(k x处的下降方向)()(1)(k k k x f G d ∇-=-构造矩阵k G 的方法之一: 令I x f G k k k ε+∇=)()(2k ε是一个适当的正数.只要k ε选择得合适,k G 就是对称正定矩阵.注6: 当)(k x为鞍点时,有0)()(=∇k x f 及 )()(2k x f ∇不定此时(3)式不能使用. 这时)(k d可取为负曲率方向:0)()()(2)(<∇k k T k d x f d当)()(2k x f ∇不定时,这样的方向必定存在,而且沿此方向进行一维搜索必能使目标函数值下降.§6.2 共轭梯度法6.2.1 共轭方向的基本原理和定理共轭梯度法是基于共轭方向的一种算法.定义1:设A 是n n ⨯对称正定矩阵,若nR 中的两个方向)1(d和)2(d满足0)2()1(=Ad d T则称这两个方向关于A 共轭,或称它们关于A 正交.若)1(d,)2(d,… ,)(k d是nR 中k 个方向,它们两两关于A 共轭,即满足j i Ad d j T i ≠= ,0)()(则称这组方向是A 共轭的,或称它们为A 的k 个共轭方向.注1:如果A 为单位矩阵,则两个方向关于A 共轭等价于两个方向正交.共轭是正交概念的推广.注2:如果A 是一般的对称正定矩阵,)(i d和)(j d关于A 共轭,也就是方向)(i d与方向)(j Ad 正交.共轭的几何意义(以正定二次函数为例): 二次函数)()(21)(x x A x x x f T --=函数)(x f 的等值面c x x A x x T =--)()(21是以x 为中心的椭球面,x 是极小点. 设)1(x 是在某个等值面上的一点,该等值面在点)1(x 处的法向量)()()1()1(x x A x f -=∇又设)1(d是这个等值面在)1(x 处的一个切向量.记)1()2(x x d -=)1(d 与)()1(x f ∇正交,即0)()1()1(=∇x f d T ,因此有0)2()1(=Ad d T即等值面上一点处的切向量与由这一点指向极小点的向量关于A 共轭.依次沿着)1(d和)2(d进行一维搜索,则经两次迭代必达到极小点.共轭方向的重要性质:定理1: 设A 是n 阶对称正定矩阵,)1(d ,)2(d,… ,)(k d是k 个A 共轭的非零向量,则这个向量组线性无关.定理2(扩张子空间定理): 设有函数c x b Ax x x f T T++=21)( 其中A 是n 阶对称正定矩阵,)1(d ,)2(d,… ,)(k d 是A 共轭的非零向量.以任意的)1(x 为初始点,依次沿)1(d,)2(d,… ,)(k d进行一维搜索,得到点)2(x ,)3(x,… ,)1(+k x,则)1(+k x 是函数)(x f 在线性流形k B x +)1(上的惟一极小点.特别地,当n k =时,)1(+n x 是函数)(x f 的惟一极小点.其中⎭⎬⎫⎩⎨⎧∞-∞∈==∑=),(,|1)(i ki i i k d x x B λλ是)1(d,)2(d,… ,)(k d生成的子空间.推论: 在定理2的条件下,必有,0)()()1(=∇+j T k d x f k j ≤∀定理2表明: 对于二次凸函数,若沿一组共轭方向(非零向量)搜索,经有限步迭代必达到极小点.6.2.2 用于正定二次函数的共轭梯度法共轭梯度法最初由Hesteness 和Stiefel 于1952年提出.本节重点介绍Fletcher-Reeves 共轭梯度法(FR 法).共轭梯度法的基本思想:把共轭性与最速下降方法相结合,利用已知点处的梯度构造一组共轭方向,沿这组方向进行搜索,求出目标函数的极小点.根据共轭方向的基本性质,这种方法具有二次终止性. 考虑如下正定二次函数优化问题的求解方法:c x b Ax x x f T T++=21)(min 令)(x f g ∇=.任意给定一个初始点)1(x ,计算出目标函数)(x f 在这点的梯度,01=g ,则停止计算;否则,令1)1()1()(g x f d -=-∇=沿方向)1(d搜索,得到点)2(x.计算在)2(x 处的梯度,若02≠g ,则利用2g -和)1(d构造第2个搜索方向)2(d ,再沿)2(d搜索.一般地,若已知点)(k x 和搜索方向)(k d ,则从)(k x出发,沿)(k d进行搜索,得到)()()1(k k k k d x x λ+=+步长k λ满足)(min )()()(0)()(k k k k k d x f d xf λλλ+=+≥.此时可求出k λ的显式表达.令)()()()(k k d x f λλφ+=,根据0)('=λφ及二次函数的梯度的表达式,得到)()()(k T k k T k k Add dg -=λ (1)计算)(x f 在)1(+k x 处的梯度,若01=+k g ,则停止计算;否则用1+-k g 和)(k d构造下一个搜索方向)1(+k d,并使)1(+k d 和)(k d关于A 共轭.按此设想,令)(1)1(k k k k d g d β+-=++上式两端左乘A dTk )(,并令0)()(1)()1()(=+-=++k T k k k T k k T k Ad d Ag d Ad d β由此得到 )()(1)(k T k k T k k Add Ag d +=β 再从)1(+k x出发,沿方向)1(+k d搜索.可以证明,按上述方法构造的一组搜索方向,是关于A 共轭的.因此,上述方法具有二次终止性.定理3: 对于正定二次函数,具有精确一维搜索的FR 法在n m ≤次一维搜索后即终止,并且对所有m i i ≤≤1(),下列关系成立:(l) )1,,2,1( 0)()(-==i j Ad d j T i (2) )1,,2,1( 0-==i j g g j T i (3) )0()()(≠-=i i T i i T i d g g d g 蕴含 证明: 用归纳法可证注3: 在FR 法中,初始搜索方向必须取最速下降方向.如果选择别的方向作为初始方向,其余方向均按FR 法构造,那么极小化正定二次函数时,构造出来的一组方向并不能保证共轭性.可以证明: 对于正定二次函数,运用FR 法时,不作矩阵运算就能求出因子 i β. 定理4: 对于正定二次函数,FR 法中因子g g ii i 221+=β,1>i , 0≠i g (2)对于二次凸函数,FR 法计算步骤:(1) 给定初始点)1(x ,置1=k .(2) 计算)()(k k x f g ∇=,若0=k g ,则停止计算,得点)(k xx =;否则,进行下一步.(3)构造搜索方向,令)1(1)(--+-=k k k k d g d β.当1=k 时,01=-k β,当1>k 时,按(2)式计算因子1-k β.(4)令)()()1(k k k k d x x λ+=+,步长k λ按(1)式计算.(5)若n k =,则停止计算,得点)1(+=k x x ;否则,置1:+=k k ,返回步骤(2).例1: 用FR 法求解问题:22212)(min x x x f +=,取初始点T x)5 ,5()1(=.目标函数梯度: ⎥⎦⎤⎢⎣⎡=∇2142)(x x x f第1次迭代: 令⎥⎦⎤⎢⎣⎡--=-=20101)1(g d,从)1(x 沿方向)1(d 作一维搜索,得 185)1()1()1(11=-=Ad d d g T T λ⎥⎦⎤⎢⎣⎡-=+=9/59/20)1(1)1()2(d x x λ 第2次迭代: 在点)2(x处,目标函数的梯度⎥⎦⎤⎢⎣⎡-=9/209/402g 构造搜索方向)2(d.计算因子 g g 81421221==β.令 ⎥⎦⎤⎢⎣⎡-=+-=1481100)1(12)2(d g d β 从)2(x出发,沿方向)2(d作一维搜索,得209)2()2()2(22=-=Ad d d g T T λ⎥⎦⎤⎢⎣⎡=+=00)2(2)2()3(d x x λ点)3(x处,目标函数梯度T g )0 ,0(2=,已达到极小点.6.2.3 将共轭梯度法用于求解非正定二次函数优化问题用于极小化任意函数的共轭梯度法与用于极小化二次函数的共轭梯度法主要差别:(1)步长不用)()()(k T k k T k k Add dg -=λ计算,必须用其它一维搜索方法来确定. (2)凡用到矩阵A 之处,需要用现行点处的Hesse 矩阵)()(2k x f ∇.用这种方法求任意函数极小点,一般来说用有限步迭代是达不到的.迭代延续可以采取不同的方案:∙直接延续,即总是用)(1)1(k k k k d g d β+-=++构造搜索方向;∙把n 步作为一轮,每搜索一轮之后,取一次最速下降方向,开始下一轮.称为“重新开始”或“重置”.每n 次迭代后以最速下降方向重新开始的共轭梯度法,有时称为传统的共轭梯度法. 计算步骤:(1)给定初始点)1(x ,允许误差0>ε.置)1()1(x y =,)()1()1(y f d -∇=, 1==j k(2)若ε<∇)()(j y f ,则停止计算;否则,作一维搜索,求j λ,满足)(min )()()(0)()(j j j j j d y f d y f λλλ+=+≥令)()()1(j j j j d y yλ+=+.(3)如果n j <,则进行步骤(4);否则,进行步骤(5). (4)令)()1()1()(j j j j d y f dβ+-∇=++,其中y f y f j j j 2)(2)1()()(∇∇=+β置1:+=j j ,转步骤(2).(5)令)1()1(++=n k y x ,)1()1(+=k x y ,)()1()1(y f d -∇=,置1=j , 1:+=k k ,转步骤(2). 注4:可以采用不同公式计算因子 j β: (1) g g jj j 221+=β(FR 法)(2) g g g g g jTjj j T j j )(11-=++β(Polak,Ribiere&Polyak ,PRP 法)(3) g g d g g g j j T j j j T j j )()(1)(11--=+++β (Sorenson 和Wolfe )(4) dxf dg x f d j j Tj j j T j j )()1(2)(1)1(2)()()(+++∇∇=β (Daniel )(1)当极小化正定二次函数,初始搜索方向取负梯度时,四个公式是等价的. (2)用于一般函数时,得到的搜索方向不同.(3)有人认为PRP 方法优于FR 法.但据一些人的计算结果,几种方法彼此差别并不很大,难以给出绝对的比较结论.注5: 运用共轭梯度法时应该注意,均假设采用精确一维搜索.精确一维搜索需付出较大代价,因此许多情形下采用不精确一维搜索.不精确一维搜索会出现新的问题,按照)(1)1(k k k k d g d β+-=++构造的搜索方向可能不是下降方向.解决方法: (1)当)1(+k d不是下降方向时,以最速下降方向重新开始.当一维搜索比较粗糙时,这样的重新开始可能是大量的,因此会降低计算效率.(2)计算过程中增加附加检验.设1+k g ,)1(+k d ,k β表示在检验点)()(k k k d x α+处计算出的1+k g ,)1(+k d和k β,如满足)1(1)1(1++++≥-k k k T k dg dg σ则取k α作为步长k λ;否则,进行精确一维搜索,求最优步长k λ.共轭梯度法的收敛性:对于一般函数, 共轭梯度法在一定条件下是收敛的.Crowder 和Wolfe 证明: 共轭梯度法的收敛速率不坏于最速下降法; 不用标准初始方向1)1(g d-=,共轭梯度法的收敛速率可能像线性速率那样慢.共轭梯度法的优点:存储量小:FR 法只需存储3个n 维向量. 求解变量多的大规模问题可用共轭梯度法§6.3 拟牛顿法6.3.1 拟牛顿法简介牛顿法的最大优点是收敛速度快,原因是牛顿法在迭代点附近对目标函数进行二次近似时,利用了目标函数的曲率信息(Hesse 矩阵)。