无约束优化方法PPT学习教案

1、会计学1 无约束优化方法无约束优化方法ppt课件课件 2021-8-42 第1页/共47页 2021-8-43 T 12 , , , ( )m i n n xx xx fx = L 使 0f= 1 (0,1,2, ) kkk k xxdka + =+=L 第2页/共47页 2021-8-44 n坐标轮换法，单 形替换法及鲍威 尔（Powell）法 等。 第3页/共47页 2021-8-45 () 1 0,1,2, kkkk XXaf Xk + =-=L ()()()()()( ) 1 m i nm i n kkkkkk aa f Xf Xaf Xf Xaf Xaj + =-=-= 第4页/共4

2、7页 2021-8-46 ()() T 1 0 kk f Xf X + 轾 蜒= 臌 T 1 0 kk dd + = x1 x2 O 图 最速下降法的搜索路径 第5页/共47页 2021-8-47 取初始点x0=2,2T 初始点处函数值及梯度分别为 () 0 104f X= () 1 0 2 24 50100 x f X x 轾轾 犏犏 = 犏犏 犏犏 臌臌 沿负梯度方向搜索 () 0 100 00 0 2424 21002100 a XXaf Xa a 轾轾轾 - 犏犏犏 =-=-= 犏犏犏- 犏犏犏 臌臌臌 第6页/共47页 2021-8-48 a0为一维搜索最佳步长，应满足极值必要条件

3、()() ()() ( ) 100 22 00 m i n m i n2425 2100m i n a aa f Xf Xaf X aaaj 轾 =- 犏 臌 =-+-= ()()() 0 8 245000 21000aaaj= -= 可算出一维搜索最佳步长 0 626 0. 02003072 31252 a= 以及第一次迭代设计点的位置和函数值 0 1 2 0 1. 91987724 21000. 307178510 a X a - 轾轾 - 犏犏 = 犏犏- - 犏犏 臌臌 从而完成了最速下降法的第一次迭代 求最佳步长 第7页/共47页 2021-8-49 0 0 X * 轾 犏 = 犏

4、犏 臌 () 0f X * = x0 x1 x2 第8页/共47页 2021-8-410 给定x0, k=0 dk=f(xk) ak=minf(xk+akdk) xk+1=xk+akdk k=k+1 xk+1xkx*=xk+1 结束 是是否否 第9页/共47页 2021-8-411 第10页/共47页 2021-8-412 () () 1 0,1,2, k kk k fx xxk fx + =-= L ( )()() ()()()() TT 2 1 2 kkkkkk f Xf Xf XXXXXf XXX 轾 +-+- 臌 极值必要条件极值必要条件 () 1 0 k f X + = ()()()

5、 2 1 0 kkkk f Xf XXX + + -= ()() 1 2 1kkkk XXf Xf X - + 轾 =-蜒 犏 臌 二次收敛 第11页/共47页 2021-8-413 取初始点为x0=2,2T () 0 1 0 2 24 50100 X x f X x 轾轾 犏犏 = 犏犏 犏犏 臌臌 () 20 20 050 f X 轾 犏 = 犏 犏 臌 () 1 20 1 0 2 1 0 50 f X - 轾 犏 犏 轾 = 犏 犏 臌 犏 犏 臌 代入牛顿法迭代公式 ()() 1 10200 1 0 240 2 211000 0 50 XXf Xf X - 轾 犏 轾轾轾 犏 轾犏犏犏

6、 =-蜒=-= 犏 犏犏犏犏 臌 犏犏犏犏 臌臌臌 犏 臌 第12页/共47页 ()() 1 2 1kkkk XXf Xf X - + 轾 =-蜒 犏 臌 ()()() () ()()()() T 1 1 T 2 Kkkk kkkk f Xf Xf XXX f Xf Xf Xf X + - 轾 +- 臌 轾 轾 =-蜒 犏臌 臌 第13页/共47页 ()() 1Kk f Xf X + ()()() 1 T 2 0 kkk f Xf Xf X - 轾 轾 - 蜒 犏臌 臌 ()()() 1 T 2 0 kkk f Xf Xf X - 轾 轾 蜒 犏臌 臌 第14页/共47页 2021-8-416

7、 第15页/共47页 2021-8-417 ()() 1 2 kkk df Xf X - 轾 = - 蜒 犏 臌 n看作是搜索方向 ()() 1 2 1 ,0,1,2, kkk kkkkk XXa dXaf Xf Xk - + 轾 =-=-蜒= 犏 臌 L 阻尼牛顿法的迭代公式为 ak沿牛顿方向的一维最佳搜索步长，可称为阻尼因子阻尼因子 ak可通过一维搜索的极小化过程求得 ()()() 1 m i n kkk kkk a f Xf Xa df Xad + =+=+ ak 取为固定值1时，阻尼牛顿法就成为了牛顿法 n每次迭代都在牛顿方向上进行一维搜索，避免了迭代后函数值上升的现象 n保持了牛顿法

8、二次收敛的特性，而对初始点的选取并没有苛刻的要求 n原来的牛顿法就相当于阻尼牛顿法的步长因子取成固定值1的情况 第16页/共47页 2021-8-418 第17页/共47页 2021-8-419 给定x0， k=0 dk=2f(xk)-1f(xk) ak=minf(xk+akdk) xk+1=xk+akdk xk+1-xk x*=xk+1 结束 k=k+1 第18页/共47页 2021-8-420 第19页/共47页 2021-8-421 * *可取最优步长或下降步长可取最优步长或下降步长 二）基本思二）基本思 想想 梯度方向是目标函数上升最快的方梯度方向是目标函数上升最快的方 向，负梯度方向

9、则是最速下降方向；向，负梯度方向则是最速下降方向； )( )()()() 1(kkkk XFXX 2 2）迭代公迭代公 式式 1 1）沿沿负梯度方向搜索负梯度方向搜索： )()()( )( kkk gXFS k g 三）终止判别条三）终止判别条 件件 梯度法梯度法 第20页/共47页 2021-8-422 给定给定 X0 ， K=0 ，X（ （K）=X0 K=K+1 X(k)=X X*= X（ （K） F*=F（X*） 结结 束束 N Y 计算计算 )()( , kk gg )(k g 从从 出发出发，沿沿 搜索得搜索得 )(k X )(k g )()()(kkk gXX * * “最速下降性

10、最速下降性”只只 是迭代点邻域的局部是迭代点邻域的局部 性质。从全局看，并性质。从全局看，并 非最速下降方向。非最速下降方向。 四四. .迭代步骤迭代步骤 第21页/共47页 1 () 2 TT f XXA XB Xc 0 1 d d0 T H 01 d ,d 0 d 1 d 第22页/共47页 0 , ,1,2, T ij SASiji jm 0 T ij SASij 1122 0 , ,1,2, mm a Sa Sa Siji jm 1122 0 T imm S A a Sa Sa S 1122 0 TTTT iiiiimim a S ASa S ASa S ASa S AS 如果 112

11、2 TT ii a S ASa S AS mi TT imii aa SSSAS A0 彼此关于A共轭的向量线性无关 0 i a 第23页/共47页 123 1000 0100 , , , 0010 0001 n eeee 1 n iii i Sa e 第24页/共47页 ( )(2)(2)(2)(1)(1)nnnnnn XXSS ( )(1)(1)(1)nnnn XXS *(0)(0)(0)(1)(1)(1)(1)nn XXSSS n维问题只需要收索n次 第25页/共47页 2021-8-427 ) 1 ( 1 )2()2( )(SXFS第二方向：第二方向： )( )1()1( XFS 第一

12、方向：第一方向： 二二. .共轭方向的构成共轭方向的构成 * *利于突破函数的非二次性利于突破函数的非二次性; ; 每轮搜索方向为一组共轭方向每轮搜索方向为一组共轭方向, , 但第一方向为负梯度方向但第一方向为负梯度方向. . 一一. .基本思路基本思路 )1()1()1()2( SXX * 可表示为两个负梯度方向的线性组合可表示为两个负梯度方向的线性组合。 )2( S ) 1 ( X)2( S )2( X ) 1 ( S )( )2( XF 第26页/共47页 2021-8-428 () ( )( ) 2 1 (1)(1) (1) () ()() () ()()() K kTk k kTk

13、K F X F XF X F XF XF X )() 1() 1( )( k k kk SXFS ， 以后新方向均按下述迭代公式产生以后新方向均按下述迭代公式产生： (2)(1) (2) (2)(2) (1) 1 (2)(1)(1)(1) (1) (1) ()() () ()() ()()()() () T T T T F XF X F X F XF X F XF XF XF X F X 因而因而， 0 ) 1 ()2( ASS T 因为因为（A A是二次函数的是二次函数的Hessian Hessian 矩阵矩阵） CXBAXXXF TT 2 1 )( BAXXF)( 二次函数二次函数 其梯度

14、其梯度 为为 故有故有0)( ) 1 ( 1 ) 1 ( 1 )2( ASSXF T )1()1( )1()2( 1 )( ASS ASXF T T )1 ()1 ()1 ()2( SXX )1()1()1()2()1()2( )()()(ASXXAXFXF 故有故有 又又0)( )2() 1 ( XFS T （正交正交） 第27页/共47页 2021-8-429 (2)(1) ()0 T F XS (2)(1)(1)(1) XXS (1)(1)(1)(1) ()0 T F XSS ()F XAXB 2(1) 0 T AXBS (1)(1)(1)(1) 0 T A XSBS (1)(1)(1)

15、(1) 0 T TT XSABS (1)(1) (1) (1)(1) TT T XABS SAS (1)(1) (1) (1)(1) T T AXBS SAS 1(1) (1) (1)(1) T T FS SAS 第28页/共47页 2021-8-430 K n 给定给定X0, n, K=1, X(K)=X0 S (K) = - F(X(K) 从从X(K)始始，沿沿S(K)进行一维搜索得进行一维搜索得X(K+1) K=K+1 是是 是是 否否 否否 计算计算 )(),( )1()1( KK XFXF )( ) 1(K XF 结结 束束 )( )1( )1( K K XFF XX ) 1( 0

16、K XX )() 1() 1( 2 )( ) 1( )( ) )( )( ( K K KK K K K SXFS XF XF 重置负梯度方向重置负梯度方向 三三. .迭代步骤迭代步骤 第29页/共47页 2021-8-431 四四. .共轭梯度法的特点共轭梯度法的特点 1.1.为共轭方向法为共轭方向法, ,具有二次收敛性具有二次收敛性; ; 2.2.算法简单算法简单, ,编程容易编程容易, ,存储量小存储量小; ; 3.3.需用到一阶导数需用到一阶导数. . 第30页/共47页 2021-8-432 )( )()()() 1(kkkk XFEXX )()( )(1)()()() 1(kkkkk

17、 XFXHXX 能否克服各自的缺点，综合发挥其优点？能否克服各自的缺点，综合发挥其优点？ 2 2）阻尼牛顿）阻尼牛顿 法法 1 1）梯度法）梯度法 一）问题的提出一）问题的提出 由由Davidan、Fletcher、Powell共同提出。共同提出。 * * 简单，开始时目标函数值下降较快，但越来越慢。简单，开始时目标函数值下降较快，但越来越慢。 * * 目标函数值在最优点附近时收敛快，但要用到目标函数值在最优点附近时收敛快，但要用到 二阶导数和矩阵求逆。二阶导数和矩阵求逆。 第31页/共47页 2021-8-433 )( )()()() 1(k k kkk XFAXX 1 kk HA2 2）迭

18、代终了迭代终了， 具有二阶收敛性具有二阶收敛性。 EAk k , 0* *1 1）当当 和梯度法一样，便于突破函数的非二次性和梯度法一样，便于突破函数的非二次性； 式中，式中，1.1.A Ak k 构造矩阵 构造矩阵（在迭代中产生，不用求导和作矩阵求逆）（在迭代中产生，不用求导和作矩阵求逆） 迭代公式：迭代公式： )( )()()() 1(kkkk XFEXX )()( )(1)()()() 1(kkkkk XFXHXX )( )()(k k k XFAS-拟牛顿方向拟牛顿方向 2. 第32页/共47页 2021-8-434 k A1） 应为正定对称矩阵；应为正定对称矩阵； k A(1) 应为

19、对称矩阵应为对称矩阵； E E和和 均为对称矩均为对称矩 阵阵 1 K H k A(2) 应为正定矩阵应为正定矩阵； 因为因为 应使应使 为函数下降方向为函数下降方向,即即 与与 的夹角应小于的夹角应小于900: k A )(k S )(k S k g ( ) 0 kTk F XS 0 kTk k F XAF X 0 kTk k F XAF X 二次型正二次型正 定定 11 kkkTkk fXfXF XXX 1 0 kTkk F XXX 0 kTk F XS 第33页/共47页 2021-8-435 k A 1 k H 2） 能逼近能逼近 以近似二次函数的梯度作为下一迭代点处的梯度以近似二次函

20、数的梯度作为下一迭代点处的梯度: : )()()()( 2 1 )()( k k TkkT k k XHXXgXFX 其梯度其梯度 )(k kk XHgg )( 1 k kkk XHgg kkkkk k gHggHX 1 1 1)( )( 1k A 1 k H用用 代替代替 , 得得 kk k gAX 1 )( 拟牛顿条件拟牛顿条件 第34页/共47页 2021-8-436 1k A 四四. 的构造方法的构造方法 kkk AAA 1 用递推方法构用递推方法构 造造 kkkkk k gAAgAX )( 1 )( 于是有于是有 k A 关键是确定关键是确定 校正矩阵校正矩阵 kk k kk gAX

21、gA )( (1) 再令再令 T kkkkk Tkk kk gAgAXXA )()( (2) 代入代入(1): kk k kk T kkkkk Tk k k gAXgAggAgXX )()()( , 1 )( k Tk k gX . 1 kk T kk gAg 两边对比得两边对比得: ),/(1 )( k Tk k gX )./(1 kk T kk gAg 回代到回代到(2)(2)得得: kk T k T kkkk k Tk Tkk k gAg gAgA gX XX A )( )()( (3) 待定常待定常 数数 可保证可保证AK的对称的对称 性性 963 642 321 321 3 2 1

22、第35页/共47页 2021-8-437 五五. .迭代步骤迭代步骤 , 0 nX给定 )(),(, 00 XFgXFFXX 1k gASEA , XSX搜索得极小点沿始从 , gg ,计算 g 是是 是是 否否 否否 nk )( , XFF X输出 结束 XX 1 kk XXgg gASAAA A gggXXX , , . , 计算 因计算机的舍入误因计算机的舍入误 差，构造矩阵的正差，构造矩阵的正 定性可能遭到破坏，定性可能遭到破坏， 故作故作n n次后重置单次后重置单 位矩阵。位矩阵。 第36页/共47页 2021-8-438 T n T T e e e 1.00 . 0.10 0.01

23、 2 1 1)1)几何描述几何描述( (以二维问题为例）以二维问题为例） 二）迭代步骤二）迭代步骤 依次沿个依次沿个n n个正交坐标轴的方向搜索：个正交坐标轴的方向搜索： 一）搜索方向一）搜索方向 第37页/共47页 2021-8-439 2) 坐标轮换法流程图坐标轮换法流程图 从从 出发沿出发沿 方向进行一维搜索得方向进行一维搜索得 ： 1i X i e i iiii eXX 1)( i XFF 1i ni 给给定定, 0 nX 0 XX n 1ii FF XX n 结结 束束 1 0 kk XX n 1k 是 否 否 是 第38页/共47页 2021-8-440 三三) ) 算法特点算法特

24、点 如如:(:(1)1)等值线为椭圆等值线为椭圆, ,且长短轴分别平行于坐标轴时且长短轴分别平行于坐标轴时-高效高效 1 x 2 x o (2(2) )等值线为如图脊线时等值线为如图脊线时-无效无效 1 x 2 x o (3(3) )一般情况一般情况-低效低效 1 1）编程简单，容易掌握；）编程简单，容易掌握； 2 2）收敛速度通常较低（）收敛速度通常较低（其有效性取决于目其有效性取决于目 标函数的性态标函数的性态），仅适于低维的情况。），仅适于低维的情况。 第39页/共47页 2021-8-441 2 x 3 x 1 x o 0 X 1 e 2 e 3 e 3 3）若目标函数为正定二次函数，

25、）若目标函数为正定二次函数，n n轮结束后即可到达轮结束后即可到达 最优点。最优点。 2 2）每轮迭代产生一个新方向取代原来的第一方向，）每轮迭代产生一个新方向取代原来的第一方向，n n 轮迭代后可产生轮迭代后可产生n n个彼此共轭的方向个彼此共轭的方向； n X 1 1）开始采用坐标轴方向）开始采用坐标轴方向； 一）一）PowellPowell基本算法基本算法 第40页/共47页 2021-8-442 2 x 3 x 1 x o 0 X 2 e 3 e 1 X 应用应用 PowellPowell基本算法时，若有一次搜索的最优步长为基本算法时，若有一次搜索的最优步长为0 0， 且该方向被换掉，则该算法失效。且该方向被换掉，则该算法失效。 1 1）问题的提出）问题的提出 第41页/共47页 2021-8-443 * * 根据根据PowellPowell条件判定是否需换方向；条件判定是否需换方向； 如需换向，则换掉函数值下降量最大的方向如需换向，则换掉函数值下降量最大的方向. .