1、 基本思想基本思想：函数的：函数的负梯度方向负梯度方向是函数值在是函数值在该点该点下降最快的方向。利用负梯度作为搜索下降最快的方向。利用负梯度作为搜索方向，故称最速下降法或梯度法。方向，故称最速下降法或梯度法。 搜索方向搜索方向s取该点的负梯度方向取该点的负梯度方向 (最速下降最速下降方向方向) ，使函数值在该点附近的范围内下降最快，使函数值在该点附近的范围内下降最快 。( )fx1(0,1,2,)kkkkskxx1() (0,1,2,)kkkkafkxxx 为了使目标函数值沿搜索方向为了使目标函数值沿搜索方向 能够获能够获得最大的下降值，其步长因子得最大的下降值，其步长因子 应取一维搜索的最
2、应取一维搜索的最佳步长。即有佳步长。即有()kf xk1()()min ()min ( )kkkkkkaaffaffa f xxxxx步长因子步长因子 求解方法：求解方法：解析法：根据极值点必要条件。解析法：根据极值点必要条件。黄金分割法黄金分割法牛顿法牛顿法抛物线法抛物线法k最速下降法的搜索路径最速下降法的搜索路径相邻相邻两个两个搜索搜索方向方向互相互相垂直垂直1()()min ()min ( )kkkkkkaaffaffa f xxxxx 根据一元函数极值的必要条件及根据一元函数极值的必要条件及复合函数求导公式得复合函数求导公式得 ( )()()0Tkkkkfff xxx1()()0kTk
3、ffxx1()0kTkss 在最速下降法中，在最速下降法中，相邻两个迭代点上的函相邻两个迭代点上的函数梯度相互垂直。数梯度相互垂直。搜索方向搜索方向就是就是负梯度负梯度方方向，因此向，因此相邻相邻两个搜索两个搜索方向方向互相垂直互相垂直。形成形成“之之”字形的锯齿字形的锯齿现象，而且越接近现象，而且越接近极小极小点点锯齿越细。锯齿越细。 图图 最速下降法的搜索路径最速下降法的搜索路径图图 最速下降法的收敛过程最速下降法的收敛过程沿负梯度方向进行一维搜索，有沿负梯度方向进行一维搜索，有02,2Tx例求目标函数例求目标函数 的极小点。的极小点。取初始点取初始点2221)(xxfx解：初始点处梯度：
4、解：初始点处梯度：4422)(0210 xxxxf)(001xfxx沿负梯度方向进行一维搜索，有沿负梯度方向进行一维搜索，有0为一维搜索最佳步长，应满足极值必要条件为一维搜索最佳步长，应满足极值必要条件 02,2Tx 例例 求目标函数求目标函数 的极小点。的极小点。取初始点取初始点2221)(xxfx)(001xfxx000142424422x)()42()42()(020201xf0)42(4)(005 . 0000)(0001xfxx0)(0022)(0)(121111xxxxfxxff第一次迭代设计点位置和函数值第一次迭代设计点位置和函数值 因此，迭代终止：因此，迭代终止： 0)(001
5、xxxfT沿负梯度方向进行一维搜索，有沿负梯度方向进行一维搜索，有01000024()2 100fxxx0为一维搜索最佳步长，应满足极值必要条件为一维搜索最佳步长，应满足极值必要条件 122()min (24 )25(2 100 )min ( )f x例例4 42 2 求目标函数求目标函数 的极小点。的极小点。解解 取初始点取初始点则初始点处梯度：则初始点处梯度：02,2Tx2212( )25fxxx如何求？如何求？00102()10424()50100 xfxfxxx00( )8(24)5 000(2 100)0 算出一维搜索最佳步长算出一维搜索最佳步长 06260.020 030 7231
6、 252第一次迭代设计点位置和函数值第一次迭代设计点位置和函数值 0120241.919 8772 1000.307178 5 10 x1()3.686164fx继续作下去，经继续作下去，经1010次迭代后，得到最优解次迭代后，得到最优解 00Tx()0fx例例 用梯度法求下面无约束优化问题：用梯度法求下面无约束优化问题：例例 用梯度法求下面无约束优化问题：用梯度法求下面无约束优化问题：例例 用梯度法求无约束优化问题：用梯度法求无约束优化问题：例例 用梯度法求下面无约束优化问题：用梯度法求下面无约束优化问题：例例 用梯度法求下面无约束优化问题：用梯度法求下面无约束优化问题：例例 用梯度法求下面
7、无约束优化问题：用梯度法求下面无约束优化问题：梯度法的特点梯度法的特点r（1）理论明确，程序简单，对）理论明确，程序简单，对初始点初始点要求不严格。要求不严格。r（2）对一般函数而言，梯度法的收敛速度并不快，因）对一般函数而言，梯度法的收敛速度并不快，因为最速下降方向仅仅是指某点的一个为最速下降方向仅仅是指某点的一个局部性质局部性质。r（3）梯度法相邻两次搜索方向的正交性，决定了迭代）梯度法相邻两次搜索方向的正交性，决定了迭代全过程的搜索路线呈全过程的搜索路线呈锯齿锯齿状，状，远快近慢远快近慢。r（4）梯度法的收敛速度与目标函数的性质密切相关。）梯度法的收敛速度与目标函数的性质密切相关。对于等
8、值线对于等值线(面面)为同心圆（球）的目标函数，一次搜索为同心圆（球）的目标函数，一次搜索即可达到极小点。即可达到极小点。4.4.2 4.4.2 共轭梯度法共轭梯度法n共轭梯度法是共轭方向法中的一种，该方法中共轭梯度法是共轭方向法中的一种，该方法中每一个共轭向量都是依赖于迭代点处的负梯度每一个共轭向量都是依赖于迭代点处的负梯度而构造出来。而构造出来。n 从从xk出发，沿负梯度方向作一维搜索出发，沿负梯度方向作一维搜索:1(0,1,2,)kkkkkxxd()kkf dx设与设与dk共共轭的下一个方向轭的下一个方向dk+1由由dk和点和点xk+1的负梯的负梯度的线形组合构成，即：度的线形组合构成，
9、即：11()kkkkf dxd21()( )0kTkfdx d共轭条件：共轭条件：4.4.2 4.4.2 共轭梯度法共轭梯度法n则：则：21()( )()0kTkkkfff xxxd解得：解得：212()()()()()()kTkkkkTkkffffffxxxxxx21()( )0kTkfdx d4.4.2 4.4.2 共轭梯度法共轭梯度法令令1( )2TfTxx Gxb xc为函数的泰勒二次展开式为函数的泰勒二次展开式()kkfxGxb则则11()kkfxGxb上两式相减，并代入上两式相减，并代入1kkkkxxd1()()kkkkff Gdxx4.4.2 4.4.2 共轭梯度法共轭梯度法1(
10、)()kkkkff Gdxx将式将式11()kkkkf dxd与式与式两边相乘，并应用两边相乘，并应用共轭条件共轭条件得：得：11()()()()0kkkkkffff xxxx21112()()()()()()kkTkkkTkkffffffxxxxxx4.4.2 4.4.2 共轭梯度法共轭梯度法因此因此11()kkkkf dxd212()()kkkffxx1(0,1,2,)kkkkkxxd4.4.2 4.4.2 共轭梯度法共轭梯度法特点：一阶求导、公式结构简单、所需存储量少、特点：一阶求导、公式结构简单、所需存储量少、收敛速度快；理论上对于二次型函数，最多经过收敛速度快；理论上对于二次型函数，
11、最多经过n步迭代必能达到最小值。步迭代必能达到最小值。课堂练习：课堂练习： 求目标函数求目标函数 的极小点。的极小点。 取初始点取初始点 用共轭梯度法解上题。用共轭梯度法解上题。 （只计算搜索两次）（只计算搜索两次）22214)(xxxfTx110( )x( )x( )f x1kx( )f x4.4.3 牛顿法和修正牛顿法牛顿法和修正牛顿法2( )( )()() ()1()()()2kkTkkTkkffffxxxxxxxxxxx设设 为为 的极小点的极小点 1kx( )x1()0kx121()()(0,1,2,)kkkkffk xxxx这就是多元函数求极值的牛顿法迭代公式。这就是多元函数求极值
12、的牛顿法迭代公式。 牛顿法牛顿法例例4 44 4 求目标函数求目标函数 的极小点。的极小点。解解 取初始点取初始点2212( )25fxxx02,2Tx102010102402()()121000050ff xxxx1004502)(0210 xxxxf50002)(02xf00 x()0fx经过一次迭代即求得极小点经过一次迭代即求得极小点函数极小值函数极小值121()()(0,1,2,)kkkkffk xxxx121()()(0,1,2,)kkkkffk xxxx 例例 用牛顿法求解函数用牛顿法求解函数22122( )44F xxxx的极小值初始起始点的极小值初始起始点1，1T。 因此对于非
13、二次函数，如果采用上述牛顿迭代公式，因此对于非二次函数，如果采用上述牛顿迭代公式，有时会使函数值上升有时会使函数值上升 。牛顿法的缺点牛顿法的缺点修正牛顿法（阻尼牛顿法）修正牛顿法（阻尼牛顿法） 121( )( )(0,1,2, )kkkkkkkksffkxxxxxk阻尼因子阻尼因子 ，沿牛顿方向进行一维搜索的最佳沿牛顿方向进行一维搜索的最佳步长，由下式求得：步长，由下式求得： 1()()min()kkkkkkkffsfsxxx开始给定结束0,x21()()kkkff dxx1:min()kkkkkkkfxxdxd1kkxx*1kxx否是1kk0k 阻尼牛顿法程序框图 （1） 应选在应选在X*
14、附近，有一定难度；附近，有一定难度； （2） 尽管每次迭代都不会是函数值上升，但不能保证尽管每次迭代都不会是函数值上升，但不能保证每次下降每次下降 ； （3） 若迭代点的海赛矩阵为奇异，则无法求逆矩阵，若迭代点的海赛矩阵为奇异，则无法求逆矩阵，不能构造牛顿法方向；不能构造牛顿法方向； （4） 不仅要计算梯度，还要求海赛矩阵及其逆矩阵，不仅要计算梯度，还要求海赛矩阵及其逆矩阵，计算量和存储量大。此外，对于二阶不可微的计算量和存储量大。此外，对于二阶不可微的F(X)也也不适用。不适用。 阻尼牛顿法方法特点阻尼牛顿法方法特点1(0,1,2,)kkkkskxx1() (0,1,2,)kkkkafkxx
15、x121()()(0,1,2,)kkkkffk xxxx121()()(0,1,2,)kkkkkffkxxxx一般迭代式：一般迭代式：梯度法：梯度法：牛顿法：牛顿法：阻尼牛顿法：阻尼牛顿法：修正牛顿法既保持了牛顿法收敛快的特性又放宽了对初始点选择的要求，并能保证每次迭代都使目标函数值下降。在实际应用中由于要求海森矩阵是非要求海森矩阵是非奇异的奇异的，另外求逆阵的计算工作量大求逆阵的计算工作量大，尤其是维数较高时，计算量与存贮量都随n2增加。在A点由于函数接近平方函数，因而由A点进行搜索，用牛顿方向更有效和更快；若从B点进行搜索，由于此点的目标函数不完全是二次函数，因此采用梯度方向进行搜索可以获
16、得更好的效果4.4.4 4.4.4 变尺度法变尺度法1. 1. 变尺度的变尺度的基本思想：基本思想： 发扬梯度法和牛顿法各自的优点，避免两者各自的缺点，发扬梯度法和牛顿法各自的优点，避免两者各自的缺点，将两者结合起来，形成变尺度法。将两者结合起来，形成变尺度法。即为梯度法，首次迭代时，为拟牛顿方向。的矩阵一个为变尺度矩阵，是：其中：迭代公式, )(, )(,),()()()0()()()()()()()()()1(kkkkkkkkkkkxfSIHxfHSnnHxfHxx即为牛顿法。最终迭代时，时接近当不断修正尺度，逼近，中间的迭代：迭代公式, )()(, )()(,)(*,)(),()(1)(
17、)()(1)()(1)()()(1)()()()()()() 1(kKkkKkKkkkkkkkkkxfxHSxfxHSxHHxxxHHxfHxx了牛顿法的优点。矩阵的逆矩阵，而利用及这样避免计算二阶导数Hesse构造变尺度矩阵的递推公式构造变尺度矩阵的递推公式：修正矩阵修正矩阵: : 次迭代时的修正矩阵。为第其中：kEEHHkkkk)()()()1(,)()()()()()()()()()()()(kkTkkTkkkkTkTkkkgHgHggHxgxxEDFPDFP公式公式: : 4.4.4.4 DFP变尺度法的特点和变尺度法的特点和BFGS变尺度法变尺度法 DFP变尺度法的特点： (1)DF
18、P变尺度法不需要求Hessian矩阵及其逆阵，但需利用一阶导数信息。 DFP法开始时是梯度法，所以从任一初始点通过梯度方向找到一个比较好的迭代点，这为以后的逐次迭代，创造了有利的条件。(2)DFP法的收敛速度介于梯度法和牛顿法之间。 (3)计算实践表明，一维搜索的精度对收敛速度影响不大。但如果精度太低，也有可能会使汁算失效，因此对一维搜索的精度要求一般不低于终止计算的精度。 DFP变尺度法虽收敛速度较快，但是它也存在数值计算稳定性较差的问题，于是在70年代初又提出了另一种变尺度法BFGS变尺度法，这种方法与DFP方法的不同之处，在于近似矩阵的计算不同。（目前最成功的变尺度法） 由于BFGS变尺
19、度法对一维最优化搜索精度要求较低，因而，在迭代中H 矩阵不易退化为病态矩阵，从而保证了算法数值计算的稳定性。牛顿法和变尺度法牛顿法和变尺度法1(0,1,2,)kkkkskxx)()()()()()()1()()()(kkkkkkkkxfCxxxfCS则令?)()()()()1()(则为什么方法则令kkkkkxfIxxIC?)()(1)()()()1(1)()(则为什么方法则令kkkkkkkxfHxxHC 在梯度算法类中，像牛顿法和修正牛顿法需要用到目标函数的二阶导数，称这些算法为；算法中仅用到目标函数的一阶导数，如梯度法、共扼梯度法、变尺度法，称为；按此分类方法，各种非梯度算法又称为。 非导数
20、类算法，由于在计算中不需求目标函数的导数，所以这类算法适合于不易求导数的优化问题，这给工程问题的计算带来很多的方便。另外，计算较为稳定，编程简单和计算较为稳定，编程简单和所需的存贮单元量少也是它的优点。缺点是收敛速度较慢，属所需的存贮单元量少也是它的优点。缺点是收敛速度较慢，属于线性或超线性收敛。于线性或超线性收敛。 导数类算法，由于利用了多元函数的极值性质，寻求更合理的搜索方向，使迭代次数减少，收敛速度加快。但当问题的当问题的目标函数无解析导数或求解析导数困难而采用差分法求近似导目标函数无解析导数或求解析导数困难而采用差分法求近似导数时，由于不可避免地存在计算误差和舍入误差的干扰，而使数时，由于不可避免地存在计算误差和舍入误差的干扰，而使计算的稳定性和可靠性比较差。计算的稳定性和可靠性比较差。
